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

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({S, \preceq_1}\right)$ be a totally ordered set and let $\left({T, \preceq_2}\right)$ be an ordered set.

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

Then $\phi$ is an order embedding.


Proof 1

Let $x \preceq_1 y$.

Then $x = y$ or $x \prec_1 y$.


Let $x = y$.

Then

$\phi \left({x}\right) = \phi \left({y}\right)$

so:

$\phi \left({x}\right) \preceq_2 \phi \left({y}\right)$


Let $x \prec_1 y$.

Then by the definition of strictly increasing mapping:

$\phi \left({x}\right) \prec_2 \phi \left({y}\right)$

so by the definition of $\prec_2$:

$\phi \left({x}\right) \preceq_2 \phi \left({y}\right)$

Thus:

$x \preceq_1 y \implies \phi \left({x}\right) \preceq_2 \phi \left({y}\right)$


It remains to be shown that:

$\phi \left({x}\right) \preceq_2 \phi \left({y}\right) \implies x \preceq_1 y$

Suppose that $x \npreceq_1 y$.

Since $\preceq_1$ is a total ordering:

$y \prec_1 x$

Thus since $\phi$ is strictly increasing:

$\phi \left({y}\right) \prec_1 \phi \left({x}\right)$

Thus:

$\phi \left({x}\right) \not\preceq_1 \phi \left({y}\right)$

Therefore:

$x \npreceq_1 y \implies \phi \left({x}\right) \npreceq_2 \phi \left({y}\right)$

By the Rule of Transposition:

$\phi \left({x}\right) \preceq_2 \phi \left({y}\right) \implies x \preceq y$

$\blacksquare$


Proof 2

Let $\phi$ be strictly increasing.

Suppose that $\phi \left({x}\right) \preceq_2 \phi \left({y}\right)$.

As $\left({S, \prec_1}\right)$ is a strictly totally ordered set:

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


Suppose for the sake of contradiction that $y \prec_1 x$.

By the definition of a strictly increasing mapping:

$\phi \left({y}\right) \prec_2 \phi \left({x}\right)$

which contradicts the fact that $\phi \left({x}\right) \preceq_2 \phi \left({y}\right)$.


Therefore $y \nprec_1 x$.

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


Hence:

$\phi \left({x}\right) \preceq_2 \phi \left({y}\right) \iff x \preceq_1 y$

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

$\blacksquare$