Equivalence Relations

What does it mean for two things to be "the same for our purposes"? Sometimes you want strict equality; more often you want a coarser notion, same parity, same remainder mod 7, same fingerprint hash, same connected component, same colour. Each of these is a relation that behaves like $=$: it is reflexive (everything is the same as itself), symmetric (if $a$ matches $b$, then $b$ matches $a$), and transitive (matching chains together). Such a relation is an equivalence relation, and its great theorem is that it carves the underlying set into disjoint "sameness classes" that completely cover it. This is the precise content of the partition theorem, and it is the structural backbone of modular arithmetic, quotient constructions, clustering, and data deduplication.

Definition

An equivalence relation on a set $A$ is a relation $\sim$ that is reflexive, symmetric, and transitive:

Equivalence classes

For $a \in A$, the equivalence class of $a$ is

Two crucial facts: $a \in [a]$ always (reflexivity), and $[a] = [b] \iff a \sim b$. So writing $[a] = [b]$ is just a tidy way of saying "$a$ and $b$ are equivalent."

The partition theorem

A partition of $A$ is a collection of nonempty, pairwise disjoint subsets whose union is $A$. The partition theorem says:

The equivalence classes of any equivalence relation on $A$ form a partition of $A$.

Conversely, any partition of $A$ defines an equivalence relation: declare $a \sim b$ iff $a$ and $b$ lie in the same block.

The two structures, "equivalence relation on $A$" and "partition of $A$", are perfectly equivalent. Choose whichever is more convenient for the problem at hand.

The canonical example

For a positive integer $n$, define congruence modulo $n$ on $\mathbb{Z}$ by $a \equiv b \pmod n$ iff $n \mid (a - b)$. This is an equivalence relation. Its classes are the residue classes $[0], [1], \ldots, [n-1]$, exactly $n$ classes that partition $\mathbb{Z}$.

(Switch presets to see equivalence classes for $n \bmod 3$ on ${0, \ldots, 11}$, $n \bmod 4$, parity, or strings-by-length. Click any element to lift its whole class and confirm: equivalence classes really are disjoint blocks whose union covers the underlying set.)

Pause and think: Why must every equivalence class be nonempty? (Hint: reflexivity guarantees one specific element.) Why must any two distinct classes be disjoint? (Hint: if $c \in [a] \cap [b]$, what does transitivity force?)

Try it

• Verify that $\equiv \pmod 4$ is an equivalence relation on $\mathbb{Z}$. List its classes within ${0, 1, \ldots, 15}$.
• The partition ${{a, b}, {c}, {d, e}}$ of ${a, b, c, d, e}$ defines an equivalence relation. List all of its pairs.
• Decide whether $R = {(1,1),(2,2),(1,2),(2,1)}$ on ${1, 2, 3}$ is an equivalence relation. If not, which property fails?
• Predict: how many equivalence relations are there on a 3-element set ${a, b, c}$? (Hint: by the partition theorem, the answer equals the number of partitions of a 3-element set, enumerate them.)
• Show that "is similar to" (triangles being similar) is an equivalence relation on the set of all triangles.

A trap to watch for

Students sometimes "prove" symmetry by writing $a = b \Rightarrow b = a$, that is the symmetry of equality, not of the relation under inspection. To prove $\sim$ is symmetric, you must start from $a \sim b$ (whatever that specifically means, e.g., $n \mid (a - b)$) and derive $b \sim a$ from that meaning. Don’t conflate "looks symmetric" with "is symmetric"; verify with the actual definition every time.

What you now know

You can verify or refute the three axioms of an equivalence relation, compute equivalence classes, apply the partition theorem in both directions, and recognise modular arithmetic, union-find, clustering, and deduplication as instances of the same structure. Chapter 5 turns the camera onto relations that are functions, the next-most-special kind of relation after equivalences and orderings.

References

• Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §4.5.
• Hammack, R. (2018). Book of Proof, ch. 11.
• Bloch, E. D. (2011). Proofs and Fundamentals (2nd ed.). Springer, ch. 5.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, ch. 21 (Union-Find).
• Jech, T. (2003). Set Theory: The Third Millennium Edition. Springer, ch. 2.