242 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7
We have just seen that any partition of a set A leads automatically to
a corresponding equivalence relation on A. A perhaps more surprising fact
is that any equivalence relation on a set leads to a corresponding partition,
whose cells are precisely the equivalence classes. [This fact, although pos-
sibly not predicted, should not be entirely unanticipated; recall Example
5(b) of the preceding article.] A first step toward this result is provided in
the following lemma.
LEMMA
Let -- be an equivalence relation on a nonempty set A. For each XE A, let
[x] = (y E A 1 x y), the equivalence class of x. Then:
(a) [x] # 0 for each XE A
(6) If x, y~ A, then either [x] = [y] or [x] n [y] = 0
(c) u([x]IxEA)=AProof (a) Given x E A, we note that x - x, since - is reflexive. Hence
x E [XI, which is thereby nonempty.
(b) This is the most interesting result of the three and hardest to
prove. It asserts that two equivalence classes generated by an equiva-
lence relation are either identical or disjoint. To conclude "either [x] =
[y] or [XI n [y] = a," we recall the approach of Article 6.2 (particu-
larly Examples 1 and 2); assume the negation of one of these conclu-
sions and try to derive the other. Specifically, suppose [x] n [y] # QI,
so that there exists z E [XI n [y]. We claim [x] = [y]; we will prove
this by proving mutual inclusion. To show [x] G [y], suppose w E [x].
To conclude w E [y], we must prove y - w. Now since z E [x], we have
x - z. Since z E [y] and w E [x], we have y - z and x - w, respectively.
How can we piece together the three known equivalences to arrive at
the desired one? We have y - z, x - z, and x - w; we want y - w. Note
first that since x - z, then by symmetry, z - x. Then since y - z and
z - x, we have y - x by transitivity. Finally, since y - x and x - w, we
have, by transitivity, y - w, our desired result. Hence [x] c [y]. The
reverse inclusion follows by an identical argument.
(c) Clearly u ([x] tx E A) G A, since each equivalence class [XI is a
subset of A. Conversely, if y E A, then y E [y], as noted in (a), so that
y E [XI for some x E A and therefore y E u ([x] lx E A), as desired.
Comparison of (a), (b), and (c) of Lemma 1 with requirements (i), (ii),
and (iii) of Definition 1, leads immediately to the following theorem.
THEOREM 2
Let E be an equivalence relation on a set A. Then the collection A/E = ([x] Ix E A}
of equivalence classes generated by E is a partition of A.