Strictly Increasing Mapping Between Wosets Implies Order Isomorphism

Theorem

Let $J$ and $E$ be well-ordered sets.

Let there exist a mapping $k: J \to E$ which is strictly increasing.

Then $J$ is order isomorphic to $E$ or an initial segment of $E$.

Proof

If the sets considered are empty or singletons, the theorem holds vacuously or trivially.

Suppose $J, E$ both have at least two elements.

Let $e_0 = \min E$, the smallest element of $E$.

Define the mapping:

$h: J \to E$:

$\map h \alpha = \begin {cases} \map \min {E \setminus h \sqbrk {S_\alpha} } & : h \sqbrk {S_\alpha} \ne E \\ e_0 & : h \sqbrk {S_\alpha} = E \end {cases}$

where $S_\alpha$ is the initial segment determined by $\alpha$ and $h \sqbrk {S_\alpha}$ is the image of $S_\alpha$ under $h$.

By the Principle of Recursive Definition for Well-Ordered Sets, this construction is well-defined and uniquely determined.

Observe that:

\(\ds h \sqbrk {S_\alpha}\)

\(=\)

\(\ds \set {\map h x \in E: \exists x \in J: \map h x = \map \min {E \setminus h \sqbrk {S_\alpha} } }\)

Definition of image of a subset

\(\ds \)

\(=\)

\(\ds \set {\map h x \in E: \exists x \in J: \map h x \prec \map h \alpha}\)

\(\ds \)

\(=\)

\(\ds S_{\map h \alpha}\)

Definition of initial segment

This equality also holds if $\map h \alpha = e_0$, by Initial Segment Determined by Smallest Element is Empty.

We claim that $\map h \alpha \preceq \map k \alpha$ for all $\alpha \in J$.

Aiming for a contradiction, suppose there is some $a \in J$ such that $\map h a \not \preceq \map k a$.

Then $\map k a \prec \map h a$ by the trichotomy law.

Because $\map h a$ has an element preceding it, $\map h a \ne e_0$.

Thus $\map k a \prec \map \min {E \setminus h \sqbrk {S_a} }$ by the construction of $k$.

Then $\map k a \in h \sqbrk {S_a}$, because it precedes the smallest element that isn't in $h \sqbrk {S_a}$.

Recall that $h \sqbrk {S_a} = S_{\map h a}$.

Then $\map k a \in S_{\map h a}$.

This implies that $\map h a \prec \map k a$, contradicting the assumption that $\map h a \not \preceq \map k a$

From this contradiction we can conclude:

$\map h \alpha \preceq \map k \alpha$ for all $\alpha \in J$.

Aiming for a contradiction, suppose there is some $\alpha \in J$ such that $h \sqbrk {S_\alpha} = E$.

Recall that $h \sqbrk {S_\alpha} = S_{\map h \alpha}$.

Thus, were such an $\alpha$ to exist, then it would succeed all elements in $E$.

It particular, it would also succeed $\map k \alpha$.

But we showed above that $\map h \alpha \preceq \map k \alpha$.

From this contradiction we see that there cannot be any $\alpha \in J$ with $h \sqbrk {S_\alpha} = E$.

Thus the definition of $h$ can be simplified:

$h: J \to E$:

$\map h \alpha = \map \min {E \setminus h \sqbrk {S_\alpha} }$

Then the hypotheses of Characterization of Strictly Increasing Mapping on Woset are satisfied.

Thus $h$ is a strictly increasing mapping and its image is $E$ or an initial segment of $E$.

From Strictly Monotone Mapping with Totally Ordered Domain is Injective, $h$ is also injective.

From Injection to Image is Bijection, $h$ is also bijective to its image.

We conclude that there is an order isomorphism from $J$ to $E$, or from $J$ to an initial segment of $E$.

$\blacksquare$

Sources

• 2000: James R. Munkres: Topology (2nd ed.): Supplementary Exercises $1.3$