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 be a subset consisting of all elements such that . - k-th step: Pick an element z in A such that
, and construct a new set . If there is no such element, we stop.
Prove that 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