Inverse of Transitive Relation is Transitive/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\RR$ be a relation on a set $S$.

Let $\RR$ be transitive.


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


Proof

Let $\RR$ be transitive.

Thus by definition:

$\RR \circ \RR \subseteq \RR$

Thus:

\(\ds \RR^{-1} \circ \RR^{-1}\) \(=\) \(\ds \paren {\RR \circ \RR}^{-1}\) Inverse of Composite Relation
\(\ds \) \(\subseteq\) \(\ds \RR^{-1}\) Inverse of Subset of Relation is Subset of Inverse

$\blacksquare$

Hence the result by definition of transitive relation.


Sources