Question

For the following statements, provide a proof if the statement is true or give a counterexample if the statement is false. S and R are binary relations over the same domain.

(a) If S and R are both symmetric, then S ∪ R is symmetric. True/False: PROOF/COUNTEREXAMPLE

(b) If S and R are both transitive, then S o R is transitive. True/False: PROOF/COUNTEREXAMPLE

(c) If S and R are both symmetric, then S o R is symmetric. True/False: PROOF/COUNTEREXAMPLE

(d) If S and R are both anti-symmetric, then S ∪ R is anti-symmetric. True/False: PROOF/COUNTEREXAMPLE

Answer 1

In (a), the statement is false. A counterexample is shown where S and R are symmetric, but their union is not. In (b), the statement is also false. A counterexample is shown where S and R are transitive, but their composition is not. In (c), the statement is true. An example is provided where S and R are symmetric, and their composition is also symmetric. In (d), the statement is false. A counterexample is shown where S and R are anti-symmetric, but their union is not.

Step-by-step explanation:

(a) False: To provide a counterexample, let's consider the following scenario: S = {(1,2), (2,1)} and R = {(2,3), (3,2)}. Both S and R are symmetric relations. However, their union S ∪ R = {(1,2), (2,1), (2,3), (3,2)} is not symmetric because (2,3) ∈ S ∪ R but (3,2) ∉ S ∪ R.

(b) False: To provide a counterexample, let's consider the following scenario: S = {(1,2), (2,3)} and R = {(3,4), (4,5)}. Both S and R are transitive relations. However, their composition S o R = {(1,3), (2,4), (2,5)} is not transitive because although (1,3) and (2,4) are in S o R, (1,4) is not in S o R.

(c) True: If S and R are both symmetric relations, then the composition S o R is symmetric. Let's consider the following scenario: S = {(1,2), (2,1)} and R = {(2,3), (3,2)}. Both S and R are symmetric relations. Their composition S o R = {(1,3), (2,2), (2,3), (3,2)} is also symmetric because for every (x,y) in S o R, (y,x) is also in S o R.

(d) False: To provide a counterexample, let's consider the following scenario: S = {(1,2), (2,3)} and R = {(3,4), (4,5)}. Both S and R are anti-symmetric relations. However, their union S ∪ R = {(1,2), (2,3), (3,4), (4,5)} is not anti-symmetric because (2,3) and (3,2) are both in S ∪ R and they are distinct elements.