0
$\begingroup$

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.

  • 0
    It is quite peculiar someone went through the trouble of downvoting this like today.2013-01-02

1 Answers 1

2

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.