Page 596 - Discrete Mathematics and Its Applications

9.1 Relations and Their Properties 575

Relations on a Set

Relations from a set A to itself are of special interest.

DEFINITION 2 A relation on a set A is a relation from A to A.

In other words, a relation on a set A is a subset of A × A.

EXAMPLE 4 Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R ={(a, b) | a divides b}?

Solution: Because (a, b) is in R if and only if a and b are positive integers not exceeding 4 such
that a divides b, we see that

R ={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

The pairs in this relation are displayed both graphically and in tabular form in Figure 2. ▲

Next, some examples of relations on the set of integers will be given in Example 5.

EXAMPLE 5 Consider these relations on the set of integers:

R 1 ={(a, b) | a ≤ b},
R 2 ={(a, b) | a> b},
R 3 ={(a, b) | a = b or a =−b},
R 4 ={(a, b) | a = b},
R 5 ={(a, b) | a = b + 1},
R 6 ={(a, b) | a + b ≤ 3}.

Which of these relations contain each of the pairs (1, 1), (1, 2), (2, 1), (1, −1), and (2, 2)?

Remark: Unlike the relations in Examples 1–4, these are relations on an infinite set.
Solution: The pair (1, 1) is in R 1 , R 3 , R 4 , and R 6 ; (1, 2) is in R 1 and R 6 ; (2, 1) is in R 2 , R 5 ,
and R 6 ; (1, −1) is in R 2 , R 3 , and R 6 ; and finally, (2, 2) is in R 1 , R 3 , and R 4 . ▲

It is not hard to determine the number of relations on a finite set, because a relation on a
set A is simply a subset of A × A.

1 1 R 1 2 3 4
1
2 2
2
3
3 3
4

4 4
FIGURE 2 Displaying the Ordered Pairs in
the Relation R from Example 4.