2.3. Relations 23 Exercise 2.3.5. Is = reflexive? Symmetric? Antisymmetric? Tran- sitive? How about =? Exercise 2.3.6. For finite relations we may check these properties by hand. Let A = {1, 2, 3, 4}. (a) What is the smallest binary relation on A that is reflexive? (b) Define the following binary relations on A. R1 = {(2, 3), (3, 4), (4, 2)} R2 = {(1, 1), (1, 2), (2, 1), (2, 2)} R3 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)} For each of those relations, answer the following questions. (i) Is the relation reflexive? Symmetric? Antisymmetric? Tran- sitive? (ii) If the relation is not reflexive, what is the smallest collection of pairs that needs to be added to make it reflexive? (iii) If the relation is not symmetric, what is the smallest collec- tion of pairs that needs to be added to make it symmetric? (iv) If the relation is not transitive, what is the smallest collec- tion of pairs that needs to be added to make it transitive? (v) If the relation is not antisymmetric, what is the smallest collection of pairs that could be removed to make it anti- symmetric? Is this answer unique? Exercise 2.3.7. Let A = {1, 2, 3}. Define binary relations on A with the following combinations of properties or say why such a relation cannot exist. Can such a relation be nonempty? (i) Reflexive and antisymmetric but neither symmetric nor transi- tive. (ii) Symmetric but neither reflexive nor transitive. (iii) Transitive but neither reflexive nor symmetric. (iv) Symmetric and transitive but not reflexive. (v) Both symmetric and antisymmetric. (vi) Neither symmetric nor antisymmetric. (vii) Reflexive and transitive but not symmetric.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.