Inverse of Non-Transitive Relation is Non-Transitive

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R$ be a relation on a set $S$.


If $\mathcal R$ is non-transitive, then so is $\mathcal R^{-1}$.


Proof

Let $\mathcal R$ be non-transitive.

Then:

$\exists x_1, y_1, z_1 \in S: \left({x_1, y_1}\right), \left({y_1, z_1}\right) \in \mathcal R, \left({x_1, z_1}\right) \in \mathcal R$
$\exists x_2, y_2, z_2 \in S: \left({x_2, y_2}\right), \left({y_2, z_2}\right) \in \mathcal R, \left({x_2, z_2}\right) \notin \mathcal R$


So:

$\exists x_1, y_1, z_1 \in S: \left({y_1, x_1}\right), \left({z_1, y_1}\right) \in \mathcal R^{-1}, \left({z_1, x_1}\right) \in \mathcal R^{-1}$
$\exists x_2, y_2, z_2 \in S: \left({y_2, x_2}\right), \left({z_2, y_2}\right) \in \mathcal R^{-1}, \left({z_2, x_2}\right) \notin \mathcal R^{-1}$

So $\mathcal R^{-1}$ is non-transitive.

$\blacksquare$