Skip to main content

Proof: An Equivalence Relation Defines A Partition

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.

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 A1,A2,...An in the following way:

Prove that A1,A2,...An is a partition of A #

Now we show that ij,AiAj= and A1A2,...An=A. Since above steps guarantee that every element in A is in at least one of A1,...An, the second property is trivially true. We're left to show that each subset is disjoint.

Let xAk for some k. (Since we assumed A is not empty, there must be at least one subset). Suppose that xAj for some j different from k. (This leads to a contradiction). Since yAk,yRx and zAj,zRx by the definition of subsets, every element in Aj is related to every element in Ak by R for its reflexivity and transitivity. Now if j>k, there must be at least one element in Aj that is not present in sets A1,A2,...Ak...Aj1 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 j<k. Thus, xAj for all j different from k. Hence A1,...An are disjoint subsets of A.

We have shown that given an equivalent relation R defined on A, we can construct disjoint subsets A1,A2,...An whose union is A. Q.E.D.