Order Isomorphism iff Strictly Increasing Surjection

From ProofWiki
Jump to navigation Jump to search

Theorem

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

A mapping $\phi: \struct {S, \preceq_1} \to \struct {T, \preceq_2}$ is an order isomorphism if and only if:

$(1): \quad \phi$ is a surjection
$(2): \quad \forall x, y \in S: x \mathop {\prec_1} y \implies \map \phi x \mathop {\prec_2} \map \phi y$


Proof

Necessary Condition

Let $\phi: \struct {S, \preceq_1} \to \struct {T, \preceq_2}$ be an order isomorphism.

Then by definition $\phi$ is a bijection and so a surjection.

Suppose $x \mathop {\prec_1} y$.

That is:

$x \mathop {\preceq_1} y$
$x \ne y$

Then:

$x \mathop {\prec_1} y \implies \map \phi x \mathop {\preceq_2} \map \phi y$

as $\phi$ is an order isomorphism.

But as $\phi$ is a bijection it is also an injection.

Thus:

$\map \phi x = \map \phi y \implies x = y$

and so it follows that:

$x \mathop {\prec_1} y \implies \map \phi x \mathop {\prec_2} \map \phi y$

$\Box$


Sufficient Condition

Suppose $\phi$ is a mapping which satisfies the conditions:

$(1): \quad \phi$ is a surjection
$(2): \quad \forall x, y \in S: x \mathop {\prec_1} y \implies \map \phi x \mathop {\prec_2} \map \phi y$

From $(2)$ and Strictly Increasing Mapping is Increasing we have:

$x \mathop {\preceq_1} y \implies \map \phi x \mathop {\preceq_2} \map \phi y$


Now suppose $\map \phi x \mathop {\preceq_2} \map \phi y$.

Suppose $y \mathop {\prec_1} x$.

Then from $(2)$ it would follow that $\map \phi y \mathop {\prec_2} \map \phi x$.

So it is not the case that $y \mathop {\prec_1} x$.

So from the Trichotomy Law:

$x \mathop {\preceq_1} y$

Thus it follows that:

$x \mathop {\preceq_1} y \iff \map \phi x \mathop {\preceq_2} \map \phi y$

It follows from Order Isomorphism is Surjective Order Embedding that $\phi$ is an order isomorphism.

$\blacksquare$


Sources