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 ${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}=\left\{r\in A\mid rRz\right\}$. 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. 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.