Discrete Mathematics for Computer Science

186 CHAPTER 3 Relations

Proof

(a) First, prove that - is an equivalence relation.

Reflexive: Let x c X, and show that x - x. Since P is a partition, x is in some set

Q E P. So, x and x are both in Q; therefore, x - x.

Symmetric: Let x, y E X, and assume that x -y. That means there is a set Q E P such

that x, y E Q. So, y and x are in Q. Therefore, y - x.

Transitive: Suppose x - y and y - z. Since x -y, there is a set Q E P such that x,y E

Q. Since y -z, z is in the same set in P as y, so z E Q. Therefore, x and z are both in Q,

giving x -z.

(b)

[x] = {y E X x yJ

= {x E X x, y are both in the same element of P}

= element of P to which x belongs^0

Example 9. Let Deck = { 10 of Hearts, King of Hearts, Queen of Clubs, Ace of Clubs).

The set

P = {{10 of Hearts, King of Hearts), {Queen of Clubs, Ace of Clubs))

is a partition of Deck. Define a relation '-- on Deck such that for x, y E Deck, x - y if and

only if x and y are in the same element of P. The elements of the relation are

(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)

By Theorem 3 in this section, this relation is an equivalence relation for which the distinct

equivalence classes are precisely the elements of P. U

3.6.2 Comparing Equivalence Relations

Consider a standard deck of 52 cards, called 52Cards. The suits are traditionally marked in

two colors: Clubs and Spades are black; Diamonds and Hearts are red. The relation Same-

Suit, consisting of all pairs of cards that are in the same suit, and the relation SameColor

consisting of all pairs of cards that are the same color, are both equivalence relations. The

equivalence class of the 2 of Diamonds in SameSuit is

[2 of Diamonds] = {2 of Diamonds, 3 of Diamonds .... Ace of DiamondsI

The equivalence class of the 2 of Diamonds in SameColor contains all the Diamonds and

all the Hearts. Figure 3.9, on page 187, is a Venn diagram showing the equivalence classes

of the two relations.

Each equivalence class of SameSuit is contained within a single equivalence class of

SameColor.

Definition 5. Let R 1 and R2 be equivalence relations on a set X. R 1 refines R 2 if, for

each x e X, the equivalence class of x in R 1 is a subset of the equivalence class of x in R 2.