Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.