Union of Transitive Relations Not Always Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

The union of transitive relations is not necessarily itself transitive.


Proof

Proof by counterexample:

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

Let $\mathcal R_1$ be the transitive relation $\left \{{\left({a, b}\right), \left({b, c}\right), \left({a, c}\right)}\right\}$.

Let $\mathcal R_2$ be the transitive relation $\left \{{\left({b, c}\right), \left({c, d}\right), \left({b, d}\right)}\right\}$.

Then we have that $\left({a, b}\right) \in \mathcal R_1 \cup \mathcal R_2$ and $\left({b, d}\right) \in \mathcal R_1 \cup \mathcal R_2$.

However, $\left({a, d}\right) \notin \mathcal R_1 \cup \mathcal R_2$, and so $\mathcal R_1 \cup \mathcal R_2$ is not transitive.

$\blacksquare$