# 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}=\{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.