# 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

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

### Prove that ${A}_{1},{A}_{2},...{A}_{n}$ is a partition of A #

Now we show that

Let

We have shown that given an equivalent relation R defined on A,
we can construct disjoint subsets