Showing that the union of transitive relations need not be transitive.

Question

I have a counterexample of the following statement but I am not sure if it is correct:

Suppose $R_1$ and $R_2$ are relations on A. If $R_1$ and $R_2$ are transitive, then $R_1 \cup R_2$ is transitive. Prove or provide a counterexample.

To me, this is of the form:

If:

$$((x,y)\in R_1 \land (y,z) \in R_1 \implies (x,z)\in R_1) \land ((x,y)\in R_2 \land (y,z) \in R_2 \implies (x,z)\in R_2) $$

Then:

$$ ((x,y)\in R_1 \lor (x,y) \in R_2) \land ((y,z)\in R_1 \lor (y,z)\in R_2) \implies ((x,z)\in R_1 \lor (x,z)\in R_2) $$

My counterexample:

\begin{align*} A&=\{ 1,2,3\} \\ R_1&= \{(1,2)\} \\ R_2&= \{(2,3)\} \end{align*}

Then if we take $x=1,y=2,z=3$, it should yield the following:

If:

$$(\underbrace{(x,y)\in R_1 \land (y,z) \in R_1}_{\text{false}} \implies \underbrace{(x,z)\in R_1}_{\text{false}}) \land (\underbrace{(x,y)\in R_2 \land (y,z) \in R_2}_{\text{false}} \implies \underbrace{(x,z)\in R_2}_{\text{false}}) $$

Then:

$$ (\underbrace{(x,y)\in R_1 \lor (x,y) \in R_2)}_{\text{true}} \land (\underbrace{(y,z)\in R_1 \lor (y,z)\in R_2)}_{\text{true}} \implies (\underbrace{(x,z)\in R_1 \lor (x,z)\in R_2}_{\text{false}}) $$

I know it's a mess, but it's the best I can do to illustrate my idea clearly. Could anyone please help? Thank you so much!

Answer 1

As noted in the comments, your counterexample is perfectly valid, though you seem to overthink a bit. All you need to note are the following:

• $R_1,R_2$ are both singletons
• $R_1$ is transitive since $(1,2),(1,2) \in R_1$ and $(1,2) \in R_1$
• $R_2$ is transitive since $(2,3),(2,3) \in R_2$ and $(2,3) \in R_2$
• $R_1 \cup R_2$ is not transitive since $(1,2),(2,3) \in R_1 \cup R_2$ but $(1,2) \not \in R_1 \cup R_2$

Thus the union of transitive relations is not necessarily transitive. (In fact, even if $R_1,R_2$ are equivalence relations, their union still need not be one, and need not even be transitive, as you can see explained here.)

---

Mostly just posting this to get this out of the unanswered queue. Posting as Community Wiki in particular since I have nothing further to add.