Discrete Mathematics for Computer Science

184 CHAPTER 3 Relations

Definition 4. Let -be an equivalence relation on a set X. For any x e X, let

[x] = {y •X :x -y}

[x ] is called the equivalence class of x.

In the example with the set SpecialDeck and equivalence relation SameSuit, we have

Heart = [10 of Hearts] = [Jack of Hearts] = [Queen of Hearts]

and

Club = [10 of Clubs] = [Jack of Clubs] = [King of Clubs]

The set Suits stores essentially the same information as the relation SameSuit. The next

two theorems make this statement precise.

Theorem 2. Let -'- be an equivalence relation on a set X. Then:

(a) Foranyx E X,x E [x].

(b) For any x, y E X, either [x] = [y ] or [ x ]and[ y ] are disjoint.

(c) {[x[ :x E X} is a partition of X.

(d) Forx, y E X,x yifandonlyify E [x].

Proof. (a) Since - is reflexive, x - x, so x E [ x].

(b) Suppose [ x ] and [ y ] are not disjoint, and prove [x [ y ] by showing that [ x ] _

[y] and [y] [x]. To prove that [x] [y], assume that r E [x], and show that

r E [ y ]-that is, that y - r.

Since [x]f[y] :0, thereis az E [x]n[y]. Thusx -z, andy -z. Since --is

symmetric, z - x. By the transitivity of --, since y - z and z - x, y - x. Now since

y '-' x and x - r, y - r. So, r E [ y ], as required. Therefore, [x] [ y].

Analogously, [y] g [xl, so [y] = [x].

(c) It must be shown that {I x ] : x E X} is a set of nonempty subsets of X such that each

y E X is in exactly one [x]. To check that the [x]'s are nonempty, observe that x E [ x ].

To check that each y E X is in at least one [ x], observe that y c [y ]. To check that

each y E X is in at most one [x ], suppose y E [xl ] and y E I[x2]. Then, by part (b)

[Xl ] = [x2 ]. The classes are the same, so y is in only one equivalence class.

(d) This is immediate from the definition of equivalence classes. U

Theorem 2 says two things. First, given an equivalence relation on a set X, its set

of distinct equivalence classes form a partition of X. Second, the relation that defines two

elements to be related if they are in the same element of the partition is equal to the original

relation (part (d)).

Example 6. Let Deck = 110 of Hearts, King of Hearts, Queen of Clubs, Ace of Clubs}.

The relation SameSuit defined on Deck consists of the following ordered pairs:

(10 of Hearts, King of Hearts) (King of Hearts,^10 of Hearts)

(10 of Hearts, 10 of Hearts) (King of Hearts, King of Hearts)

(Queen of Clubs, Ace of Clubs) (Ace of Clubs, Queen of Clubs)

(Queen of Clubs, Queen of Clubs) (Ace of Clubs, Ace of Clubs)

Find the equivalence classes of this relation. Also, find the partition determined by this

equivalence relation.