(
Equivalence Relations and Partitions) Let S be a nonempty set and let ~ be an equivalence relation on S. Then ~ yields a partition of S, where
= {x
S | x ~ a}. Also, each partition of S gives rise to an equivalence relation ~ on S where a ~ b if and only if a and b are in the same cell of the partition.
We must show that the different cells
= {x
S | x ~ a} for a
S do give a partition of S, so that every element of S is in some cell and so that if a
, then
=
. Let a
S. Then a
by the reflexive condition, so a is in at least one cell. Suppose now that a were in a cell
also. We need to show that
=
as sets; this will show that a cannot be in more than one cell. There is a standard way to show that two sets are the same: Show that each set is a subset of the other. We show that
. Let x
. Then x ~ a. But a
, so a ~ b. Then, by the transitive condition, x ~ b, so x
. Thus
. Now we show that
. Let y
B. Then y ~ b. But a
, so a ~ b and by symmetry b ~ a. Then by transitivity y ~ a, so y
. Hence
also, so
=
and our proof is complete.