4
$\begingroup$

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?

  • 2
    hint: induction2010-11-08
  • 0
    @George: Sorry, too vague, induction on what?2010-11-08
  • 1
    @Jonas: You are trying to show that if you have an order preserving injection from $X$ to $Y$, then you have an order preserving injection from $X$ to an initial segment of $Y$. How about trying ordinal induction on $X$?2010-11-08
  • 0
    @Arturo: Right, this is the section before ordinals but after order-types. But I do have the induction theorem. I will try that, thanks.2010-11-08
  • 0
    @Arturo and @Andres: Could one of you post the suggestions in a reply so I can accept it for the sake of having less questions with no answers on this site.2010-11-10
  • 0
    @Andres Caicedo and @Jonas T: I'll let Andres do it, since his suggestion was more fleshed out than mine.2010-11-10

2 Answers 2

4

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.)

  • 0
    Thank you, I missed it when you posted it. Can you give a hint how I should show that $f(x) \leq x$? Induction?2010-11-15
  • 0
    Hi Jonas. Yes, induction. This is clear if $x$ is the smallest element of $Z$. If $f(x)\le x$ and $y$ is the smallest element of $Z$ larger than $x$, then $f(y)$ is the smallest element of $Y$ that is larger than $f(x)$. Since $f(x)\le x$, we have that $f(y)\le$ the successor of $x$ in $Y$, which is $\le y$. The remaining ("limit") case is similar.2010-11-15
1

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)


1By order preserving we mean $a