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 $$A_1,A_2,...A_n$$ in the following way:

• Basis: Pick an element $$x\in A$$, and let $$A_1$$ be a subset consisting of all elements $$y\in A$$ such that $$yRx$$.
• k-th step: Pick an element z in A such that $$z\notin A_1,...z\notin A_{k-1}$$, and construct a new set $$A_k=\{r\in A\mid rRz\}$$. If there is no such element, we stop.

Prove that $$A_1,A_2,...A_n$$ is a partition of A

Now we show that $$\mathrm{\forall }i\ne j,A_i\cap A_j=\mathrm{\varnothing }$$ and $$A_1\cup A_2\cup ,...\cup A_n=A$$. Since above steps guarantee that every element in A is in at least one of $$A_1,...A_n$$, the second property is trivially true. We’re left to show that each subset is disjoint.

Let $$x\in A_k$$ for some k. (Since we assumed A is not empty, there must be at least one subset). Suppose that $$x\in A_j$$ for some j different from k. (This leads to a contradiction). Since $$\mathrm{\forall }y\in A_k,yRx$$ and $$\mathrm{\forall }z\in A_j,zRx$$ by the definition of subsets, every element in $$A_j$$ is related to every element in $$A_k$$ by R for its reflexivity and transitivity. Now if $$j>k$$, there must be at least one element in $$A_j$$ that is not present in sets $$A_1,A_2,...A_k...A_{j-1}$$ 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, $$x\notin A_j$$ for all j different from k. Hence $$A_1,...A_n$$ are disjoint subsets of A.

We have shown that given an equivalent relation R defined on A, we can construct disjoint subsets $$A_1,A_2,...A_n$$ whose union is A. Q.E.D.