Discrete Mathematics for Computer Science

Equivalence Relations 183

Example 5.

(a) On R, define x - y if Ix - y I < 0.01. Then, -' is reflexive and symmetric, but it is

not transitive.

(b) On R, the relation GeR is reflexive and transitive, but it is not symmetric.

Solution.

(a) Let x = 0.0, y = 0.0075, and z = 0.015 Then, x -y, because

Ix - Yj = 0.0075 < 0.01

and y -z, because

lY - zj = 0.0075 < 0.01

However, x /- z, since

Ix - zI = 0.015 > 0.01

(b) It is clear that x > x for all x E R and that for all x, y, z E IR, if x > y and y > z,

then x > z, making the relation transitive. Since 5 > 3 but 3? 5, the relation is not

symmetric. Therefore, GeR is reflexive and transitive, but it is not symmetric. M

3.6.1 Partitions

The relation SameSuit (see Table 3.3) is an equivalence relation on the set

SpecialDeck = {10 of Hearts, Jack of Hearts, Queen of Hearts, 10 of Clubs

Jack of Clubs, King of Clubs)

Essentially the same information can be stored in the three sets:

Heart = {10 of Hearts, Jack of Hearts, Queen of Hearts)

Club = { 10 of Clubs, Jack of Clubs, King of Clubs)

Suits = {Heart, Club}

Suits consists of two sets. Each element of SpecialDeck is in exactly one of those sets. The
cards in the first set are exactly the cards in the same suit as the 10 of Hearts. The cards in
the second set are exactly the cards in the same suit as 10 of Clubs.

Definition 3. Let X be a nonempty set. A partition of X is a set Y of nonempty subsets
of X such that every element of X is in exactly one element in Y.

A partition of SpecialDeck is the set Suits. The nonempty sets in Suits are Heart and
Club. We can restate the definition as Theorem 1.

Theorem 1. Let X be a set, and let Y be a set of subsets of X. Then, Y is a partition of X
if and only if:

(a) Each element of Y is a nonempty subset of X,

(b) For any two sets u, v e Y, u n v = 0 unless u = v, and

(c) The union of all the sets in Y is X.