Prove the comparability theorem for well ordered sets using transfinite induction

elementary-set-theoryproof-explanationwell-orders

My question is about the same proof discussed here, but I am confused about more than this question addresses.

In Naive Set Theory, Halmos phrases the comparability theorem as follows:

The assertion is that if $\langle X, \leqslant_X \rangle$ and $\langle Y, \leqslant_Y \rangle$ are well ordered sets, then either $X$ and $Y$ are similar, or one of them is similar to an initial segment of the other.

My questions are about the following proof:

We assume that $X$ and $Y$ are non-empty well ordered sets such that neither is similar to an initial segment of the other; we proceed to prove that under these circumstances $X$ must be similar to $Y$. Suppose that $a \in X$ and that $t$ is a sequence of type $a$ in $Y$; in other words $t$ is a function from $s(a)$ into $Y$. Let $f(t)$ be the least of the proper upper bounds of the range of $t$ in $Y$, if there are any; in the contrary case, let $f(t)$ be the least element of $Y$. In the terminology of the transfinite recursion theorem, the function $f$ thereby determined is a sequence function of type $X$ in $Y$. Let $U$ be the function that the transfinite recursion theorem associates with this situation. An easy argument (by transfinite induction) shows that, for each $a \in X$, the function $U$ maps the initial segment determined by $a$ in $X$ one-to-one onto the initial segment determined by $U(a)$ in $Y$. This implies $U$ is a similarity, and the proof is complete.

Where the statement of the transfinite recursion theorem is:

If $W$ is a well ordered set, and if $f$ is a sequence function of type $W$ in a set $X$, then there exists a unique function $U$ from $W$ into $X$ such that $U(a) = f(U|_{s(a)})$ for each $a$ in $W$.

and $s(a)$ is the initial segment of $a$.

I don't understand how to complete the proof given this outline. My questions are:

  1. How do I show that, for each $a \in X$, the function $U$ maps the initial segment determined by $a$ in $X$ one-to-one onto the initial segment determined by $U(a)$ in $Y$

I can figure out how to set up the beginning of the transfinite induction proof (I think), but can't prove the induction step:

Let $S$ be the set of all $a \in X$ such that $U$ maps the initial segment determined by $a$ in $X$ one-to-one onto the initial segment determined by $U(a)$ in $Y$. Assume by the hypothesis of transfinite induction that the initial segment $s(a) \subseteq S$.

How do I show that $a \in S$?

Finally, given (1),

  1. Why is U 1-1?

  2. Why is U onto?

  3. Why is it the case that $\forall a, b \in X, a \leqslant_X b \iff U(a) \leqslant_Y U(b)$?

I'm really not sure where to even start with these last three. I can write down the definitions of 1-1 and onto and stare at them, and stare at their contrapositives, but I can't figure out how to make progress.

Best Answer

This is simply part of the induction. If $U$ was a bijection between $s(a)$ and $s(y)$, then by the definition, $U(a)$ must be mapped to $\min Y\setminus s(y)$. And that is also injective, and it is also surjective onto $s(U(a))$ because that is the only thing we added. And likewise, it has to remain order preserving for the same reason.

For the limit case, the proof is somewhat similar.

If you are not Halmos, and you are not afraid of ordinals, then you can really talk about this as a transfinite induction over order-types. Then this becomes clearer from an intuitive point of view.

The initial segments of $X$ and $Y$ respectively, have "shorter" order types, and must therefore embed into one another in the appropriate way.

Related Question