I have a question that asks the following:
Let R and S be binary relations on a set A. Suppose that R is reflexive, symmetric, and transitive and that S is symmetric, and transitive but is not reflexive. Which statement is always true for any choice of R and S with the above properties? Only one of the following choices is correct. Provide a proof for your choice.
(a) R ∪ S is symmetric but not reflexive and not transitive.
(b) R ∪ S is symmetric but not reflexive.
(c) R ∪ S is transitive and symmetric but not reflexive.
(d) R ∪ S is reflexive and symmetric, but not transitive.
I think that the correct answer is d) because if R is reflexive, then for every x ∈ A, we have that (x,x) ∈ R. If (x,x) ∈ R, then (x,x) must also be in R ∪ S. So R ∪ S should be reflexive. However, I feel like I can apply that logic to the symmetric and transitive argument. So why would R ∪ S be symmetric but not transitive also? Is my choice wrong? Would appreciate any help
Best Answer
Your instincts are right: (d) is the correct answer, and the proof that $R \cup S$ is symmetric is similar to the proof for reflexivity. You should have a go at it.
The reason that transitivity (might) fail is that transitivity takes two inputs, so it is entirely possible that one input is in $R$ but not $S$ and the other is in $S$ but not $R$. That way, you can't get anything from the transitivity of $R$ or $S$.
You should finish the proof by finding a small example of a pair of relations $R$ and $S$ on a set which satisfy the conditions but whose union isn't transitive.