So I was reading CS172 textbook chapter 0, and came across the equivalence relations. Equivalence relations, my favorite topic! But I almost forgot most of it since I reviewed my discrete math book briefly over the summer, and started to wonder why is that the equivalence relations defines a partition. So I started looking over my discrete math book. Well, there was no proof about why equivalence relations defines a partition, so here’s my (attempted) proof.
Let A be any finite set (I would let you figure out for infinite set), R be an equivalence relation defined on A; hence R is reflective, symmetric, and transitive.
The statement is trivially true if A is empty because any relation defined on A defines the trivial empty partition of A. Thus, we assume that A is not empty.
We construct non-empty subsets in the following way:
- Basis: Pick an element , and let be a subset consisting of all elements such that .
- k-th step: Pick an element z in A such that , and construct a new set . If there is no such element, we stop.
Prove that is a partition of A
Now we show that and . Since above steps guarantee that every element in A is in at least one of , the second property is trivially true. We’re left to show that each subset is disjoint.
Let for some k. (Since we assumed A is not empty, there must be at least one subset). Suppose that for some j different from k. (This leads to a contradiction). Since and by the definition of subsets, every element in is related to every element in by R for its reflexivity and transitivity. Now if , there must be at least one element in that is not present in sets because j-th step picks an element in A that has not been picked in the previous steps. But this is a contradiction. A similar argument holds when . Thus, for all j different from k. Hence are disjoint subsets of A.
We have shown that given an equivalent relation R defined on A, we can construct disjoint subsets whose union is A. Q.E.D.