1
Equivalence generalises equality
It is the relation of "the same in some respect": same remainder, same shape, same parity. It keeps equality's three structural properties and drops the demand that the objects be identical.
Lesson · Sets, Relations, and Functions · Relations
Equivalence Relations and Partitions
An equivalence relation is one that behaves like equality in the respects that matter. Every one of them cuts its set into disjoint classes, and every such cutting comes from exactly one equivalence relation.
equivalence = reflexive + symmetric + transitive
[a] = {x : x R a} the class of a
a R b ⟺ [a] = [b] classes are equal or disjoint
equivalence relations on A ⟷ partitions of A (a bijection)
One structure, two descriptions
Core ideas
What this lesson establishes
This is the first theorem on the path that says two apparently different things are the same thing.
2
Classes partition the set
Every element lies in exactly one class. Two classes are either identical or share nothing — there is no partial overlap.
3
The correspondence goes both ways
Every equivalence relation gives a partition; every partition gives an equivalence relation; and the two constructions undo each other.
The material
Classes and partitions
The definition, the theorem, and the proof that the classes fit together.
Definition · Equivalence relation
A relation R on A is an equivalence relation when it is reflexive, symmetric and transitive. It is often written ∼.
Definition · Equivalence class
For a ∈ A, the class of a is [a] = {x ∈ A : x ∼ a}. Any member of a class is called a representative of it.
Definition · Partition
A partition of A is a collection of nonempty, pairwise disjoint subsets whose union is A. Every element of A lies in exactly one block.
Theorem · Classes are equal or disjoint
For an equivalence relation on A and any a, b ∈ A: a ∼ b if and only if [a] = [b]; and if a ≁ b then [a] ∩ [b] = ∅.
Suppose a ∼ b and let x ∈ [a], so x ∼ a. By transitivity x ∼ b, so x ∈ [b]; hence [a] ⊆ [b]. Symmetry of ∼ gives b ∼ a, and the same argument gives [b] ⊆ [a]. So [a] = [b].
Conversely if [a] = [b] then, since a ∈ [a] by reflexivity, a ∈ [b], which means a ∼ b.
Finally suppose x ∈ [a] ∩ [b], so x ∼ a and x ∼ b. By symmetry and transitivity a ∼ b, so by the first part [a] = [b]. Contrapositively, [a] ≠ [b] forces the intersection to be empty.
□
All three properties were needed, and each did a distinct job: reflexivity puts a into its own class, symmetry lets the argument run in both directions, and transitivity is what links two members of the same class to each other.
Theorem · The fundamental correspondence
The equivalence relations on A and the partitions of A are in bijection. An equivalence relation gives the partition into its classes; a partition gives the relation "lies in the same block"; and each construction undoes the other.
Example · Congruence modulo 3
On ℤ, define a ∼ b when 3 | (a − b). It is reflexive (3 | 0), symmetric (3 | (a−b) gives 3 | (b−a)) and transitive (3 | (a−b) and 3 | (b−c) give 3 | (a−c)). The three classes are the integers leaving remainder 0, 1 and 2. Number Theory and Cryptography builds on nothing else.
The utility is that a class can be treated as one object. Arithmetic modulo 3 works because + and × respect the classes: adding any member of [1] to any member of [2] always lands in [0]. That compatibility is not automatic and is exactly what makes modular arithmetic well defined.
Example · A relation that just misses
"|a − b| ≤ 1" on ℤ is reflexive and symmetric but not transitive: 1 ∼ 2 and 2 ∼ 3 but 1 ≁ 3. So it produces no partition — and indeed the "classes" [1] = {0,1,2} and [2] = {1,2,3} overlap without being equal, which is exactly what the theorem forbids.
Interactive
Relation properties
Decided by checking, not by name
Method
Working with an equivalence relation
Verify all three properties, then find the classes.
1
Check reflexivity, symmetry and transitivity
All three, with witnesses. Missing one means there are no classes to find, and any "classes" you write down will overlap.
2
Find the class of one element
Collect everything related to it. That set is a block of the partition.
3
Move to an element not yet placed
Its class is a new block, disjoint from the ones found. Repeat until every element is placed.
4
Check the blocks partition the set
Nonempty, pairwise disjoint, covering everything. If two overlap, one of the three properties failed.
Equivalence
Score 0 / 0Choose the answer you can justify.
The classes of congruence mod 4
On ℤ, a ∼ b when 4 | (a − b).
[0] = {…, −8, −4, 0, 4, 8, …} remainder 0
[1] = {…, −7, −3, 1, 5, 9, …} remainder 1
[2] = {…, −6, −2, 2, 6, 10, …} remainder 2
[3] = {…, −5, −1, 3, 7, 11, …} remainder 3
[4] = [0] — same class, different representative
[−1] = [3]
Four classes, pairwise disjoint, union ℤ. This partition is
written ℤ/4ℤ, and Number Theory and Cryptography does arithmetic in it.
[4] = [0] is the point at which representatives stop mattering. A class has many names and one identity, which is why a definition made through a representative has to be checked for independence of the choice — the well-definedness question Number Theory and Cryptography raises for modular arithmetic.
Common mistakes
1
Calling a relation an equivalence after checking two properties"|a − b| ≤ 1" is reflexive and symmetric and produces overlapping classes. Transitivity is the property that makes the classes fit together.
2
Treating a class as its representative[4] and [0] are the same object modulo 4. A definition that gives different answers for different representatives is not well defined.
3
Forgetting that blocks must be nonemptyA partition has no empty block. It is a small condition and it is what makes the correspondence with equivalence relations exact.
Check your understanding
✓
Finish when you can go from a partition to its relation and back.
Take the partition {{1,4}, {2}, {3,5}} of {1,…,5}, write the relation it induces as a set of pairs, and verify all three properties. Then read the classes back off the relation.
Note: The number of partitions of an n-element set is the Bell number Bₙ: 1, 1, 2, 5, 15, 52, 203. It grows faster than exponentially and has no simple closed form, which is a first sign that counting problems can be hard in ways Combinatorics and Counting makes precise.