# 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.
• 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$$.
• 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:
1. $$A_i\ne\emptyset$$
2. $$A_i\cap A_j = \emptyset$$ if $$i\ne j$$
3. $$\bigcup_i A_i = S$$
• 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.