Any subset of a well-ordered set is isomorphic to an initial segment of this well-ordered set.

Question

I wanted to prove the fact for which I have a sketch of proof: Let $(W,\leq )$ be a well-ordered set and $U$ be a subset of $W$. Then considering the restriction of $\leq $ to $U\times U$, we have that $U$ is isomorphic to an initial segment of $W$ or it is isomorphic to $W$.

A natural proof would be as follows: We shall define an order-embedding $f:U\rightarrow W$ such that $f(U)$ is $W$ or an initial segment of $W$. Send the least element of $U$ to the least element of $W$. Assume that $f$ is defined for all $v \lt u$ where $u\in U$. Then define $f(u)=\min\{ w\in W:f(v) \lt w \text{ for all }v \lt pred_U(u)\}$.

This proof is very long because one also has to show that $f$ is really an order isomorphism and that $f(U)$ is an initial segment of $W$ or the whole $W$. Both by transfinite induction... In the proof above, one has to also check that $f(v)$ is not the greatest element of $W$ for $v \lt u\in U$.

On the other hand, I also believe that such a simple and basic statement should have much shorter proof without transfinite recursion&induction.

Do you have any idea for a simpler proof?

Answer 1

I’m not sure if this is any simpler, and this is still an application of transfinite induction, but you can also construct the order isomorphism the other way around. That is, instead of trying to define a map $U \to W$, we define, by transfinite induction, a partial map $f: W \to U$. At each $w \in W$, let,

$$f(w) = \min \{u \in U: u \notin f(\{w_0 \in W: w_0 < w\})\}$$

The inductive construction stops when either the range is already the entire $U$, so the set over which to take the minimum is empty; or if the map is defined on the entirety of $W$. The domain then is clearly an initial segment of $W$ (or $W$ itself). Using transfinite induction, it is not hard to show that $f$ is an order isomorphism onto its range. Finally, the range must be $U$. Indeed, by transfinite induction, $f$ applies to an initial segment of $W$ is an initial segment of $U$, and $f(w) \geq w$ for all $w \in W$, whenever $f(w)$ is defined. If the range is not the entirety of $U$, then the transfinite inductive construction only terminates when $f$ is defined on the entirety of $W$ and we have $f(W) \subsetneq U$. But then let $w = \min \{U \setminus f(W)\}$, and we must have $f(w) < w$ (as $f(W)$ is an initial segment of $U$), a contradiction.