Equivalence Relations Induce Partitions
You'll learn: How every equivalence relation on a set automatically creates a partition of that set into disjoint equivalence classes.
The Core Connection
We've seen that equivalence relations produce equivalence classes, and separately that partitions divide sets into non-overlapping pieces. Now comes the beautiful theorem: these are the same thing. Every equivalence relation naturally creates a partition.
Why This Works
Given an equivalence relation ~ on set S, the collection of all equivalence classes forms a partition because:
- Every element is in some class: Each element a belongs to [a], its own equivalence class
- Classes are either identical or disjoint: If [a] and [b] overlap at any element, they must be the same class (because transitivity forces all their elements to be related)
- Classes cover the whole set: The union of all equivalence classes equals S
Think of it like sorting a deck of cards by suit. The "same suit" relation is an equivalence relation, and it automatically partitions the deck into four piles (hearts, diamonds, clubs, spades). No card appears in two piles, every card is in exactly one pile, and together the piles reconstruct the full deck.
The Proof Sketch
To prove classes are disjoint or identical: suppose x ∈ [a] ∩ [b]. Then a ~ x and b ~ x. By symmetry, x ~ b. By transitivity, a ~ b. This means every element related to a is also related to b, so [a] = [b].
The converse is also true: any partition defines an equivalence relation where elements are related if and only if they're in the same partition block.
Key Takeaway: Equivalence relations and partitions are two sides of the same coin—every equivalence relation induces a partition into equivalence classes, and conversely, every partition defines an equivalence relation.