# Equivalence of Definitions of Order Isomorphism

## Theorem

The following definitions of the concept of Order Isomorphism are equivalent:

Let $\struct {S, \preceq_1}$ and $\struct {T, \preceq_2}$ be ordered sets.

### Definition 1

Let $\phi: S \to T$ be a bijection such that:

$\phi: S \to T$ is order-preserving
$\phi^{-1}: T \to S$ is order-preserving.

Then $\phi$ is an order isomorphism.

### Definition 2

Let $\phi: S \to T$ be a surjective order embedding.

Then $\phi$ is an order isomorphism.

### Definition 3

Let $\phi: S \to T$ be a bijection such that:

$\forall x, y \in S: x \preceq_1 y \iff \map \phi x \preceq_2 \map \phi y$

Then $\phi$ is an order isomorphism.

## Proof

### Definition 1 implies Definition 2

Let $\phi: S \to T$ be an order isomorphism by Definition 1.

Then $\phi$ is bijective, and thus trivially surjective.

Let $x, y \in S$.

Then by Definition 1:

$x \preceq_1 y \implies \map \phi x \preceq_2 \map \phi y$

Suppose that $\map \phi x \preceq_2 \map \phi y$.

Then by Definition 1:

$\map {\phi^{-1} } {\map \phi x} \preceq_1 \map {\phi^{-1} } {\map \phi y}$

By the definition of inverse:

$x \preceq_1 y$

Thus by Rule of Implication:

$\map \phi x \preceq_2 \map \phi y \implies x \preceq_1 y$.

So:

$x \preceq_1 y \iff \map \phi x \preceq_2 \map \phi y$

As this holds for all $x, y \in S$ and $\phi$ is surjective, $\phi$ is an order isomorphism by Definition 2.

$\Box$

### Definition 2 implies Definition 1

Let $\phi: S \to T$ be an order isomorphism by Definition 2.

Then $\phi$ is a surjective order embedding.

By Order Embedding is Injection, $\phi$ is injective.

As it is also surjective, $\phi$ is bijective, and thus satisfies the first condition of Definition 1.

Since $\phi$ is an order embedding:

$\forall x, y \in S: \paren {x \preceq_1 y \iff \map \phi x \preceq_2 \map \phi y}$

Thus

$\forall x, y \in S: \paren {x \preceq_1 y \implies \map \phi x \preceq_2 \map \phi y}$

This satisfies the second condition of Definition 1.

Furthermore:

$\forall x, y \in S: \paren {\map \phi x \preceq_2 \map \phi y \implies x \preceq_1 y}$

Let $p, q \in T$ and let $p \preceq_2 q$.

Then since $\phi$ is bijective, it has an inverse $\phi^{-1}$ such that

$\map \phi {\map {\phi^{-1} } p} = p$
$\map \phi {\map {\phi^{-1} } q} = q$

Thus:

$\map \phi {\map {\phi^{-1} } p} \preceq_2 \map \phi {\map {\phi^{-1} } q}$

Therefore:

$\map {\phi^{-1} } p \preceq_1 \map {\phi^{-1} } q$

Thus we see that:

$\forall p, q \in T: \paren {p \preceq_2 q \implies \map {\phi^{-1} } p \preceq_2 \map {\phi^{-1} } q}$

Thus we have satisfied the final condition of Definition 1.

$\blacksquare$

### Definition 1 iff Definition 3

Let $\phi: S \to T$ be an order isomorphism by Definition 1.

Then by Definition 1:

 $\ds \map \phi x$ $\preceq_2$ $\ds \map \phi y$ $\ds \leadsto \ \$ $\ds \map {\phi^{-1} } {\map \phi x}$ $\preceq_1$ $\ds \map {\phi^{-1} } {\map \phi y}$ $\ds \leadsto \ \$ $\ds x$ $\preceq_1$ $\ds y$

That is:

$\forall x, y \in S: \map \phi x \preceq_2 \map \phi y \implies x \preceq_1 y$

which together with:

$\forall x, y \in S: x \preceq_1 y \implies \map \phi x \preceq_2 \map \phi y$

gives:

$\forall x, y \in S: x \preceq_1 y \iff \map \phi x \preceq_2 \map \phi y$

Hence $\phi$ is an order isomorphism by Definition 3.

The above argument reverses.

$\blacksquare$