Equivalence Classes

Intro to Proofs · Axiom Academy

How an equivalence relation automatically carves a set into disjoint classes — with congruence mod n as the model example. 1. What Is an Equivalence Relation? A relation on a set S is an equivalence relation when it satisfies three properties at once. Together they encode exactly what we mean by elements being "the same" in some respect. Every element relates to itself: for all . The relation reads both ways: if then . It chains together: if and then . Drop any one and the structure breaks — only all three give clean classes. 2. The Equivalence Class of an Element Pick any element a . Sweep up everything equivalent to it, and you get its equivalence class [a] . The element a is called a representative of that class. Here is the payoff. The classes don't just sit there — they tile the whole set with no gaps and no overlaps. every element lies in exactly one class, and any two classes are either identical or completely disjoint. Why it's forced: suppose two classes [a] and [b] share an element c . Then and . By symmetry and transitivity, — and that forces every member of [a] into [b] and vice versa. So the classes are equal. They cannot merely overlap : they coincide or stay apart. 4. The Model Example: Congruence mod n The classic equivalence relation lives on the integers. Define to mean n divides a - b . This is reflexive, symmetric, and transitive — so it partitions into n classes called residue classes . [0] = …, −10, −5, 0, 5, 10, 15, … [1] = …, −9, −4, 1, 6, 11, 16, …

This is the written version of the interactive lesson above. See the full Intro to Proofs course.