Union of Transitive Relations Not Always Transitive
Jump to navigation
Jump to search
Theorem
The union of transitive relations is not necessarily itself transitive.
Proof
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$