Page 619 - Discrete Mathematics and Its Applications

598 9 / Relations

of R with respect to P. (Note that the closure of a relation with respect to a property may not
exist; see Exercises 15 and 35.) We will show how reflexive, symmetric, and transitive closures
of relations can be found.

Closures

The relation R ={(1, 1), (1, 2), (2, 1), (3, 2)} on the set A ={1, 2, 3} is not reflexive. How can
we produce a reflexive relation containing R that is as small as possible? This can be done by
adding (2, 2) and (3, 3) to R, because these are the only pairs of the form (a, a) that are not in R.
Clearly, this new relation contains R. Furthermore, any reflexive relation that contains R must
also contain (2, 2) and (3, 3). Because this relation contains R, is reflexive, and is contained
within every reflexive relation that contains R, it is called the reflexive closure of R.
As this example illustrates, given a relation R on a set A, the reflexive closure of R can be
formed by adding to R all pairs of the form (a, a) with a ∈ A, not already in R. The addition
of these pairs produces a new relation that is reflexive, contains R, and is contained within any
reflexive relation containing R. We see that the reflexive closure of R equals R ∪ , where
={(a, a) | a ∈ A} is the diagonal relation on A. (The reader should verify this.)

EXAMPLE 1 What is the reflexive closure of the relation R ={(a, b) | a< b} on the set of integers?

Solution: The reflexive closure of R is

R ∪ ={(a, b) | a< b}∪{(a, a) | a ∈ Z}={(a, b) | a ≤ b}. ▲

The relation {(1, 1), (1, 2), (2, 2), (2, 3), (3, 1), (3, 2)} on {1, 2, 3} is not symmetric. How
can we produce a symmetric relation that is as small as possible and contains R? To do this,
we need only add (2, 1) and (1, 3), because these are the only pairs of the form (b, a) with
(a, b) ∈ R that are not in R. This new relation is symmetric and contains R. Furthermore, any
symmetric relation that contains R must contain this new relation, because a symmetric relation
that contains R must contain (2, 1) and (1, 3). Consequently, this new relation is called the
symmetric closure of R.
As this example illustrates, the symmetric closure of a relation R can be constructed by
adding all ordered pairs of the form (b, a), where (a, b) is in the relation, that are not al-
ready present in R. Adding these pairs produces a relation that is symmetric, that contains R,
and that is contained in any symmetric relation that contains R. The symmetric closure of a
relation can be constructed by taking the union of a relation with its inverse (defined in the
preamble of Exercise 26 in Section 9.1); that is, R ∪ R −1 is the symmetric closure of R, where
R −1 ={(b, a) | (a, b) ∈ R}. The reader should verify this statement.
EXAMPLE 2 What is the symmetric closure of the relation R ={(a, b) | a> b} on the set of positive integers?

Solution: The symmetric closure of R is the relation

−1
R ∪ R ={(a, b) | a> b}∪{(b, a) | a> b}={(a, b) | a = b}.
This last equality follows because R contains all ordered pairs of positive integers where the
first element is greater than the second element and R −1 contains all ordered pairs of positive
integers where the first element is less than the second. ▲

Suppose that a relation R is not transitive. How can we produce a transitive relation that
contains R such that this new relation is contained within any transitive relation that con-
tains R? Can the transitive closure of a relation R be produced by adding all the pairs of
the form (a, c), where (a, b) and (b, c) are already in the relation? Consider the relation