Exercises
179
(d) IsSiblingOfOrEquals on the set of all people
(e) IsCousinOfOrEquals on the set of all people
Prove your assertions.
6. Since relations are sets, it is possible to define union, intersection, relative complement,
and absolute complement on pairs of relations. A natural question is which properties
of the original relations still hold for the resulting new relation. Fill in the following
table with Y/N, representing YES and NO, respectively. If the entry is N, find an
example that shows the property is not preserved under the operation. For instance,
enter a Y in the first row, second column, if the intersection of two reflexive relations
is still reflexive; otherwise, enter an N.
Relative
Absolute
Union Intersection Complement Complement
Reflexive
Irreflexive
Symmetric
Antisymmetric
Transitive
7. Let A = {a, b, c, d}. Define the relations R 1 and R 2 on A as
R= {(a, a), (a, b), (b, d)}
and
R2 = {(a, d), (b, c), (b, d), (c, b)}
Find
(a) R 1 o R2
(b) R 2 o RI
(c) R
2
(d) R2
8. Find a set A with n elements and a relation R on A such that R
1 , R2
. . R are all
distinct.
9. In the example involving the family tree (see Figure 3.2);
(a) What is the transitive and reflexive closure of IsParentOf?
(b) What is the transitive and reflexive closure of IsMarriedTo?
10. Let X = {a, b, c, d, e}. Let R, be the relation on X with elements {(a, b), (a, c), (d,
e)}. Let R 2 be the relation on X with elements {(a, b), (b, c), (c, d), (d, e), (e, a)}. For
each of these relations, find the following:
(a) The smallest relation on X that contains R and is reflexive
(b) The smallest relation on X that contains R and is symmetric
(c) The smallest relation on X that contains R and is transitive
(d) The smallest relation on X that contains R and is reflexive and transitive
11. Let X = {1, 2, 3, 4}, and define a relation R on X as