Inverse of Transitive Relation is Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathcal R$ be transitive.


Then its inverse $\mathcal R^{-1}$ is also transitive.


Proof 1

Let $\mathcal R$ be transitive.

Then:

$\left({x, y}\right), \left({y, z}\right) \in \mathcal R \implies \left({x, z}\right) \in \mathcal R$

Thus:

$\left({y, x}\right), \left({z, y}\right) \in \mathcal R^{-1} \implies \left({z, x}\right) \in \mathcal R^{-1}$

and so $\mathcal R^{-1}$ is transitive.

$\blacksquare$


Proof 2

Let $\mathcal R$ be transitive.

Thus by definition:

$\mathcal R \circ \mathcal R \subseteq \mathcal R$

Thus:

\(\displaystyle \mathcal R^{-1} \circ \mathcal R^{-1}\) \(=\) \(\displaystyle \left({\mathcal R \circ \mathcal R}\right)^{-1}\) Inverse of Composite Relation
\(\displaystyle \) \(\subseteq\) \(\displaystyle \mathcal R^{-1}\) Inverse of Subset of Relation is Subset of Inverse

$\blacksquare$

Hence the result by definition of transitive relation.


Sources