Discrete Mathematics for Computer Science

Binary Relations 159

Definition 1. A binary relation is a set of ordered pairs. A binary relation on a set X is

a set of ordered pairs of elements of X.

Example 1. The relation HigherValue defined in Table 3.2 can be represented as the

following set of ordered pairs:

{(Jack of Hearts, 10 of Hearts), (Queen of Hearts, 10 of Hearts), (Jack of Clubs,

10 of Hearts), (King of Clubs, 10 of Hearts), (Queen of Hearts, Jack of Hearts),

(King of Clubs, Jack of Hearts), (King of Clubs, Queen of Hearts), (Jack of Hearts,

10 of Clubs), (Queen of Hearts, 10 of Clubs), (Jack of Clubs, 10 of Clubs),

(King of Clubs, 10 of Clubs), (Queen of Hearts, Jack of Clubs),

(King of Clubs, Jack of Clubs))

A second important binary relation on SpecialDeck is SameSuit, which is defined as

(a, b) e SameSuit if a and b are cards in SpecialDeck that belong to the same suit. For

example, both the ordered pair (10 of Hearts, Jack of Hearts) and the ordered pair (Jack of

Hearts, 10 of Hearts) are in SameSuit, but the ordered pair (10 of Hearts, Jack of Clubs) is

not. The pairs in the relation SameSuit for SpecialDeck are listed in Table 3.3.

Table 3.3 SameSuit Relation

SameSuit

10 of Hearts 10 of Hearts 10 of Clubs 10 of Clubs

10 of Hearts Jack of Hearts 10 of Clubs Jack of Clubs

10 of Hearts Queen of Hearts 10 of Clubs King of Clubs

Jack of Hearts 10 of Hearts Jack of Clubs 10 of Clubs

Jack of Hearts Jack of Hearts Jack of Clubs Jack of Clubs

Jack of Hearts Queen of Hearts Jack of Clubs King of Clubs

Queen of Hearts 10 of Hearts King of Clubs 10 of Clubs

Queen of Hearts Jack of Hearts King of Clubs Jack of Clubs

Queen of Hearts Queen of Hearts King of Clubs King of Clubs

A third relation defined on SpecialDeck is that of having a higher value and being
in the same suit. This relation is shown in Table 3.4. Here, an ordered pair (a, b) of cards
belongs to the relation HigherValueSameSuit if cards a and b in SpecialDeck have the same
suit and furthermore, card a has a higher value than card b.

Table 3.4 HigherValueSameSuit

Relation

HigherValueSameSuit

Jack of Hearts 10 of Hearts

Queen of Hearts 10 of Hearts

Queen of Hearts Jack of Hearts

Jack of Clubs 10 of Clubs

King of Clubs 10 of Clubs

King of Clubs Jack of Clubs