Equivalence Classes and Quotient Sets
One might want to know precisely when two objects are “equivalent” with respect to a given relation. Not every relation gives us a natural ability to determine whether two objects are equivalent, but when they do, we give them a special name.
Property 1 states that in an equivalence relation \(R\) on a set \(A\), all elements of the set \(A\) are related to themselves. Property 2 states that you can swap the order in the relation. Property 3 states that if an element \(a\) is related to a second element \(b\) and that second element is related to a third element \(c\), then it must be the case that \(a\) is related to that third element \(c\).
An Example of an Equivalence Relation
The relation of equivalence, modulo \(m=2\), \(\equiv_{mod\ 2}\), is an equivalence relation.
To see this, note that for any integer \(x\), we have \(x \equiv x\ (\text{mod}\ m)\); i.e. \(x\) has the same remainder as itself when divided by \(2\). Thus, \(\equiv_{mod\ 2}\) is reflexive.
To show symmetry, suppose we have \(a,b\in \mathbb{Z}\) so that \(a\equiv b\ (\text{mod}\ 2)\). Then by definition of equivalence, mod \(m\), note \(m\vert (a-b)\) and so \(m\vert (b-a)\), which implies \(b\equiv a\ (\text{mod}\ 2)\). (Alternatively, but less precisely, \(a\equiv b\ (\text{mod}\ 2)\) means \(a\) has the same remainder as \(b\) when divided by \(2\), so certainly \(b\) has the same remainder as \(a\) when divided by \(2\). Hence, \(b\equiv a\ (\text{mod}\ 2)\), and we have symmetry.
To show transitivity, suppose we have \(a\equiv\ b\ (\text{mod}\ 2)\) and \(b\equiv\ c\ (\text{mod}\ 2)\) for some \(a,b,c\in \mathbb{Z}\). Then \(a\equiv\ b\ (\text{mod}\ 2)\) implies \(2\vert (b-a)\), which further implies that \(b-a=2n\) for some \(n\in \mathbb{Z}\). Similarly, \(b\equiv\ c\ (\text{mod}\ 2)\) implies \(2\vert (c-b)\), further implying \(c-b=2k\) for some \(k\in \mathbb{Z}\). Solving for \(b\) in the equation \(b-a=2n\), we get \(b=2n+a\). Substitution this in for \(b\) in the second equation \(c-b=2k\) gives us \(c-(2n+a)=2k\). Distributing the negative gives \(c-2n-a=2k\). Adding \(2n\) to both sides gives \(c-a=2k+2n\). Finally, factoring a \(2\) out of the right-hand-side gives \(c-a=2(k+n)\), which implies that \(2\vert (c-a)\) which further implies \(c\equiv a\ \text{mod}\ 2\). Therefore equivalence, mod \(2\) is transitive.
All three properties in the definition of equivalence relation have been satisfied, so we have that equivalence mod \(2\) is indeed an equivalence relation.
(Note that the same reasoning above can be applied to any nonnegative \(m\); not just \(m=2\). )
Two Examples of Relations that are NOT Equivalence Relations
- The divides relation \(\vert\) on the integers. Note that \(2\ \vert\ 4\) but \(4 \not|\ 2\). So therefore “divides” is not symmetric.
- The “less than” relation on the set of real numbers is not an equivalence relation. Note that \(2\not<2\) so \(“<“\) is not reflexive.
Equivalence Classes and Partitions
An equivalence relation is called such because it imposes a sense of “equality” or “sameness” on elements of a set despite being apparently different. It is often helpful to group these equivalent elements of a set together into a set of their own.
Given any equivalence relation \(R\) on a set \(A\), every element \(x\) of \(A\) must belong to some equivalence class (by default, \(x\in [x]\)). Furthermore, it can be easily deduced that each element of \(A\) can only belong to exactly one equivalence class (because if element \(x\) were in two different classes, say \([a]\) and \([b]\), then \(x\) is equivalent to everything in \([a]\) and everything in \([b]\). This implies by transitivity that everything in \([a]\) and \([b]\) are equivalent, and thus must be the same class; i.e. \([a]=[b]\)).
What the partition theorem essentially says is that, given an equivalence relation on a set \(A\), the set can be “broken apart” or partitioned into disjoint sets formed by all the different equivalence classes.
Example of Equivalence Class Partition
Lets look at the set of integers \(\mathbb{Z}\) with the relation \(\equiv_{\text{mod}\ 3}\). Then, let:
- \([0]=\{b\vert\ b \equiv 0\ \text{mod}\ 3\}\) (i.e. the set of all integers with remainder \(0\) when divided by \(3\).)
- \([1]=\{b\vert\ b \equiv 1\ \text{mod}\ 3\}\) (i.e. the set of all integers with remainder \(1\) when divided by \(3\).)
- \([2]=\{b\vert\ b \equiv 2\ \text{mod}\ 3\}\) (i.e. the set of all integers with remainder \(2\) when divided by \(3\).)
Note, by the set definitions above, that:
- \([0]=\{…,-9,-6,-3,0,3,6,9,…\}\)
- \([1]=\{…, -8,-5,-2,1,4,7,10,…\}\)
- \([2]=\{…, -10,-7,-4,-1,2,5,8,11,…\}\)
Notice that the three sets above have NOTHING IN COMMON; i.e. they are disjoint. Notice also that the every integer belongs to exactly one of these three sets. Due to this, it follows that if you union all three sets, you will get the set of all integers \(\mathbb{Z}\). Hence, the sets \([0],[1],[2]\) partition \(\mathbb{Z}\).
Nope!
Note that \(3\leq 4\) but \(4\not\leq 3\). Thus the “Less than” relation is not symmetric and therefore not an equivalence relation.
Nope!
\(R\) is not transitive. Note that \(0R1\) and \(1R2\) but \(0\not R 2\).
Yes!
Reflexivity: Note that \((1,1),(2,2),(3,3)\in S\), so all elements of \(A\) relate to themselves.
Symmetry: Note that for every ordered pair \((a,b)\in S\) we have \((b,a)\in S\). That is, since \((1,2)\in S\) so is \((2,1)\); since \((1,3)\in S\) so is \((3,1)\), etc.
Transitivity: Note that for every \(a,b,c\in A\), \(aRb\) and \(bRc\) imply \(aRc\). For example, we have \(1R1\) and \(1R2\) which implies \(1R2\), and \(1R3\) and \(3R1\) implies \(1R1\), etc. This works for any pair of ordered pairs that “chain together” in this way.
\((1,1)\) and \((2,1)\).
As it stands, \(R\) is not reflexive and symmetric, so let’s work on that before worrying about transitivity, which tends to be more complicated. We want every element in \(A\)( to relate to itself (reflexive). We already have \(2R2\) and \(3R3\) but we don’t have \(1R1\). So add \((1,1)\) to \(R\). Note that since \((1,2)\in R\), we also need \((2,1)\in R\) to ensure symmetry.
After these two additions, it is easy to check that the relation is reflexive, symmetric, and transitive.
\([1]=\{…,-9,-4,1,6,11,…\}\); i.e. the set of all multiples of \(5\) plus 1.
Roughly speaking, the given relation is nothing more than the set of all pairs of integers \((a,b)\) that have the same remainder when divided by \(5\); that’s what it means for \(a\equiv\ b\ (\text{mod}\ 5)\). Thus, the set \([1]\) is the set of all \(a\in \mathbb{Z}\) that have \(a\equiv 1\ (\text{mod}\ 5)\); i.e. the set of all \(a\in\mathbb{Z}\) that have remainder \(1\) when divided by \(5\). Such numbers are specifically the multiples of \(5\) plus 1.
\([1]=\{1,2,3\}=[2]\)
Everything in the relation is related to everything else. So everything in \(A\) that relates to \(1\) (i.e. everything in \([1]\)) is \(1,2\) and \(3\). Same goes for everything related to \(2\).