# Initial segments order-isomorphic

Let $(X, \prec)$ and $(Y, <)$ be two well-ordered sets. Now, I want to understand the proof that $X$ is isomorphic to an initial segment of $Y$ or $Y$ is isomorphic with an initial segment of $X$.

Now, they define $\mathcal{F}$ to be the set of all mappings with as domain an initial segment of $X$ and $Y$ as codomain and $F: \mathcal{F} \to Y \cup \{Y\}$ as $F(f) = \text{min}(Y \setminus \text{ran} f)$ if $f$ is not surjective and equal to $Y$ if $f$ is surjective. Now, they want to apply the recursion principle to $F$ to get a mapping from $X$ to $Y \cup \{Y\}$ that satisfies $f(x) = F(f|_{\hat{x}})$ for all $x$. Now I wonder how this is possible with the Recursion principle because the codomain is different. (Arturo solved this (very easy...) question in the comments).

Further they begin $x \prec y$ in $X$ and $f(y) \neq Y$ then $f(x) \lt f(y)$, so I assume the above but then I see that (strict) $Y \setminus \text{ran} f|_{\hat{y}} \subset Y \setminus \text{ran} f|_{\hat{x}}$ but why would could the minimum not be equal?

Thanks.

-
What do you mean? The Transfinite Recursion Principle requires the given function to have a domain different from the one in the conclusion. – Arturo Magidin Nov 4 '10 at 20:58
Well, in the given function $F$ the codomain in the statement of the Recursion principle is the same as the codomain of the functions in $\mathcal{F}$. It is probably something easy that I'm missing. – Jonas Teuwen Nov 4 '10 at 21:03
Both $F$ and $f$ have codomain $Y\cup\{Y\}$. What do you mean "different codomain"? – Arturo Magidin Nov 4 '10 at 21:11
@Arturo: $\mathcal{F}$ is defined as the functions with codomain $Y$, not $Y \cup \\{Y\\}$. In the Recursion principle they then require the functions to be from $\mathcal{F} \to Y$ if $Y$ is the codomain of the functions in $\mathcal{F}$. – Jonas Teuwen Nov 4 '10 at 21:13
Since $Y$ is contained in $Y\cup\{Y\}$, there is no problem in thinking of $\mathcal{F}$ as having codomain $Y\cup\{Y\}$. "Codomain" is just "a set that contains the image". – Arturo Magidin Nov 4 '10 at 21:16

## 1 Answer

Let $z$ be the least element of $X$ strictly larger than $x$; it exists, since you have at least $y$ among the upper bounds. You cannot have $f(z)=Y$, because you do not have $f(y)=Y$; so $f(z)$ is the least element which is not the image of any element of $\{a\in X\mid a\preceq x\}$. If $z=y$, then this shows that $f(y)$ cannot be equal to $f(x)$ (since $f(y)$ is the least element of the complement of a set that contains $f(x)$); if $z\neq y$, then $f(z)\in \mathrm{ran}f|_{\hat{y}}$; so the minimum of the complement of the range of $f|_{\hat{y}}$ cannot be equal to the minimum of the complement of the range of $f|_{\hat{x}}$: the latter is $f(z)$, and this is not in the complement of the former.

-