6.6k views
1 vote
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

User Blazkovicz
by
8.3k points

1 Answer

5 votes

Final answer:

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.

User Nikkya
by
7.8k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories