Order-isomorphic with a subset iff order-isomorphic with an initial segment Let $(X, \prec)$ and $(Y, <)$ be two well-ordered sets. I want to show that if $X$ is isomorphic to a subset of Y then $X$ is isomorphic with an initial segment of $Y$. (The other direction is of course true).
I would appreciate some hints. Does this require the recursion theorem to construct the isomorphism?
 A: Jonas: What you need to show is that if $Y$ is well-ordered, then any subset $Z$ of $Y$ is isomorphic to an initial segment of $Y$. How would you define such an isomorphism $f$? You do not have many possibilities: The least element of $Z$ must be mapped by $f$ to the smallest element of $Y$. The next element of $Z$ must be mapped by $f$ to the next element of $Y$, and so on. You just need to check that this works.
In more detail, say that $g$ is an approximation iff its domain is an initial segment of $Z$, its range is an initial segment of $Y$, and $g$ is an order isomorphism from its domain onto its range.
One checks (by considering least disagreements) that any two approximations coincide on the common part of their domains, so we can let $f$ be the common function resulting from pasting all the approximations together.
We just need to see that $f$ exhausts $Z$. For this, one can check that $f(x)\le x$ for all $x$, so one "does not run out of room." 
There is a slightly more elegant (and formal) way of presenting this argument, by appealing to the recursion theorem. 
For $x$ in $Z$, define $f(x)=\sup_Y({\rm succ}_Y f(y)\mid y\in Z, y\lt x)$, where ${\rm succ}_Y a$ means the successor in $Y$ of $a$. Then $f$ is precisely the map we wanted. (One still needs a little argument to see that it works).
A trickier question for another day is whether the recursion theorem is needed for the argument. This may be formalized by asking whether Zermelo set theory proves the result (so we do not have access to replacement), but there may be finer formulations. 
(The above was written quickly. Let me know of infelicities or plain falsehoods and I'll try to edit.)
A: We will use the fact that for any two well ordered sets either $X$ is isomorphic to an initial segment of $Y$ or other way round. (This is basically trichotomy for inequality ordinals. Some authors call this fundamental theorem for well-ordered sets; see here or here.)

Another useful fact:
Lemma. If $X$ is well-ordered set and $f\colon X\to X$ is an order-preserving map1, then $x\le f(x)$ for each $x\in X$.
Hint: Suppose that this is not true for each $x$. What can be said about the minimal element of the non-empty set $\{x\in X; x>f(x)\}$?

Now we finally get to the proof of the fact you ask about.
Let us assume that $X$ is isomorphic to a subset of $Y$ but it is not isomorphic to any initial segment of $Y$. Then $Y$ is isomorphic to some proper initial segment $X_a$ of $X$ (by the fundamental theorem). 
We have some order-preserving maps $f\colon X \to Y$ and $g\colon Y\to X$ such that the range of $g$ is not the whole $X$. Then $h=g\circ f \colon X\to X$ is an order-preserving map which maps $X$ to some subset of $X_a$. This means that $h(x)<a$ for each $x\in x$ and, in particular,
$$h(a)<a.$$
This contradicts the above lemma.

1By order preserving we mean $a<b$ $\Rightarrow$ $f(a)<f(b)$; i.e. the maps which preserve strict inequality (or equivalently they are injective and preserve non-strict inequality.) 
