Transitivity of union of two transitive relations

Question

I have a question concerning proving properties of Relations. The question is this: How would I go about proving that, if R and S (R and S both being different Relations) are transitive, then R union S is transitive?

The answer is actually FALSE, and then a counter example is given as a solution in the book.

I understand how the counterexample works as explained in the book, but what I don't understand is, how exactly they arrive to the conclusion that the statement is actually false.

Basically I can see myself giving a proof that if that for all values (x,y,z) in R and S, if (x,y) is in R and (y,z) is in R, (x, z) is in R since R is transitive. And if (x,y) is in S and (y,z) is in R, (x,z) is in S since S is transitive. Since (x,z) is in both R and S, the intersection is true. But why wouldn't the union of R and S be true as well?

Is it because that the proof cannot be ended with "since (x,z) is in both R and S, (x,z) can be in R or S"?

Basically, that a proof can't be ended with an OR statement at the end?

Hope that all makes sense.

Answer 1

The existence of any counterexample is a proof that the statement is false. The statement is of the form

"For all transitive relations, if $S$ and $R$ are transitive relations, then $S\cup R$ is transitive." $\quad (*)$

Hence, to prove this statement is false, it suffices to prove the existence of two transitive relations whose union is not transitive. This is what a counterexample proves.

That is, the negation of $(*)$ is

$\lnot (*)$ "It is NOT THE CASE that for all transitive relations, S, R, that $S \cup R$ is transitive."

which is equivalent to

$\lnot (*)$"There exists transitive relations $S, R$ such that $S \cup R$ is NOT transitive."

Answer 2

Suppose $(x,y)$ is in $R$, and $(y,z)$ is in $S$, but $(x,z)$ is in neither.

Then $R$ and $S$ could both be transitive, but their union wouldn't be, because it would be missing $(x, z)$.

So you can't prove that the union of two transitive relations is also transitive, because it is not always true.

Answer 3

If $\langle x,y\rangle$ and $\langle y,z\rangle$ belong to $R\cap S$, then both belong to $R$, so you can apply transitivity of $R$, and both belong to $S$, so you can apply transitivity of $S$. Thus, you get $\langle x,z\rangle$ in both $R$ and $S$ and therefore in they’re intersection.

$R\cup S$ doesn’t behave nearly so nicely. The problem is that $\langle x,y\rangle$ and $\langle y,z\rangle$ might belong to $R\cup S$ because $\langle x,y\rangle\in R\setminus S$ and $\langle y,z\rangle\in S\setminus R$. Then transitivity would require $\langle x,z\rangle$ to be in $R\cup S$, i.e., in $R$, in $S$, or in both, but there is nothing in the hypotheses that requires $\langle x,z\rangle$ to belong to $R$ (since $\langle y,z\rangle\notin R$) or to $S$ (since $\langle x,y\rangle\notin S$). And in fact it’s this problem with the straightforward attempt to prove that $R\cup S$ is transitive that suggests how to construct a counterexample.

All you need is three elements, so let $A=\{0,1,2\}$, say. If $R=\{\langle 0,1\rangle\}$ and $S=\{\langle 1,2\rangle\}$, then $R$ and $S$ are both (vacuously) transitive, but $R\cup S=\{\langle 0,1\rangle,\langle 1,2\rangle\}$ fails to be transitive, since it doesn’t contain $\langle 0,2\rangle$. It shows that the potential difficulty that we spotted in trying to carry out the proof is a real difficulty: it actually can happen.

Answer 4

"How exactly they arrive to the conclusion that the statement is actually false" is by giving a counterexample. A counterexample is all it takes to prove that the statement is false. I think the question you meant to ask is, what goes wrong if you try to prove that the union of two transitive relations is transitive? Let's see.

Suppose $R$ and $S$ are transitive relations, and let's try to prove that $R\cup S$ is transitive. For that we have to show that, if $(x,y)\in R\cup S$ and $(y,z)\in R\cup S$, then $(x,z)\in R\cup S$.

Since $(x,y)\in R\cup S$, we know that either $(x,y)\in R$ or $(x,y)\in S$.

Since $(y,z)\in R\cup S$, we know that either $(y,z)\in R$ or $(y,z)\in S$.

We have four cases to consider.

Case 1. $(x,y)\in R$ and $(y,z)\in R$. Since $R$ is transitive, it follows that $(x,z)\in R$, and so $(x,z)\in R\cup S$.

Case 2. $(x,y)\in S$ and $(y,z)\in S$. Since $S$ is transitive, it follows that $(x,z)\in S$, and so $(x,z)\in R\cup S$.

Case 3. $(x,y)\in R$ and $(y,z)\in S$. Oops! Now what?

Case 4. $(x,y)\in S$ and $(y,z)\in R$. Oops! Now what?