334
Relations, Functions, and Matrices
closures of Relations
If a relation r on a set S fails to have a certain property, we may be able to extend
r to a relation r* on S that does have that property. By “extend,” we mean that the
new relation r* will contain all the ordered pairs in r plus the additional ordered
pairs needed for the desired property to hold. Thus r # r*. If r* is the smallest
such set, then r* is called the closure of r with respect to that property.
PRaCtiCe 5 Test each binary relation on the given set S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = N; x r y 4 x + y is even
b. S = Z
+
(positive integers); x r y 4 x divides y
c. S = set of all lines in the plane; x r y 4 x is parallel to y or x coincides with y
d. S = N; x r y 4 x = y
2
e. S = 50, 16; x r y 4 x = y
2
f. S = 5x 0 x is a person living in Peoria6; x r y 4 x is older than y
g. S = 5x 0 x is a student in your class6; x r y 4 x sits in the same row as y
h. S = 51, 2, 36; r = 5(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)6
■
example 8
The discussion on recursion in Prolog (Section 1.5) noted that a recursive rule
should be used when the predicate being described is one that is inherited from one
object to the next. The predicate in-food-chain used there has this property because
in-food-chain-(x, y) ` in-food-chain ( y, z) S in-food-chain (x, z)
Now we see that this is simply the transitive property.
DefInItIon cloSuRe oF a Relation
A binary relation r* on a set S is the closure of a relation r on S with respect to
property P if
1. r* has property P.
2. r # r*.
3. r* is a subset of any other relation on S that includes r and has property P.
We can look for the reflexive closure, the symmetric closure, and the transitive closure of a relation on a set. Of course, if the relation already has a property,
it is its own closure with respect to that property.
example 9
Let S = 51, 2, 36 and r = 5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)6. Then r is not reflexive, not symmetric, and not transitive. The closure of r with respect to reflexivity is
r* = 5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)6
Relations, Functions, and Matrices
closures of Relations
If a relation r on a set S fails to have a certain property, we may be able to extend
r to a relation r* on S that does have that property. By “extend,” we mean that the
new relation r* will contain all the ordered pairs in r plus the additional ordered
pairs needed for the desired property to hold. Thus r # r*. If r* is the smallest
such set, then r* is called the closure of r with respect to that property.
PRaCtiCe 5 Test each binary relation on the given set S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = N; x r y 4 x + y is even
b. S = Z
+
(positive integers); x r y 4 x divides y
c. S = set of all lines in the plane; x r y 4 x is parallel to y or x coincides with y
d. S = N; x r y 4 x = y
2
e. S = 50, 16; x r y 4 x = y
2
f. S = 5x 0 x is a person living in Peoria6; x r y 4 x is older than y
g. S = 5x 0 x is a student in your class6; x r y 4 x sits in the same row as y
h. S = 51, 2, 36; r = 5(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)6
■
example 8
The discussion on recursion in Prolog (Section 1.5) noted that a recursive rule
should be used when the predicate being described is one that is inherited from one
object to the next. The predicate in-food-chain used there has this property because
in-food-chain-(x, y) ` in-food-chain ( y, z) S in-food-chain (x, z)
Now we see that this is simply the transitive property.
DefInItIon cloSuRe oF a Relation
A binary relation r* on a set S is the closure of a relation r on S with respect to
property P if
1. r* has property P.
2. r # r*.
3. r* is a subset of any other relation on S that includes r and has property P.
We can look for the reflexive closure, the symmetric closure, and the transitive closure of a relation on a set. Of course, if the relation already has a property,
it is its own closure with respect to that property.
example 9
Let S = 51, 2, 36 and r = 5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)6. Then r is not reflexive, not symmetric, and not transitive. The closure of r with respect to reflexivity is
r* = 5(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)6