Mapping from Totally Ordered Set is Order Embedding iff Strictly Increasing/Reverse Implication/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preceq_1}$ be a totally ordered set and let $\struct {T, \preceq_2}$ be an ordered set.

Let $\phi: S \to T$ be a strictly increasing mapping.

Then $\phi$ is an order embedding.


Proof

Let $\phi$ be strictly increasing.

Let $\map \phi x \preceq_2 \map \phi y$.

As $\struct {S, \prec_1}$ is a strictly totally ordered set:

Either $y \prec_1 x$, $y = x$, or $x \prec_1 y$.


Aiming for a contradiction, suppose that $y \prec_1 x$.

By the definition of a strictly increasing mapping:

$\map \phi y \prec_2 \map \phi x$

which contradicts the fact that $\map \phi x \preceq_2 \map \phi y$.


Therefore $y \nprec_1 x$.

Thus $y = x$, or $x \prec_1 y$, so $x \preceq_1 y$.


Hence:

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

and $\phi$ has been proved to be an order embedding.

$\blacksquare$


Sources