Intersection of Transitive Relations is Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

The intersection of two transitive relations is also a transitive relation.


General Result

Let $\left\{ {\mathcal R_i: i \mathop \in I}\right\}$ be an $I$-indexed collection of transitive relations on a set $S$.


Then their intersection $\displaystyle \bigcap_{i \mathop \in I} \mathcal R_i$ is also a transitive relation on $S$.


Proof

Let $\mathcal R_1$ and $\mathcal R_2$ be transitive relations (on what sets is immaterial for this argument).

Let $\left({s_1, s_2}\right) \in \mathcal R_1 \cap \mathcal R_2$ and $\left({s_2, s_3}\right) \in \mathcal R_1 \cap \mathcal R_2$.


Then by definition of intersection:

$\left({s_1, s_2}\right) \in \mathcal R_1$ and $\left({s_1, s_2}\right) \in \mathcal R_2$
$\left({s_2, s_3}\right) \in \mathcal R_1$ and $\left({s_2, s_3}\right) \in \mathcal R_2$


Then as $\mathcal R_1$ and $\mathcal R_2$ are both transitive:

$\left({s_1, s_3}\right) \in \mathcal R_1$ and $\left({s_1, s_3}\right) \in \mathcal R_2$

and by definition of intersection:

$\left({s_1, s_3}\right) \in \mathcal R_1 \cap \mathcal R_2$

hence $\mathcal R_1 \cap \mathcal R_2$ is transitive.

$\blacksquare$