Section 5.1 Relations
335
This relation is reflexive and contains r. Furthermore, any reflexive relation on S
would have to contain the new ordered pairs we’ve added—(2, 2) and (3, 3)—so
no smaller reflexive relation can exist; that is, any reflexive relation containing r
must have the relation above as a subset.
The closure of r with respect to symmetry is
r* = 5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)6
Here it is also clear that we have added just those new pairs required—(2, 1) and
(3, 2)—for the relation to be symmetric.
For both reflexive closure and symmetric closure, we only had to inspect the
ordered pairs already in r to find out what ordered pairs we needed to add (assuming we knew what the set S was). The reflexive or symmetric closure of the relation could be found in one step. Transitive closure may require a series of steps.
Inspecting the ordered pairs in our example r, we see that we need to add (3, 2)
(because of (3, 1) and (1, 2)), (3, 3) (because of (3, 1) and (1, 3)), and (2, 1) (because of (2, 3) and (3, 1)). This gives the relation
5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)6
However, this relation is still not transitive. Because of the new pair (2, 1) and the
old pair (1, 2), we need to add (2, 2). This gives the relation
5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)6
which is transitive and also the smallest transitive relation containing r. It is the
transitive closure of r.
As in Example 9, one way to find the transitive closure of a relation is to inspect
the ordered pairs in the original relation, add new pairs if necessary, inspect the
resulting relation, add new pairs if necessary, and so on, until a transitive relation is
achieved. This is a rather ad hoc procedure, and we will give a better algorithm in
Chapter 7. There we will also see that the transitive closure of a binary relation is
related to “reachability in a directed graph,” which has many applications.
PRaCtiCe 6 Does it make sense to look for the antisymmetric closure of a relation on a set? Why or why
not?
■
PRaCtiCe 7 Find the reflexive, symmetric, and transitive closure of the relation
5(a, a), (b, b), (c, c), (a, c), (a, d), (b, d), (c, a), (d, a)6
on the set S = 5a, b, c, d6.
■
335
This relation is reflexive and contains r. Furthermore, any reflexive relation on S
would have to contain the new ordered pairs we’ve added—(2, 2) and (3, 3)—so
no smaller reflexive relation can exist; that is, any reflexive relation containing r
must have the relation above as a subset.
The closure of r with respect to symmetry is
r* = 5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)6
Here it is also clear that we have added just those new pairs required—(2, 1) and
(3, 2)—for the relation to be symmetric.
For both reflexive closure and symmetric closure, we only had to inspect the
ordered pairs already in r to find out what ordered pairs we needed to add (assuming we knew what the set S was). The reflexive or symmetric closure of the relation could be found in one step. Transitive closure may require a series of steps.
Inspecting the ordered pairs in our example r, we see that we need to add (3, 2)
(because of (3, 1) and (1, 2)), (3, 3) (because of (3, 1) and (1, 3)), and (2, 1) (because of (2, 3) and (3, 1)). This gives the relation
5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)6
However, this relation is still not transitive. Because of the new pair (2, 1) and the
old pair (1, 2), we need to add (2, 2). This gives the relation
5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)6
which is transitive and also the smallest transitive relation containing r. It is the
transitive closure of r.
As in Example 9, one way to find the transitive closure of a relation is to inspect
the ordered pairs in the original relation, add new pairs if necessary, inspect the
resulting relation, add new pairs if necessary, and so on, until a transitive relation is
achieved. This is a rather ad hoc procedure, and we will give a better algorithm in
Chapter 7. There we will also see that the transitive closure of a binary relation is
related to “reachability in a directed graph,” which has many applications.
PRaCtiCe 6 Does it make sense to look for the antisymmetric closure of a relation on a set? Why or why
not?
■
PRaCtiCe 7 Find the reflexive, symmetric, and transitive closure of the relation
5(a, a), (b, b), (c, c), (a, c), (a, d), (b, d), (c, a), (d, a)6
on the set S = 5a, b, c, d6.
■