• 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…

• 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.

• 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.

• 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$.

• 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…

• 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}\}$.

• 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$.∎

• Notice what the last two mean: two equivalence classes are either identical or disjoint (share no elements).
• Equivalence classes never overlap partially.

• 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$

• Can't be in zero because of condition 3.
• Can't be in more than one because of condition 2.

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.

• So every equivalence relation partitions its set into equivalence classes.
• And every partition creates an equivalence relation: the “is in the same partition” relation.

• 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$.

• 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.

• 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}$.

• 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$.∎

• No relation can refine equals, because the equivalence classes can't be subdivided any more.

• Any other relation on $A$ is a refinement of it.