Proof of Comparability Theorem for well-ordered sets using transfinite recursion

I am reading through Halmos's "Naive Set Theory". In Section 18, Halmos uses transfite recursion to prove the Comparability Thereom for well-ordered sets:

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.

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.

I think I understand the proof up until this step:

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.

I can't seem to get my head around this "easy transfinite induction". I think I get what I am meant to do. Let $S$ be the set such that $a \in S$ if and only if there exists a bijection between $s(a)$ and $s(U(a))$. We need to prove that if $s(b) \subseteq S$, then $b \in S$. This would imply that $S = X$ by the transfinite induction principle. I assume I need to construct a bijection from $s(b)$ to $s(U(b))$ using the bijections for each $a < b$, but I am unsure of how to proceed with this.

Note that Halmos has not introduced the concept of ordinal numbers at this point in the book, only well-ordered sets. As a result, I'd appreciate any help which avoids the use of "ordinal terminology". There has been a question on the site that has asked about this before but I couldn't really make sense of the answers and comments.

EDIT: At the suggestion of the comments I decided to work through the following example:

$$ X = a > b > c > d \\ Y = e > f > g > h $$

Then starting at $a$ we have

$$ U(a) = e \\ U(b) = f \\ U(c) = g \\ U(d) = h \\ $$

I kind of understand how the proof works in these kind of instances as each element has an immediate predecessor. In this case, we can use the following argument. Any $x \in X$ has an immediate predecessor, say $x^{\prime}$ (apart from base case that is easy). So we must have $s(x) - \{x^{\prime}\} = s(x^{\prime})$. We construct an isomorphism by taking the isomorphism we know exists from $s(x^{\prime})$ to $s(U(x^{\prime}))$ and simply add the pair $(x^{\prime}, U(x^{\prime}))$.

However, I don't really understand what to do when an element of $X$ does not have an immediate predecessor. For example consider the set of positive integers $X$, where every odd is greater than every even. Then consider the set $Y$ of positive integers where every even is greater than every odd. In both sets order the odds with respect to each other as normal, and the evens with respect to each other as normal. So we have

$$ X = 2 < 4 < 6 < \dots < 1000< 1002 < \dots < 1 < 3 < \dots \\ Y = 1 < 3 < 5 < \dots < 1001 < 1003 < \dots < 2 < 4 < \dots $$

How does transfinite recursion deal with the case where $b = 1$ as $1$ has no immediate predecessor?

EDIT:

I think I understand the proof now. Either:

i) $b$ has an immediate predecessor $c$ in $s(b)$. In which case, all $a \in s(b) - \{c\}$ are mapped one-to-one into $U|_{s(c)}$ and thus $U|_{s(b)}$. By definition of $U$, $U(c) < U(b)$ and $U(c) > U(a)$ for all $a \in s(b) - \{c\}$, thus $U(c) \in s(U(b)$ and $U(c) \neq U(a)$ for all $a \in s(c)$. Hence $U|_{s(b)}$ is an injection into $s(U(b))$. Assume for the sake of contradiction that $U|_{s(b)}$ is not onto. Then there exists some $y$ such that $U(c) < y < U(b)$. However, then $U(b)$ would not be the least upper bound of $U|_{s(b)}$, thus we have a contradiction and no such $y$ can exist. So $U|_{s(b)}$ must map onto $s(U(b))$. Hence $U|_{s(b)}$ is a surjection and an injection and thus a bijection onto $s(U(b))$ as desired.

ii) $b$ has no immediate successor in $s(b)$. Then for every $a \in s(b)$ there exists another $c \in s(b)$ such that $a \in s(c)$. Observe that we can write $U|_{s(b)}$ as $\bigcup_{a \in s(b)}U|_{s(a)}$, and hence $U|_{s(b)}$ is an injection. Next we prove that $s(U(b))$ is in the range of $U|_{s(b)}$. For the sake of contradiction assume there is $y \in s(U(b))$ such that $y$ is not in the range of $U|_{s(b)}$. Then there are three cases that can occur:

1. $y$ is the least element in $s(U(b))$. Let $x$ be the least element in $X$. By definition of $U$ we must have $U(x) = y$. Hence $y$ is in the range of $U|_{s(b)}$ for all $b \neq x$. Since $U|_{s(x)} = \{\}$, this implies case (1) cant occur.

2. There are elements $a$ and $c$ in the range of $U|_{s(b)}$ such that $a < y < c$. However this would imply $y$ is not in the range of $U|_{s(c)}$, a contradiction. Thus case (2) can't occur.

3. $a < y$ for all $a \in s(U(b))$. In this case $U(b)$ is not the least upper bound of $U|_{s(b)}$, a contradiction by the definition of $U$. Thus case (3) can't occur.

So in all cases, we have a contradiction and thus $s(U(b))$ must lie in the range of $U|_{s(b)}$. Lastly we observe that the range of $U|_{s(b)}$ lies in $s(U(b))$. If it didn't then $U(b)$ would not be an upper bound for $U|_{s(b)}$. Thus we conclude that $U|_{s(b)}$ is a surjection onto $s(U(b))$. Thus as $U|_{(s(b)}$ is surjective and injective, it is bijection onto $s(U(b))$ as desired.

Thus for both cases $(i)$ and $(ii)$ the result holds and we are done.

Solution 1:

Let $(X_1,\le_1), (X_2,\le_2)$ be any well-orderings. If they are similar then call an order-isomorphism $f:X_1\to X_2$ a similarity.

(1).Lemma. The only similarity from a well-ordering from itself to itself is the identity function.

(2).Lemma. There is at most one similarity $f:X_1\to X_2$.

(3). Lemma. No well-ordering is similar to an initial segment of itself.

For $i\in\{1,2\}$ and $a\in X_i$ let pred$_i(a)=\{b: b<_i a\}.$ ("Pred" for "predecessors").

For $x\in X_1$ let $x\in X_1^*$ iff pred$_1(x)$ is similar to an initial segment of $X_2.$ For $x\in X_2$ let $x\in X_2^*$ iff pred$_2(x)$ is similar to an initial segment of $X_1$. The sets $X_1^*,X_2^*$ exist by the Axiom Schema of Comprehension.

If y$<_2y'$ then pred$_2(y)$ is an initial segment of pred$_2(y')$ so by (3), no pred$_1(x)$ can be similar to both pred$_2(y)$ and pred$_2(y').$ So for each $x\in X_1^*$ there is a unique $U(x)\in X_2$ such that pred$_1(x)$ is similar to pred$_2(U(x))$. And by (2), if $x\in X_1^*$ there is a unique similarity $f_x:$pred$_1(x)\to $ pred$_2(U(x)).$

Analogously, if $y\in X_2^*$ then there is a unique $V(y)\in X_1$ such that pred$_2(y)$ is similar to pred$_1(V(y)),$ and there is a unique similarity $g_y:\text{pred}_2(y)\to \text{ pred}_1(V(y)).$

The Axiom Schema of Replacement implies existence of the functions $U=\{(x,U(x)):x\in X_1^*\}$ and $V=\{(y,V(y)):y\in X_2^*\}.$

We can show by elementary considerations, without Recursion, that exactly one of the following holds:

(i)... $X_1^*=X_1$ and $X_2^*=X_2$ and $U:X_1\to X_2$ is a similarity.

(ii)...$X_1^*$ is an initial segment of $X_1$ and $X_2^*=X_2$ and $V:X_2\to X_1^*$ is a similarity.

(iii). $X_2^*$ is an initial segment of $X_2$ and $X_1^*=X_1$ and $U:X_1\to X_2^*$ is a similarity.