Page 621 - Discrete Mathematics and Its Applications

600 9 / Relations

The term path also applies to relations. Carrying over the definition from directed graphs to
relations, there is a path from a to b in R if there is a sequence of elements a, x 1 ,x 2 ,...,x n−1 ,b
with (a, x 1 ) ∈ R, (x 1 ,x 2 ) ∈ R,..., and (x n−1 ,b) ∈ R. Theorem 1 can be obtained from the
definition of a path in a relation.

THEOREM 1 Let R be a relation on a set A. There is a path of length n, where n is a positive integer, from
n
a to b if and only if (a, b) ∈ R .

Proof: We will use mathematical induction. By definition, there is a path from a to b of length
one if and only if (a, b) ∈ R, so the theorem is true when n = 1.
Assume that the theorem is true for the positive integer n. This is the inductive hypothesis.
There is a path of length n + 1 from a to b if and only if there is an element c ∈ A such that
there is a path of length one from a to c,so (a, c) ∈ R, and a path of length n from c to b,
n
that is, (c, b) ∈ R . Consequently, by the inductive hypothesis, there is a path of length n + 1
n
from a to b if and only if there is an element c with (a, c) ∈ R and (c, b) ∈ R . But there
is such an element if and only if (a, b) ∈ R n+1 . Therefore, there is a path of length n + 1
from a to b if and only if (a, b) ∈ R n+1 . This completes the proof.

Transitive Closures

We now show that finding the transitive closure of a relation is equivalent to determining which
pairs of vertices in the associated directed graph are connected by a path. With this in mind, we
define a new relation.

DEFINITION 2 Let R be a relation on a set A. The connectivity relation R consists of the pairs (a, b) such
∗
that there is a path of length at least one from a to b in R.

n
Because R consists of the pairs (a, b) such that there is a path of length n from a to b, it follows
n
∗
that R is the union of all the sets R . In other words,
∞

∗ n
R = R .
n=1
The connectivity relation is useful in many models.
EXAMPLE 4 Let R be the relation on the set of all people in the world that contains (a, b) if a has met b.
n
∗
What is R , where n is a positive integer greater than one? What is R ?
2
Solution:The relation R contains (a, b) if there is a person c such that (a, c) ∈ R and (c, b) ∈ R,
n
that is, if there is a person c such that a has met c and c has met b. Similarly, R consists of
those pairs (a, b) such that there are people x 1 ,x 2 ,...,x n−1 such that a has met x 1 ,x 1 has
met x 2 ,..., and x n−1 has met b.
∗
The relation R contains (a, b) if there is a sequence of people, starting with a and ending
with b, such that each person in the sequence has met the next person in the sequence. (There
are many interesting conjectures about R . Do you think that this connectivity relation includes
∗
the pair with you as the first element and the president of Mongolia as the second element? We
will use graphs to model this application in Chapter 10.) ▲