Equivalence relations
Equivalence relations capture the idea of 'the same in some respect'. They split a set into non-overlapping groups.
Definition
An equivalence relation is reflexive, symmetric, and transitive. Examples: 'has the same birthday as', 'has the same remainder when divided by 3', 'is congruent to' for triangles. Each captures a notion of sameness that ignores some details.
Equivalence classes
The equivalence class of \(a\), written \([a]\), is the set of all elements equivalent to \(a\). For 'same remainder mod 3' on the integers, there are three classes: \([0] = \{\ldots, -3, 0, 3, 6, \ldots\}\), \([1]\), and \([2]\). Any element of a class can represent it.
Partitions
The equivalence classes of an equivalence relation form a partition: non-empty, non-overlapping subsets that together cover the whole set. Conversely, every partition defines an equivalence relation, 'is in the same part as'. Equivalence relations and partitions are two descriptions of the same thing.
Congruence modulo n
Integers \(a\) and \(b\) are congruent modulo \(n\), written \(a \equiv b \pmod{n}\), if \(n\) divides \(a - b\). So \(17 \equiv 2 \pmod{5}\). Congruence is an equivalence relation with \(n\) classes, the remainders \(0\) to \(n - 1\). Clock arithmetic is arithmetic modulo 12.
a \equiv b \pmod{n} \iff n \mid (a - b)Worked example
Show congruence mod \(n\) is transitive. If \(n \mid (a - b)\) and \(n \mid (b - c)\), then \(n\) divides their sum, \(a - c\). So \(a \equiv c\). Reflexivity (\(n \mid 0\)) and symmetry (\(n \mid -(a - b)\)) are similarly quick.
Quotient sets
The set of equivalence classes is the quotient set. The integers mod \(n\), written \(\mathbb{Z}_n\), is the quotient of the integers by congruence. Arithmetic on classes is well defined: adding any representatives of \([2]\) and \([4]\) mod 5 always lands in \([1]\).
Applications
Equivalence classes group strings that are anagrams, states of a machine that behave identically (used to minimise automata), and pixels in the same region of an image. Hashing assigns items to buckets, which partitions them by hash value.
Common mistakes
Forgetting to check all three properties. Assuming classes can overlap; they never do. Confusing congruence mod \(n\) with equality of remainders for negative numbers without care: \(-1 \equiv 4 \pmod 5\).
Key takeaways
Equivalence relations are reflexive, symmetric, and transitive, and their classes partition the set. Every partition gives an equivalence relation. Congruence mod \(n\) is the key example, producing \(\mathbb{Z}_n\), with well-defined arithmetic on classes.
Flashcard
Reflexive, symmetric, transitive
Check your understanding
How many equivalence classes does congruence modulo 7 have on the integers?