Union of Transitive Relations Not Always Transitive

Theorem

The union of transitive relations is not necessarily itself transitive.

Proof

Proof by counterexample:

Let $S = \set {a, b, c, d}$.

Let $\RR_1$ be the transitive relation $\set {\tuple {a, b}, \tuple {b, c}, \tuple {a, c} }$.

Let $\RR_2$ be the transitive relation $\set {\tuple {b, c}, \tuple {c, d}, \tuple {b, d} }$.

Then we have that $\tuple {a, b} \in \RR_1 \cup \RR_2$ and $\tuple {b, d} \in \RR_1 \cup \RR_2$.

However, $\tuple {a, d} \notin \RR_1 \cup \RR_2$, and so $\RR_1 \cup \RR_2$ is not transitive.

$\blacksquare$