Inverse of Transitive Relation is Transitive/Proof 1
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.
Then:
- $\tuple {x, y}, \tuple {y, z} \in \RR \implies \tuple {x, z} \in \RR$
Thus:
- $\tuple {y, x}, \tuple {z, y} \in \RR^{-1} \implies \tuple {z, x} \in \RR^{-1}$
and so $\RR^{-1}$ is transitive.
$\blacksquare$