Relation Isomorphism Preserves Transitivity

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({S, \mathcal R_1}\right)$ and $\left({T, \mathcal R_2}\right)$ be relational structures.

Let $\left({S, \mathcal R_1}\right)$ and $\left({T, \mathcal R_2}\right)$ be (relationally) isomorphic.


Then $\mathcal R_1$ is a transitive relation if and only if $\mathcal R_2$ is a transitive relation.


Proof

Let $\phi: S \to T$ be a relation isomorphism.

By Inverse of Relation Isomorphism is Relation Isomorphism it follows that $\phi^{-1}: T \to S$ is also a relation isomorphism.

Without loss of generality, it is therefore sufficient to prove only that if $\mathcal R_1$ is transitive, then $\mathcal R_2$ is also transitive.


So, suppose $\mathcal R_1$ is a transitive relation.


Let $y_1, y_2, y_3 \in T$ such that $y_1 \mathrel {\mathcal R_2} y_2$ and $y_2 \mathrel {\mathcal R_2} y_3$.

Let $x_1 = \phi^{-1} \left({y_1}\right)$, $x_2 = \phi^{-1} \left({y_2}\right)$ and $x_3 = \phi^{-1} \left({y_3}\right)$.

As $\phi$ is a bijection it follows from Inverse Element of Bijection that:

$y_1 = \phi \left({x_1}\right)$
$y_2 = \phi \left({x_2}\right)$
$y_3 = \phi \left({x_3}\right)$


As $\phi^{-1}$ is a relation isomorphism it follows that:

$x_1 = \phi^{-1} \left({y_1}\right) \mathrel {\mathcal R_1} \phi^{-1} \left({y_2}\right) = x_2$
$x_2 = \phi^{-1} \left({y_2}\right) \mathrel {\mathcal R_1} \phi^{-1} \left({y_3}\right) = x_3$

As $\mathcal R_1$ is a transitive relation it follows that:

$x_1 \mathrel {\mathcal R_1} x_3$

As $\phi$ is a relation isomorphism it follows that:

$y_1 = \phi \left({x_1}\right) \mathrel {\mathcal R_2} \phi \left({x_3}\right) = y_3$


Hence if $y_1 \mathrel {\mathcal R_2} y_2$ and $y_2 \mathrel {\mathcal R_2} y_3$, then also:

$y_1 \mathrel {\mathcal R_2} y_3$

Hence, $\mathcal R_2$ is a transitive relation, by definition.

Hence the result.

$\blacksquare$


Sources