Equivalence Relations and Equivalence Classes

2. Equivalence Relations and Equivalence Classes

Equivalence relations formalise the everyday idea of "being alike" in some respect — same remainder on division, same length, same shape, and so on. To prove $R$ is an equivalence relation, all three properties from Section 1 must be verified explicitly; to disprove it, a single counterexample to any one property is enough.

Worked Illustration — Congruence Modulo 5

Let $R$ be the relation on $\mathbb{Z}$ defined by $a\,R\,b$ iff $5$ divides $a - b$ (written $a \equiv b \pmod 5$).

• Reflexive: $a - a = 0$, and $5 \mid 0$, so $(a,a) \in R$ for every $a$.
• Symmetric: if $5 \mid (a-b)$ then $a-b = 5k$ for some integer $k$, so $b - a = 5(-k)$, and $5 \mid (b-a)$.
• Transitive: if $5 \mid (a-b)$ and $5 \mid (b-c)$, write $a-b=5k$, $b-c=5m$; then $a-c = (a-b)+(b-c) = 5(k+m)$, so $5 \mid (a-c)$.

All three hold, so $R$ is an equivalence relation on $\mathbb{Z}$.

Equivalence Classes

Equivalence classes have a remarkable structural property: any two equivalence classes are either identical or completely disjoint, and their union is all of $A$ — that is, the classes partition $A$ into non-overlapping blocks.

For congruence modulo $5$ above, there are exactly five classes:

Every integer lies in exactly one of these five classes, decided entirely by its remainder on division by $5$. …