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.