Page 597 - Discrete Mathematics and Its Applications

576 9 / Relations

EXAMPLE 6 How many relations are there on a set with n elements?

2
Solution: A relation on a set A is a subset of A × A. Because A × A has n elements when A
2
m
has n elements, and a set with m elements has 2 subsets, there are 2 n subsets of A × A. Thus,
9
there are 2 n 2 relations on a set with n elements. For example, there are 2 3 2 = 2 = 512 relations
on the set {a, b, c}. ▲

Properties of Relations

There are several properties that are used to classify relations on a set. We will introduce the
most important of these here.
In some relations an element is always related to itself. For instance, let R be the relation
on the set of all people consisting of pairs (x, y) where x and y have the same mother and the
same father. Then xRx for every person x.

DEFINITION 3 A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A.

Remark: Using quantifiers we see that the relation R on the set A is reflexive if ∀a((a, a) ∈ R),
where the universe of discourse is the set of all elements in A.

We see that a relation on A is reflexive if every element of A is related to itself.
Examples 7–9 illustrate the concept of a reflexive relation.
EXAMPLE 7 Consider the following relations on {1, 2, 3, 4}:

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

Which of these relations are reflexive?

Solution: The relations R 3 and R 5 are reflexive because they both contain all pairs of the form
(a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4). The other relations are not reflexive because
they do not contain all of these ordered pairs. In particular, R 1 , R 2 , R 4 , and R 6 are not reflexive
because (3, 3) is not in any of these relations. ▲

EXAMPLE 8 Which of the relations from Example 5 are reflexive?

Solution: The reflexive relations from Example 5 are R 1 (because a ≤ a for every integer a),
R 3 , and R 4 . For each of the other relations in this example it is easy to find a pair of the
form (a, a) that is not in the relation. (This is left as an exercise for the reader.) ▲

EXAMPLE 9 Is the “divides” relation on the set of positive integers reflexive?

Solution: Because a | a whenever a is a positive integer, the “divides” relation is reflexive. (Note
that if we replace the set of positive integers with the set of all integers the relation is not reflexive
because by definition 0 does not divide 0.) ▲