Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.3 EQUIVALENCE CLASSES AND PARTITIONS 243

Additional properties of equivalence classes may be found in Exercise 4.
Consider the equivalence relation on A = (1,2,3,4,5) given by E =
{(I, I), (2, a, (3, 3)7 (4,4), (5, 5), (1, 31, (3, 11, (1, 4)7 (4, 11, (3, 41, (4,319 (2,5),
(5,2)). Since [I] = [3] = [4] = (1,3,4) and [2] = [5] = (2, 51, the set of
equivalence classes (which is necessarily a partition of A, by Theorem 2)
equals ((1,3,4), (2,511. Suppose now we apply Theorem 1 to A/E and
compute the corresponding equivalence relation A/(A/E). The result, which
you may easily verify, is precisely the original equivalence relation E. On
the other hand, suppose we start with a partition '$ = ((11, (2,3), (41, (5))
of the same A. We calculate easily that A/'$ = ((1, I), (2,2), (3, 3), (4,4),
(5,5), (2, 3), (3,2)]. Then since [I] = (I), [2] = [3] = {2,3), [4] = {4), and
[5] = (51, we conclude that A/(A/(IP) = ((I), (2,3), (41, (5)) = '$.
The upshot of the two preceding examples is that the two canonical pro-
cesses by which we go from equivalence relation E to partition A/E (AIE
is the set of equivalence classes generated by E) and from partition '$ to
equivalence relation A/!@ (two elements of A are related by A/'$ if and only
if they are contained in some cell of (IP) are inverse processes. This means
that by carrying out these two processes consecutively, we proceed either
E -, (AIE) -, E or (IP + (A/'$) 4 '$. The next theorem formalizes these
facts.

THEOREM 3

(a) Let E be an equivalence relation on a set A. Then A/(A/E) = E.

(b) Let '@ be a partition of a set A. Then A/(A/q3) = 13.

Proof We prove (a), leaving (b) as Exercise 5. We must show A/(A/E) G E

and E c_ A/(A/E). Since E is an equivalence relation on A, then A/E is

a partition of A (by Theorem 2) and so A/(A/E) is an equivalence relation

on A (by Theorem 1). Let (x, y) E A/(A/E). Then there exists a cell X of

the partition A/E such that x E X and y E X. But the cells of A/E are

precisely the equivalence classes generated by E. Since X is therefore an

equivalence class generated by E and since X contains both x and y, it

follows from Exercise 4 that [x] = X = [y] so that x E y or (x, y) E E, as

desired. Thus A/(A/E) c E.

Conversely, suppose (x, y) E E. To show (x, y) E A/(A/E), we must

prove that there exists a cell X of the partition A/E that contains both

x and y. Now since x E y, then [x] = [y], by Exercise 4(c). Letting

X = [x] (= [y]), we note that X is a cell of A/E and contains both x

and y, as desired. Hence (x, y) E A/(A/E) and E r A/(A/E), as we wished

to prove.

You may have already discovered (using Exercise 10, Article 7.2) that

the set of equivalence classes corresponding to the equivalence relation -= ,

on Z looks like ((... , -15, -10, -5,0, 5, 10, 15,.. .), (... , -14, -9,

-4, 1,6,11,16,...], { ..., -13, -8, -3,2,7,12,17 ,... ], {..., -12,