Page 599 - Discrete Mathematics and Its Applications

578 9 / Relations

EXAMPLE 12 Is the “divides” relation on the set of positive integers symmetric? Is it antisymmetric?

Solution: This relation is not symmetric because 1|2, but 2 | 1. It is antisymmetric, for if a
and b are positive integers with a |b and b|a, then a = b (the verification of this is left as an
exercise for the reader). ▲
Let R be the relation consisting of all pairs (x, y) of students at your school, where x has
taken more credits than y. Suppose that x is related to y and y is related to z. This means
that x has taken more credits than y and y has taken more credits than z. We can conclude
that x has taken more credits than z, so that x is related to z. What we have shown is that R has
the transitive property, which is defined as follows.

DEFINITION 5 A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R,
then (a, c) ∈ R, for all a, b, c ∈ A.

Remark: Using quantifiers we see that the relation R on a set A is transitive if we have
∀a∀b∀c(((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R).
EXAMPLE 13 Which of the relations in Example 7 are transitive?

Solution: R 4 , R 5 , and R 6 are transitive. For each of these relations, we can show that it is
transitive by verifying that if (a, b) and (b, c) belong to this relation, then (a, c) also does. For
instance, R 4 is transitive, because (3, 2) and (2, 1), (4, 2) and (2, 1), (4, 3) and (3, 1), and (4, 3)
and (3, 2) are the only such sets of pairs, and (3, 1), (4, 1), and (4, 2) belong to R 4 . The reader
should verify that R 5 and R 6 are transitive.
R 1 is not transitive because (3, 4) and (4, 1) belong to R 1 ,but (3, 1) does not. R 2 is
not transitive because (2, 1) and (1, 2) belong to R 2 ,but (2, 2) does not. R 3 is not transitive
because (4, 1) and (1, 2) belong to R 3 ,but (4, 2) does not. ▲

EXAMPLE 14 Which of the relations in Example 5 are transitive?

Solution:The relations R 1 , R 2 , R 3 , and R 4 are transitive. R 1 is transitive because a ≤ b and b ≤ c
imply that a ≤ c. R 2 is transitive because a> b and b> c imply that a> c. R 3 is transitive
because a =±b and b =±c imply that a =±c. R 4 is clearly transitive, as the reader should
verify. R 5 is not transitive because (2, 1) and (1, 0) belong to R 5 ,but (2, 0) does not. R 6 is not
transitive because (2, 1) and (1, 2) belong to R 6 ,but (2, 2) does not. ▲

EXAMPLE 15 Is the “divides” relation on the set of positive integers transitive?

Solution: Suppose that a divides b and b divides c. Then there are positive integers k and l
such that b = ak and c = bl. Hence, c = a(kl),so a divides c. It follows that this relation is
transitive. ▲
We can use counting techniques to determine the number of relations with specific proper-
ties. Finding the number of relations with a particular property provides information about how
common this property is in the set of all relations on a set with n elements.
EXAMPLE 16 How many reflexive relations are there on a set with n elements?

Solution: A relation R on a set A is a subset of A × A. Consequently, a relation is determined
2
by specifying whether each of the n ordered pairs in A × A is in R. However, if R is reflexive,
each of the n ordered pairs (a, a) for a ∈ A must be in R. Each of the other n(n − 1) ordered