Equivalence Relations
- When we looked at the relation for “equals” (that is \(\{(a,a)\mid a\in A\}\)), it had all three of our nice properties.
- It is reflexive, symmetric, and transitive.
- Congruence modulo \(k\) did as well: \(\{(a,b)\mid a,b\in \mathbf{Z}, a\equiv b \ (\text{mod }k)\}\).
- It is reflexive (\(a\) congruent to itself) and symmetric (swap \(a\) and \(b\) and relation would still hold).
- It's transitive since if \(a-b=mk\) and \(b-c=nk\) then \(a-c=(a-b)+(b-c)=(m+n)k\).
- We can generalize that idea…
- An equivalence relation is a relation that is reflexive, symmetric, and transitive.
- If two elements are related by some equivalence relation, we will say that they are equivalent (under that relation).
- We have already seen that \(=\) and \(\equiv(\text{mod }k)\) are equivalence relations.
- Some more examples…
- Real numbers that have the same fractional part: \(\{(a,b)\mid a,b\in\mathbf{R}, a-b\in \mathbf{Z}\}\).
- Reflexive: \(a-a=0\in \mathbf{Z}\).
- Symmetric: if \(a-b\in\mathbf{Z}\) then \(b-a=-(a-b)\in\mathbf{Z}\).
- Transitive: if \(a-b, b-c\in\mathbf{Z}\), then \(a-c=(a-b)+(b-c)\in \mathbf{Z}\).
- For a function \(f:A\rightarrow B\), the relation on \(A\) “maps on to the same element”. That is, \(\{(a_1,a_2)\mid f(a_1)=f(a_2)\}\).
- Reflexive: \(f(a_1)=f(a_1)\).
- Symmetric: \(f(a_1)=f(a_2)\) iff \(f(a_2)=f(a_1)\).
- Transitive: if \(f(a_1)=f(a_2)\) and \(f(a_2)=f(a_3)\) then \(f(a_1)=f(a_3)\).
- Remember that our relations don't have to be on numbers. Let \(L\) be the set of all lines on the plane. We will say that \((l_1,l_2)\in R\) if \(l_1\) is parallel to \(l_2\).
- [Not going to bother with the details, but should be obvious enough.]
- Words with the same number of letters.
- Reflexive: a word has the same number of letters as itself.
- Symmetric: if A has the same number of letters as B, then B has same as A.
- Transitive: if A/B and B/C have same number of letters, then so do A and C.
- Real numbers that have the same fractional part: \(\{(a,b)\mid a,b\in\mathbf{R}, a-b\in \mathbf{Z}\}\).
- But some that aren't equivalence relations:
- Divisibility.
- Reflexive: \(a\mid a\).
- Transitive: if \(a\mid b\) and \(b\mid c\) then \(a\mid c\).
- It's not symmetric: \(4\mid 12\), but \(12\nmid 4\).
- “Differ by at most one”: \(\{(a,b)\mid a,b\in\mathbf{R}, |a-b|\le 1\}\).
- Reflexive: \(|a-a|\le 1\).
- Symmetric: \(|a-b|=|b-a|\), so it's obvious.
- But not transitive: if \(a=1, b=2, c=3\), then \(|a-b|=|b-c|= 1\), but \(|a-c|=2\).
- Divisibility.
- Informally, all of the equivalence relations are all sort of “have some property in common” relations.
- Of course, saying that is no substitute for actually showing reflexive + symmetric + transitive.
- But it should give you a good guess whether something is an equivalence relation or not.
- Maybe a few more facts about equivalence relations will give you a better idea how to spot them…
- For an equivalence relation, you'll sometimes see this notation for \((a,b)\in R\): \(a\sim b\) or \(a\sim_R b\) or \(a\equiv b\) or \(a\equiv_R b\).
Equivalence Classes
- For an equivalence relation \(R\) on \(A\), we will define the equivalence class of an element \(a\in A\) as:
\[[a]_R = \{b\mid (a,b)\in R\}\,.\]
- That is, the subset of \(A\) where all elements are related to \(a\) by the relation.
- For example, with the “same fractional part” relation, \([0.3]_R=\{\ldots,-1.7,-0.7,0.3,1.3,2.3,\ldots\}\), and \([0]_R=\mathbf{Z}\).
- For equality (\(=\)), the equivalence classes are small: \([4]_{=} = \{4\}\).
- For “words with same the number of letters”, equivalence classes are like \([\text{hello}]_R= \{w\mid w\text{ a word}, w\text{ has five letters}\}\).
- For the equivalence class \([a]_R\), we will call \(a\) the representative for that equivalence class.
- Note that \(a\in [a]_R\) since \(R\) is reflexive.
Theorem: For an equivalence relation \(R\), two equivalence classes are equal iff their representatives are related. That is, \([a]_R=[b]_R\) iff \((a,b)\in R\).
Proof: First assume \([a]_R=[b]_R\). Since we know \(a\in [a]_R=[b]_R\), we know that \((a,b)\in R\).
Now, if \((a,b)\in R\), consider any \(c\in [b]_R\). By definition, \((b,c)\in R\) and since \(R\) is transitive, \((a,c)\in R\), so \(c\in [a]_R\) and \([b]_R\subseteq [a]_R\). With a similar argument, we get \([a]_R\subseteq [b]_R\) and thus \([a]_R= [b]_R\).∎
Theorem: Two elements are related if and only if their equivalence classes share any elements. That is, \((a,b)\in R\) iff \([a]_R \cap [b]_R\ne\emptyset\).
Proof: If \((a,b)\in R\), then we know that \(b\in [a]_R\). It is always the case that \(b\in [b]_R\). Thus \(b\in [a]_R \cap [b]_R\) and \([a]_R \cap [b]_R\ne\emptyset\).
If \([a]_R \cap [b]_R\ne\emptyset\), then let \(c\in [a]_R \cap [b]_R\). Then \((a,c),(b,c)\in R\). Since \(R\) is symmetric and transitive, we have \((c,b)\in R\) and then \((a,b)\in R\).∎
- The two above theorems combine to show that these three things are logically equivalent for an equivalence relation \(R\) on \(A\) and \(a,b\in A\):
\[(a,b)\in R \\ [a]_R=[b]_R \\ [a]_R \cap [b]_R\ne\emptyset\]
- Notice what the last two mean: two equivalence classes are either identical or disjoint (share no elements).
- Equivalence classes never overlap partially.
Partitions
- Another set theory definition: a partition of a set \(S\) is a collection of subsets of \(S\) such that the subsets are non-empty, pairwise disjoint, and cover all of \(S\).
- That is, a collection of subsets \(A_1,A_2,\ldots\subseteq S\) forms a partition of \(S\) if:
- \(A_i\ne\emptyset\)
- \(A_i\cap A_j = \emptyset\) if \(i\ne j\)
- \(\bigcup_i A_i = S\)
- That is, a collection of subsets \(A_1,A_2,\ldots\subseteq S\) forms a partition of \(S\) if:
- Notice that an element of \(S\) is in exactly one of the partitions.
- Can't be in zero because of condition 3.
- Can't be in more than one because of condition 2.
- In other words, a partition is a way to chop a set up into pieces.
Theorem: If we have an equivalence relation \(R\) on \(A\), the equivalence classes of a relation form a partition of \(A\).
Proof: Since \(a\in[a]_R\), we know that no equivalence class is empty.
From the above, we know that if \(a\) and \(b\) are in different equivalence classes then \((a,b)\not\in R\) and then \([a]_R \cap [b]_R=\emptyset\).
For any element \(a\in A\), we know that \(a\in [a]_R\), so the union of all equivalence classes covers \(A\).∎
Theorem: Consider a partition \(A_1,A_2,\ldots\) of a set \(S\). The partition forms the equivalence relation \((a,b)\in R\) iff there is an \(i\) such that \(a,b\in A_i\).
Proof idea: This relation is reflexive, symmetric, and transitive, so it is an equivalence relation. The equivalence classes of this relation are the \(A_i\) sets.
- Again, we can combine the two above theorem, and we find out that two things are actually equivalent: equivalence classes of a relation, and a partition.
- So every equivalence relation partitions its set into equivalence classes.
- And every partition creates an equivalence relation: the “is in the same partition” relation.
Refinement of Partitions
- Suppose we have two partitions of a set \(S\): \(P_1=\{A_1,A_2,\ldots\}\) and \(P_2=\{B_1,B_2,\ldots\}\).
- We say that \(P_1\) is a refinement of \(P_2\) if every \(A_i\) is a subset of some \(B_j\).
- … or that \(P_1\) is finer than \(P_2\), or that \(P_2\) is coarser than \(P_2\), or \(P_1\) refines \(P_2\).
- We could also say that one equivalence relation refines another: \(R_1\) is a refinement of \(R_2\) if the equivalences classes of \(R_1\) are a refinement of the equivalence classes of \(R_2\).
- Actually, if we have a relations where \(R_1\) is a refinement of \(R_2\), we know which equivalence classes are subsets.
- The equivalence class \([a]_1\) is a subset of \([a]_2\).
- We know \(a\) is in both, and since we have a partition, \([a]_2\) is the only option.
- For example, consider the partition formed by equivalence modulo 6, and by equivalence modulo 3.
- The equivalence classes are different: \([1]_{\text{mod}3}=\{\ldots,-5,-2,1,4,7,\ldots\}\) and \([1]_{\text{mod}6}=\{\ldots,-5,1,7,13\ldots\}\).
- But \(\text{mod }6\) is a refinement.
- Consider any \([a]_{\text{mod}6}\). Every element of that equivalence class is \(6k+a=3(2k)+a\), so it is in \([a]_{\text{mod}3}\). Thus \([a]_{\text{mod}6}\subseteq [a]_{\text{mod}3}\).
- But not every pair of relations/partitions (on/of the same set) have one refining the other.
- Consider the equivalence classes of congruence modulo 6 and the partition \(\{-1,-2,-3,\ldots\},\{0\},\{1,2,3\ldots\}\).
- Those partitions don't overlap nicely. (Actually, the only containment is \(\{0\}\subseteq [0]_{\text{mod}6}\).)
Theorem: For two equivalence relations \(R_1\) and \(R_2\), \(R_1\) refines \(R_2\), iff \(R_1\subseteq R_2\).
Proof: Suppose \(R_1\) refines \(R_2\) and that \((a,b)\in R_1\). The equivalence classes have \([a]_{1}\subseteq [a]_{2}\). Since \((a,b)\in R_1\subseteq [a]_{2}\), we have \((a,b)\in R_2\).
Now suppose \(R_1\subseteq R_2\) and consider a \([a]_1\). For any \(b\in [a]_1\), we know that \((a,b)\in R_1\). Thus \((a,b)\in R_2\) and \(b\in [a]_2\). Each equivalence class for \(R_1\) is contained in an equivalence class for \(R_2\), so \(R_1\) is a refinement of \(R_2\).∎
- Informally, if \(R_1\) refines \(R_2\), then \(R_1\) is \(R_2\) with some extra restrictions.
- Now we can easily come up with examples of relations that are refinements of another.
- Having the same sign and fractional part is a refinement of having the same fractional part.
- Equals (\(R_{=}\)) is a refinement of congruence modulo 5.
- Since the equivalence classes of the equals relation are singletons (\([a]_{=}=\{a\}\)) it is somehow the “most refined” relation.
- No relation can refine equals, because the equivalence classes can't be subdivided any more.
- Similarly, the relation where everything is related (\(R=A\times A\)… the “complete relation”?) is the “least refined”.
- Any other relation on \(A\) is a refinement of it.