Page 601 - Discrete Mathematics and Its Applications

580 9 / Relations

DEFINITION 6 Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite
of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for
which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S. We denote the
composite of R and S by S ◦R.

Computing the composite of two relations requires that we find elements that are the second
element of ordered pairs in the first relation and the first element of ordered pairs in the second
relation, as Examples 20 and 21 illustrate.

EXAMPLE 20 What is the composite of the relations R and S, where R is the relation from {1, 2, 3} to {1, 2, 3, 4}
with R ={(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2}
with S ={(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}?

Solution: S ◦R is constructed using all ordered pairs in R and ordered pairs in S, where the
second element of the ordered pair in R agrees with the first element of the ordered pair
in S. For example, the ordered pairs (2, 3) in R and (3, 1) in S produce the ordered pair (2, 1)
in S ◦R. Computing all the ordered pairs in the composite, we find

S ◦ R ={(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}. ▲

EXAMPLE 21 Composing the Parent Relation with Itself Let R be the relation on the set of all people
such that (a, b) ∈ R if person a is a parent of person b. Then (a, c) ∈ R ◦R if and only if there
is a person b such that (a, b) ∈ R and (b, c) ∈ R, that is, if and only if there is a person b such
that a is a parent of b and b is a parent of c. In other words, (a, c) ∈ R ◦R if and only if a is a
grandparent of c. ▲

The powers of a relation R can be recursively defined from the definition of a composite of
two relations.

n
DEFINITION 7 Let R be a relation on the set A. The powers R ,n = 1, 2, 3,..., are defined recursively by
1
n
R = R and R n+1 = R ◦ R.
2
3
2
The definition shows that R = R ◦ R, R = R ◦ R = (R ◦ R)◦ R, and so on.
n
EXAMPLE 22 Let R ={(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers R ,n = 2, 3, 4,....
2
2
Solution: Because R = R ◦R, we find that R ={(1, 1), (2, 1), (3, 1), (4, 2)}. Further-
3
2
3
more, because R = R ◦R, R ={(1, 1), (2, 1), (3, 1), (4, 1)}.Additional computation shows
4
4
3
n
that R is the same as R ,so R ={(1, 1), (2, 1), (3, 1), (4, 1)}. It also follows that R = R 3
for n = 5, 6, 7,.... The reader should verify this. ▲
The following theorem shows that the powers of a transitive relation are subsets of this
relation. It will be used in Section 9.4.
n
THEOREM 1 The relation R on a set A is transitive if and only if R ⊆ R for n = 1, 2, 3,....