180 CHAPTER 3 Relations
R = {(1, 2), (2, 3), (3, 4)}
(a) Find the reflexive closure of R.
(b) Find the symmetric closure of R.
(c) Find the transitive closure of R.
(d) Find the reflexive and transitive closure of R.- Let X = {1, 2, 3, 4, 5, 6}, and define a relation R on X as
R = {(1, 2), (2, 1), (2, 3), (3, 4), (4, 5), (5, 6)}
(a) Find the reflexive closure of R.
(b) Find the symmetric closure of R.
(c) Find the transitive closure of R.
(d) Find the reflexive and transitive closure of R.13. Let A = {1, 2, 3, 4). Find the transitive closure of the relation R defined on A as
R = {(1, 2), (2, 1), (2, 3), (3, 4))
- Let R be the relation on (a, b, c, d, e, f g} defined as
R = {(a, b), (b, c), (c, a), (d, e), (e, f), (f, g))
Find the smallest integers m and n such that 0 < m < n and R' = Rn. Identify the
transitive closure of R as well as the transitive, reflexive, and symmetric closures of R.15. Let X = (4, 5, 6, 7, 8), and define the relation R on X as {(4, 5), (5, 6), (6, 7), (7, 8),
(8, 4)). Find the smallest integers m and n such that R' = Rn, where 0 < m < n.- Find the reflexive, symmetric, and transitive closures of the following relations:
(a) = onN
(b) < onN•
(c) < onN
(d) R on N where R(x, y) if and only if y = x + 1
(e) R on R where R(x, y) if and only if y = x + 1
(f) R on R where R(x, y) if and only if Ix - y I < 0.0005- Show that the transitive closure of a relation R on a set X is the intersection of all
transitive binary relations R' on X where R C R'. - Is there a reasonable notion of antisymmetric closure? Why, or why not?
- Prove Theorem 5(c) as follows:
(a) Prove by induction that if R is a binary relation on a set X, then R' o Rn = Rm+n
where m, n E N.
(b) Prove that R+ is transitive.
(c) Prove by induction that if R C S and S is a transitive binary relation, then Rn C S.
Conclude that R+ C S. - Prove Theorem 5(d).