Today we’ll take a brief break from group theory to prove a fact about equivalence relations, namely, that they are the same as partitions. A partition is a pretty intuitive concept: you take a big set, and cut it up into smaller sets so that every element of the big set belongs to exactly one of the small sets. That is, no elements are left out, and none of the small sets overlap with each other at all.
More formally, a partition of a set is a finite collection of nonempty sets such that
- The union of all the is the original set: .
- The do not overlap, i.e. they are pairwise disjoint: if then .
So how does this relate to equivalence relations? Suppose we have a set and an equivalence relation on . Then the equivalence class of an element is defined as the set of all elements which are equivalent to . We write
to denote the equivalence class of . It turns out that if is an equivalence relation, the equivalence classes form a partition of . Intuitively, each equivalence class consists of a bunch of things which are all equivalent to each other, and these necessarily include everything (since everything is at least equivalent to itself) and don’t overlap (because if two equivalence classes did overlap, they would collapse into one big class due to transitivity). Let’s prove it.
- First we’ll prove a small lemma: if then . As is usual, to prove two sets are equal, we’ll prove that each is a subset of the other. First, suppose is any element in . Then by definition . By symmetry, , and then by transitivity (since we assumed ), . By symmetry again , so by definition . So every element of is also an element of . An entirely analogous argument shows that is a subset of as well. Thus .
- Now we can prove that the set of distinct equivalence classes forms a partition of . First, every is at the very least included in its own equivalence class , which must contain since by reflexivity. So the equivalence classes don’t miss any elements, that is, the union of all the equivalence classes is the entire set .
- We also have to prove that distinct equivalence classes don’t overlap. Let and be two different equivalence classes. We want to show they have no elements in common. Suppose, on the contrary, that there is some which is in both and . Then by definition and . So by symmetry , and then by transitivity . By our lemma above, this means , contradicting our assumption that they are different.