Section 5.1 Relations
349
22. Let r and s be binary relations on a set S.
a. If r and s are reflexive, is r c s reflexive? Is r d s reflexive?
b. If r and s are symmetric, is r c s symmetric? Is r d s symmetric?
c. If r and s are antisymmetric, is r c s antisymmetric? Is r d s antisymmetric?
d. If r and s are transitive, is r c s transitive? Is r d s transitive?
23. Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 11.
24. Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 12.
25. Given the following binary relation
S = set of all cities in the country
x r y 4 Take-Your-Chance Airlines flies directly from x to y
describe in words what the transitive closure relation would be.
26. Two additional properties of a binary relation r are defined as follows:
r is irreflexive
means: (4x)(x [ S S (x, x) o r)
r is asymmetric means: (4x)(4y)(x [ S ` y [ S ` (x, y) [ r S (y, x) o r)
a. Give an example of a binary relation r on set S = 51, 2, 36 that is neither reflexive nor irreflexive.
b. Give an example of a binary relation r on set S = 51, 2, 36 that is neither symmetric nor asymmetric.
c. Prove that if r is an asymmetric relation on a set S, then r is irreflexive.
d. Prove that if r is an irreflexive and transitive relation on a set S, then r is asymmetric.
e. Prove that if r is a nonempty, symmetric, and transitive relation on a set S, then r is not irreflexive.
27. Does it make sense to look for the irreflexive closure of a relation? (See Exercise 26.) Why or why not?
28. Does it make sense to look for the asymmetric closure of a relation? (See Exercise 26.) Why or why not?
29. Let S be an n-element set. How many different binary relations can be defined on S? (Hint: Recall the
formal definition of a binary relation.)
30. Let r be a binary relation on a set S. For A # S, define
[A = 5x 0 x [ S ` (4y)(y [ A S x r y)6
A[ = 5x 0 x [ S ` (4y)(y [ A S y r x)6
a. Prove that if r is symmetric, then [A = A[.
b. Prove that if A # B then [B # [A and B[ # A[.
c. Prove that A # ([A)[.
d. Prove that A # [(A[).
31. Draw the Hasse diagram for the following partial orderings.
a. S = 5a, b, c6
r = 5(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)6
b. S = 5a, b, c, d6
r = 5(a, a), (b, b), (c, c), (d, d ), (a, b), (a, c)6
c. S = 5[, 5a6, 5a, b6, 5c6, 5a, c6, 5b66
A r B 4 A # B
349
22. Let r and s be binary relations on a set S.
a. If r and s are reflexive, is r c s reflexive? Is r d s reflexive?
b. If r and s are symmetric, is r c s symmetric? Is r d s symmetric?
c. If r and s are antisymmetric, is r c s antisymmetric? Is r d s antisymmetric?
d. If r and s are transitive, is r c s transitive? Is r d s transitive?
23. Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 11.
24. Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 12.
25. Given the following binary relation
S = set of all cities in the country
x r y 4 Take-Your-Chance Airlines flies directly from x to y
describe in words what the transitive closure relation would be.
26. Two additional properties of a binary relation r are defined as follows:
r is irreflexive
means: (4x)(x [ S S (x, x) o r)
r is asymmetric means: (4x)(4y)(x [ S ` y [ S ` (x, y) [ r S (y, x) o r)
a. Give an example of a binary relation r on set S = 51, 2, 36 that is neither reflexive nor irreflexive.
b. Give an example of a binary relation r on set S = 51, 2, 36 that is neither symmetric nor asymmetric.
c. Prove that if r is an asymmetric relation on a set S, then r is irreflexive.
d. Prove that if r is an irreflexive and transitive relation on a set S, then r is asymmetric.
e. Prove that if r is a nonempty, symmetric, and transitive relation on a set S, then r is not irreflexive.
27. Does it make sense to look for the irreflexive closure of a relation? (See Exercise 26.) Why or why not?
28. Does it make sense to look for the asymmetric closure of a relation? (See Exercise 26.) Why or why not?
29. Let S be an n-element set. How many different binary relations can be defined on S? (Hint: Recall the
formal definition of a binary relation.)
30. Let r be a binary relation on a set S. For A # S, define
[A = 5x 0 x [ S ` (4y)(y [ A S x r y)6
A[ = 5x 0 x [ S ` (4y)(y [ A S y r x)6
a. Prove that if r is symmetric, then [A = A[.
b. Prove that if A # B then [B # [A and B[ # A[.
c. Prove that A # ([A)[.
d. Prove that A # [(A[).
31. Draw the Hasse diagram for the following partial orderings.
a. S = 5a, b, c6
r = 5(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)6
b. S = 5a, b, c, d6
r = 5(a, a), (b, b), (c, c), (d, d ), (a, b), (a, c)6
c. S = 5[, 5a6, 5a, b6, 5c6, 5a, c6, 5b66
A r B 4 A # B