Discrete Mathematics for Computer Science

Equivalence Relations 185

Solution. The equivalence classes are

[10 of Hearts] = {10 of Hearts, King of Hearts)

[King of Hearts] = {10 of Hearts, King of Hearts)

[Queen of Clubs] = {Queen of Clubs, Ace of Clubs)

[Ace of Clubs] = {Queen of Clubs, Ace of Clubs)

The distinct equivalence classes are the two sets

I 10 of Hearts, King of Hearts) {Queen of Clubs, Ace of Clubs)

which form a partition of Deck U

Example 7. Recall the equivalence relation = (mod p) of Example 3 in Section 3.6. The

following are the equivalence classes of = (mod 5):

[0] = {0, 5, 10, 15, 20, 25, 30 .... I

[1] = {1, 6, 11, 16, 21, 26, 31 ,....

[2] = {2, 7, 12, 17, 22, 27, 32 .... I

[3] = {3, 8, 13, 18, 23, 28, 33, ....

[4] = {4, 9, 14, 19, 24, 29, 34 .... I

The reader should prove that these are the equivalence classes. U

In Example 8 we determine all the equivalence classes of - (mod p) for any positive
integer p.

Example 8. Let p be a positive integer. Determine the equivalence classes of = (mod p).

Solution. We know from Example 3 in Section 3.6 that every integer is congruent to its
remainder (mod p). Since the only possible remainders are 0, 1. p - 1, we have

N C [0] U [1] U... U [p- 1]

Thus, there are, at most, p equivalence classes-namely, [0], [1]. [p - 1]. We must
show that these equivalence classes are all different.
Let rl and r2 be two different remainders, such as 0 < rl < r2 _< p - 1. We must
show that [rl] # [r2]. Note that r2 - r, is a positive integer less that p so that r2 - rl
is not divisible by p. Then, rl # r2 (mod p), whence [rl] A [r2]. Therefore, the distinct
equivalence classes are [0], [1] .... [p - 1]. M

Theorem 2 says that one can go from an equivalence relation to a partition from, which
one may read off the equivalence relation. Theorem 3 says that one can go from a partition
to an equivalence relation, from which one may read off the partition.

Theorem 3. Let P be a partition of a set X. For x, y E X, define x - y to mean that x
and y are in the same element of the partition. Then:

(a) -is an equivalence relation.
(b) The equivalence classes of - are exactly the elements of P.