Recall that the reflexive/symmetric/transitive closure of a relation R on a set S is the smallest...

 

Transcribed Image Text:

Recall that the reflexive/symmetric/transitive closure of a relation R on a set S is the smallest relation R' CSXS containing R that is reflexive/symmetric/transitive. So if R is a relation on {1,2,3} given by R = {(1, 2), (2, 3)}, the symmetric closure of R is {(1, 2), (2, 1), (2, 3), (3, 2)} and the transitive closure of R is {(1, 2), (2, 3), (1, 3)}. (a):Let S = {1, 2, 3, 4, 5}. Write down a relation RCS x S with as few elements as you can find whose transitive closure is all of S x S. Bonus: the smallest such relation I can find has 5 elements. Prove that this is optimal. (b): Is the symmetric closure of a transitive relation necessarily transitive? If so, prove it. If not, find a counterexample. (c): Is the transitive closure of a symmetric relation necessarily symmetric? If so, prove it. If not, find a counterexample. Hint: For one of (b) and (c), there is a counterexample. Try experimenting with relations on a three-element set. Recall that the reflexive/symmetric/transitive closure of a relation R on a set S is the smallest relation R' CSXS containing R that is reflexive/symmetric/transitive. So if R is a relation on {1,2,3} given by R = {(1, 2), (2, 3)}, the symmetric closure of R is {(1, 2), (2, 1), (2, 3), (3, 2)} and the transitive closure of R is {(1, 2), (2, 3), (1, 3)}. (a):Let S = {1, 2, 3, 4, 5}. Write down a relation RCS x S with as few elements as you can find whose transitive closure is all of S x S. Bonus: the smallest such relation I can find has 5 elements. Prove that this is optimal. (b): Is the symmetric closure of a transitive relation necessarily transitive? If so, prove it. If not, find a counterexample. (c): Is the transitive closure of a symmetric relation necessarily symmetric? If so, prove it. If not, find a counterexample. Hint: For one of (b) and (c), there is a counterexample. Try experimenting with relations on a three-element set.