{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "*This notebook uses Python to generate a list of relations and check their properties (reflexive, symmetric, antisymmetric, transitive, and equivalence). Defintions and examples are taken from lecture 15 and 16 of a discrete math course taught by Professor Maltais at the University of Ottawa during the 2017 winter semester.*\n", "\n", "
\n", "\n", "# All Relations on a Set (and Their Properties)\n", "\n", "by [Ben Pyrik](http://www.wsundine.com/about), 2017/04/17\n", "\n", "A function is an assignment of elements from one set (the domain) to another set (the codomain) where every element of the domain is assigned only a single element from the codomain. In other words, every *pre-image* has one (and only one) *image*. Relations are similar, but looser in the sense that pre-images can have multiple images. If $1$ is an element of A, it can be related to $5$ *and* $6$. This kind of assignment is not possible with a function.\n", "\n", "A *binary relation* between two sets (A and B) is defined as \"a subset of A x B\" (i.e. the \"Cartesian product\" of A and B). Similarly, a relation between a set (A) and itself is defined as a subset of A x A. What does this mean?\n", "\n", "**Note:** I'm going to use lists instead of sets here due to complications with powerset." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "A = [1, 2]" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# for simplicity, make B = A\n", "B = [1, 2]" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[(1, 1), (1, 2), (2, 1), (2, 2)]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Applying definition of the Cartesian Product\n", "AB = [(a, b) for a in A for b in B]\n", "AB" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Though it may be tempting, the above is **not** the set of all possible relations between A and B. Rather, it is the superset of any relation between A and B--in other words, any relation between A and B will be a subset of this set.\n", "\n", "However, the powerset of AB **is** the set of all possible relations between A and B." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# http://sevko.io/articles/power-set-algorithms/#tocAnchor-1-9\n", "def is_bit_flipped(num, bit):\n", " return (num >> bit) & 1\n", "\n", "def powerset(set_):\n", " subsets = []\n", " for subset in range(2 ** len(set_)):\n", " new_subset = []\n", " for bit in range(len(set_)):\n", " if is_bit_flipped(subset, bit):\n", " new_subset.append(set_[bit])\n", " subsets.append(new_subset)\n", " return subsets" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[[],\n", " [(1, 1)],\n", " [(1, 2)],\n", " [(2, 1)],\n", " [(2, 2)],\n", " [(1, 1), (1, 2)],\n", " [(1, 1), (2, 1)],\n", " [(1, 2), (2, 1)],\n", " [(1, 1), (2, 2)],\n", " [(1, 2), (2, 2)],\n", " [(2, 1), (2, 2)],\n", " [(1, 1), (1, 2), (2, 1)],\n", " [(1, 1), (1, 2), (2, 2)],\n", " [(1, 1), (2, 1), (2, 2)],\n", " [(1, 2), (2, 1), (2, 2)],\n", " [(1, 1), (1, 2), (2, 1), (2, 2)]]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pAB = powerset(AB)\n", "# order sets from smallest to largest\n", "pAB = sorted(pAB, key=len)\n", "pAB" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "pAB contains all possible subsets of A x B (and equivalently) all possible relations between A and B. Some are functions (e.g. #6), but most are not.\n", "\n", "How many relations are there? You could count them, but I'll save you the trouble." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "16" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(pAB)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are 16 relations between the set $A$ and itself. \n", "\n", "Another way of determining this number is to use the formula\n", "\n", "$$\n", "\\begin{align}\n", " |P(A \\times B)| &= 2^{|A \\times B|} \\\\\n", " &= 2^{|A| |B|} \\\\\n", " &= 2^{|2| |2|} & \\text{Substituting the cardinalities of A and B} \\\\\n", " &= 2^{4} \\\\\n", " &= 16\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Properties of Relations on a Set\n", "\n", "### Reflexive\n", "\n", "A relation $R$ on a set $A$ is called **reflexive** if\n", "\n", "$$ \\forall u \\in A, \\ \\ (u, u) \\in R$$" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# function that determines if a relation (r) on a set (A) is reflexive (or not)\n", "def reflexive(r, A):\n", " '''(list, list) -> boolean'''\n", " for u in A:\n", " # look for (u, u), return False if it wasn't found\n", " try:\n", " r.index((u, u))\n", " except ValueError:\n", " return False\n", " \n", " # loop completed without error, thus the relation must be reflexive\n", " return True" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# testing\n", "reflexive([(1, 1)], A)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "reflexive([(1, 1), (2, 2)], A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For all possible relations on the set $A$, which are reflexive?" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[] is NOT reflexive.\n", "\n", "[(1, 1)] is NOT reflexive.\n", "\n", "[(1, 2)] is NOT reflexive.\n", "\n", "[(2, 1)] is NOT reflexive.\n", "\n", "[(2, 2)] is NOT reflexive.\n", "\n", "[(1, 1), (1, 2)] is NOT reflexive.\n", "\n", "[(1, 1), (2, 1)] is NOT reflexive.\n", "\n", "[(1, 2), (2, 1)] is NOT reflexive.\n", "\n", "[(1, 1), (2, 2)] is reflexive!\n", "\n", "[(1, 2), (2, 2)] is NOT reflexive.\n", "\n", "[(2, 1), (2, 2)] is NOT reflexive.\n", "\n", "[(1, 1), (1, 2), (2, 1)] is NOT reflexive.\n", "\n", "[(1, 1), (1, 2), (2, 2)] is reflexive!\n", "\n", "[(1, 1), (2, 1), (2, 2)] is reflexive!\n", "\n", "[(1, 2), (2, 1), (2, 2)] is NOT reflexive.\n", "\n", "[(1, 1), (1, 2), (2, 1), (2, 2)] is reflexive!\n", "\n" ] } ], "source": [ "for relation in pAB:\n", " if (reflexive(relation, A)):\n", " print(str(relation) + \" is reflexive!\" +\"\\n\")\n", " else:\n", " print(str(relation) + \" is NOT reflexive.\" +\"\\n\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Symmetric\n", "\n", "A relation $R$ on a set $A$ is called **symmetric** if \n", "\n", "$$\\forall \\ u,v \\in A \\ \\ \\left((u, v) \\in R \\right) \\rightarrow \\left((v, u) \\in R \\right) \\text{is true.}$$\n", "\n", "While the symmetric definition could be implemented exactly as described, there is actually no reason to test $(u, v)$ pairs that are not in a particular relation. If a pair is not in the relation, then the left side of the implication is false and the implication is *vacuously* true (because false $\\rightarrow$ anything is always true). Of course, if $(v, u)$ happens to be in the relation, $(u, v)$ will be sought (and not found) causing `symmetric(r)` to return false." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def symmetric(r):\n", " '''(list) -> boolean'''\n", " # for every pair (u, v) in the relation\n", " for pair in r:\n", " # search for (v, u) <- order switched!\n", " try:\n", " r.index((pair[1], pair[0]))\n", " except ValueError:\n", " return False\n", " \n", " # if loop completes without error, every pair in the relation has a symmetric counterpart (r is symmetric!)\n", " return True" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# test\n", "symmetric([(1, 2), (2, 1), (2, 2)])" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "symmetric([(1, 2), (2, 2)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For all possible relations on the set $A$, which are symmetric? " ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[] is symmetric!\n", "\n", "[(1, 1)] is symmetric!\n", "\n", "[(1, 2)] is NOT symmetric.\n", "\n", "[(2, 1)] is NOT symmetric.\n", "\n", "[(2, 2)] is symmetric!\n", "\n", "[(1, 1), (1, 2)] is NOT symmetric.\n", "\n", "[(1, 1), (2, 1)] is NOT symmetric.\n", "\n", "[(1, 2), (2, 1)] is symmetric!\n", "\n", "[(1, 1), (2, 2)] is symmetric!\n", "\n", "[(1, 2), (2, 2)] is NOT symmetric.\n", "\n", "[(2, 1), (2, 2)] is NOT symmetric.\n", "\n", "[(1, 1), (1, 2), (2, 1)] is symmetric!\n", "\n", "[(1, 1), (1, 2), (2, 2)] is NOT symmetric.\n", "\n", "[(1, 1), (2, 1), (2, 2)] is NOT symmetric.\n", "\n", "[(1, 2), (2, 1), (2, 2)] is symmetric!\n", "\n", "[(1, 1), (1, 2), (2, 1), (2, 2)] is symmetric!\n", "\n" ] } ], "source": [ "for relation in pAB:\n", " if (symmetric(relation)):\n", " print(str(relation) + \" is symmetric!\" +\"\\n\")\n", " else:\n", " print(str(relation) + \" is NOT symmetric.\" +\"\\n\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Antisymmetric\n", "\n", "A relation $R$ on a set $A$ is called **antisymmetric** if\n", "\n", "$$\\forall u, v \\in A \\ \\left((u, v) \\in R \\ \\text{and} \\ (v, u) \\in R \\right) \\rightarrow (u = v) \\ \\text{is true.}$$\n", "\n", "Equivalently (in its contrapositive form)\n", "\n", "$$ (u \\ne v) \\rightarrow \\left( (u,v) \\notin R \\ \\text{or} \\ (v,u) \\notin R \\right)$$\n", "\n", "For this property (and possibly subsequent properties), I will use a helper function that searches a relation for a particular pair returning `True` if found and `False` otherwise. This should be easier to read than copy and pasting try/except blocks everywhere." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# helper that searches a relation (r) for a pair (u ,v)\n", "def rsearch(r, pair):\n", " '''(list, tuple) -> boolean'''\n", " try:\n", " r.index(pair)\n", " except ValueError:\n", " # not found\n", " return False\n", " \n", " # found\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As with symmetric, rather than implement the definition (which requires assigning variables to elements in $A$) I've elected to only test pairs that are in the relation. Also, I worked from the contrapositive definition because it felt easier to code." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def antisymmetric(r):\n", " '''(list) -> boolean'''\n", " # for every pair (u, v) in the relation\n", " for pair in r:\n", " u = pair[0]\n", " v = pair[1]\n", " \n", " # only test pairs with unique elements\n", " if (u != v):\n", " # relation can contain (u, v) or (v, u), but it CANNOT contain both\n", " if (rsearch(r, (u, v)) and rsearch(r, (v, u))):\n", " return False\n", " \n", " # if loop completes without returning, then the relation is antisymmetric\n", " return True" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# test\n", "antisymmetric([(1, 1), (1, 2), (2, 2)]) # Though the relation contains (1, 2), it does not contain (2, 1)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "antisymmetric([(1, 1), (1, 2), (2, 1)]) # It contains both (1, 2) AND (2, 1) so it must be..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For all possible relations on the set $A$, which are antisymmetric?" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[] is antisymmetric!\n", "\n", "[(1, 1)] is antisymmetric!\n", "\n", "[(1, 2)] is antisymmetric!\n", "\n", "[(2, 1)] is antisymmetric!\n", "\n", "[(2, 2)] is antisymmetric!\n", "\n", "[(1, 1), (1, 2)] is antisymmetric!\n", "\n", "[(1, 1), (2, 1)] is antisymmetric!\n", "\n", "[(1, 2), (2, 1)] is NOT antisymmetric.\n", "\n", "[(1, 1), (2, 2)] is antisymmetric!\n", "\n", "[(1, 2), (2, 2)] is antisymmetric!\n", "\n", "[(2, 1), (2, 2)] is antisymmetric!\n", "\n", "[(1, 1), (1, 2), (2, 1)] is NOT antisymmetric.\n", "\n", "[(1, 1), (1, 2), (2, 2)] is antisymmetric!\n", "\n", "[(1, 1), (2, 1), (2, 2)] is antisymmetric!\n", "\n", "[(1, 2), (2, 1), (2, 2)] is NOT antisymmetric.\n", "\n", "[(1, 1), (1, 2), (2, 1), (2, 2)] is NOT antisymmetric.\n", "\n" ] } ], "source": [ "for relation in pAB:\n", " if (antisymmetric(relation)):\n", " print(str(relation) + \" is antisymmetric!\" +\"\\n\")\n", " else:\n", " print(str(relation) + \" is NOT antisymmetric.\" +\"\\n\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Transitive\n", "\n", "A relation $R$ on a set $A$ is called an **transitive** if\n", "\n", "$$ \\forall u,v,w \\in A \\ \\left( (u, v) \\in R \\ \\text{and} \\ (v,w) \\in R \\right) \\rightarrow \\left( (u,w) \\in R \\right) \\ \\text{is true.} $$\n", "\n", "I followed the definition exactly for this one, the implementation (with 3 loops!) is costly--$O(n^3)$. " ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def transitive(r, A):\n", " '''(list, list) -> boolean'''\n", " for u in A:\n", " for v in A:\n", " for w in A:\n", " if (rsearch(r, (u, v)) and rsearch(r, (v, w))):\n", " # (u, w) must be in the relation\n", " if (not rsearch(r, (u, w))):\n", " return False\n", " \n", " # loop completed without returning, so the relation is transitive\n", " return True" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# test\n", "transitive([(1, 2), (2, 3), (1, 3)], A)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "transitive([(1, 2), (2, 1), (2, 2)], A) # 1 -> 2 and 2 -> 1, but 1 -> 1 is missing!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Can I do better? **Spoiler:** not really." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def transitive2(r):\n", " # for every pair (u, v)\n", " for pair in r:\n", " # take u and v\n", " u = pair[0]\n", " v = pair[1]\n", " \n", " # iterate through the relation looking for a pair with a first element = v\n", " for v_pair in r:\n", " if (v_pair[0] == v):\n", " # take second element from that pair (v, x)\n", " x = v_pair[1]\n", " \n", " # iterate through the relation again, looking for the pair (u, x)\n", " if (not rsearch(r, (u, x))):\n", " # if the pair is not found, the relation cannot be transitive\n", " return False\n", " \n", " # if function hasn't returned, the relation must be transitive\n", " return True" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# the same tests\n", "transitive2([(1, 2), (2, 3), (1, 3)])" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "transitive2([(1, 2), (2, 1), (2, 2)]) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is possible that `transitive2()` is more efficient than `transitive()`, but it is hard to tell and the logic is definitely more convoluted." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For all possible relations on the set $A$, which are transitive?" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[] is transitive!\n", "\n", "[(1, 1)] is transitive!\n", "\n", "[(1, 2)] is transitive!\n", "\n", "[(2, 1)] is transitive!\n", "\n", "[(2, 2)] is transitive!\n", "\n", "[(1, 1), (1, 2)] is transitive!\n", "\n", "[(1, 1), (2, 1)] is transitive!\n", "\n", "[(1, 2), (2, 1)] is NOT transitive.\n", "\n", "[(1, 1), (2, 2)] is transitive!\n", "\n", "[(1, 2), (2, 2)] is transitive!\n", "\n", "[(2, 1), (2, 2)] is transitive!\n", "\n", "[(1, 1), (1, 2), (2, 1)] is NOT transitive.\n", "\n", "[(1, 1), (1, 2), (2, 2)] is transitive!\n", "\n", "[(1, 1), (2, 1), (2, 2)] is transitive!\n", "\n", "[(1, 2), (2, 1), (2, 2)] is NOT transitive.\n", "\n", "[(1, 1), (1, 2), (2, 1), (2, 2)] is transitive!\n", "\n" ] } ], "source": [ "for relation in pAB:\n", " if (transitive(relation, A)):\n", " print(str(relation) + \" is transitive!\" +\"\\n\")\n", " else:\n", " print(str(relation) + \" is NOT transitive.\" +\"\\n\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Equivalence Relation\n", "\n", "A relation $R$ on a set $A$ is called an **equivalence** relation if R is **reflexive**, **symmetric**, and **transitive**." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def equivalence(r, A):\n", " '''(list) -> boolean'''\n", " if (reflexive(r, A) and symmetric(r) and transitive(r, A)):\n", " return True\n", " else:\n", " return False" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "equivalence([(1, 1), (2, 2)], A)" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "equivalence([(1, 1)], A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "From a performance standpoint, this one is **super** expensive!\n", "\n", "For all possible relations on the set $A$, which are equivalence relations?" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[] is NOT an equivalence relation.\n", "\n", "[(1, 1)] is NOT an equivalence relation.\n", "\n", "[(1, 2)] is NOT an equivalence relation.\n", "\n", "[(2, 1)] is NOT an equivalence relation.\n", "\n", "[(2, 2)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (1, 2)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (2, 1)] is NOT an equivalence relation.\n", "\n", "[(1, 2), (2, 1)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (2, 2)] is an equivalence relation!\n", "\n", "[(1, 2), (2, 2)] is NOT an equivalence relation.\n", "\n", "[(2, 1), (2, 2)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (1, 2), (2, 1)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (1, 2), (2, 2)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (2, 1), (2, 2)] is NOT an equivalence relation.\n", "\n", "[(1, 2), (2, 1), (2, 2)] is NOT an equivalence relation.\n", "\n", "[(1, 1), (1, 2), (2, 1), (2, 2)] is an equivalence relation!\n", "\n" ] } ], "source": [ "for relation in pAB:\n", " if (equivalence(relation, A)):\n", " print(str(relation) + \" is an equivalence relation!\" +\"\\n\")\n", " else:\n", " print(str(relation) + \" is NOT an equivalence relation.\" +\"\\n\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Closing Comments\n", "\n", "This turned out to be a good exercise. I think I have a better understanding of these properties and how to \"prove\" they are held by an arbitrary relation.\n", "\n", "For me, the most interesting discovery was that every property except reflexive can be determined by looking exclusively at the relation itself. This was not obvious from reading the definitions, but it is something you learn when doing these by hand during an exam. For example, to determine if `{(1, 2), (2, 1), (2, 2)}` is symmetric, the steps I find myself taking are:\n", "\n", "1. Look at the first pair: (1, 2)\n", "2. *Is (2, 1) also present?* **Yes**\n", "3. Look at the second pair: (2, 1)\n", "4. *Already covered, move on*\n", "5. Look at the third pair: (2, 2)\n", "6. *The elements are the same, move on*\n", "7. *All pairs checked and each had a symmetric counterpart, thus the relation is symmetric*\n", "\n", "In a way, the formal definition for symmetry is misleading.\n", "\n", "$$\\forall \\ u,v \\in A \\ \\ \\left((u, v) \\in R \\right) \\rightarrow \\left((v, u) \\in R \\right) \\text{is true.}$$\n", "\n", "I see \"for all u, v in A\" and think \"for all possible pairs in the set $A \\times A$...oh no, I have to generate a Cartesian Product\". But really, this is never necessary. While the reflexive property does require looking at the actual set, each element is considered independently (so the Cartesian Product is not needed).\n", "\n", "If it was up to me, I'd define symmetry like this\n", "\n", "$$\n", "\\begin{align}\n", "& \\text{Let: u, v} \\in A \\\\\n", "& \\forall \\ (u,v) \\in R \\ \\ \\left((u, v) \\in R \\right) \\rightarrow \\left((v, u) \\in R \\right) \\text{is true.}\n", "\\end{align}\n", "$$\n", "\n", "Which says: \"for all ordered pairs in the relation, this implication must be true in order for the relation to be symmetric\".\n", "\n", "To finish this I should really identify the relations that are functions as well as their types (injective, subjective, bijective), but I think I'll save that for another notebook." ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 1 }