Strictly Increasing Mapping Between Wosets Implies Order Isomorphism

From ProofWiki
Jump to navigation Jump to search

Lemma

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$:
$h(\alpha) = \begin{cases} \min \left({E \setminus h\left[ {S_\alpha} \right]}\right) & \text{ if } h\left[ {S_\alpha} \right] \ne E \\ e_0 & \text{ if } h\left[ {S_\alpha} \right] = E \end{cases}$


where $S_\alpha$ is the initial segment determined by $\alpha$ and $h\left[ {S_\alpha} \right]$ 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:

\(\displaystyle h[S_\alpha]\) \(=\) \(\displaystyle \left\{ { h(x) \in E: \exists x \in J: h(x) = \min\left({E \setminus h\left[{S_\alpha}\right] }\right)} \right\}\) Definition of image of a subset
\(\displaystyle \) \(=\) \(\displaystyle \left\{ { h(x) \in E: \exists x \in J: h(x) \prec h(\alpha)} \right\}\)
\(\displaystyle \) \(=\) \(\displaystyle S_{h(\alpha)}\) Definition of initial segment

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


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

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

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

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

Thus $k(a) \prec \min \left({E \setminus h\left[ {S_a} \right]}\right)$ by the construction of $k$.

Then $k(a) \in h\left[ {S_a} \right]$, because it precedes the smallest element that isn't in $h\left[ {S_a} \right]$.

Recall that $h[S_a] = S_{h(a)}$.

Then $k(a) \in S_{h(a)}$.

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

From this contradiction we can conclude:

$h(\alpha) \preceq k(\alpha)$ for all $\alpha \in J$.


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

Recall that $h[S_\alpha] = S_{h(\alpha)}$.

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

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

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

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

Thus the definition of $h$ can be simplified:

$h: J \to E$:
$h(\alpha) = \min \left({E \setminus h\left[ {S_\alpha} \right]}\right)$

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