Comparability theorem for well ordered sets using transfinite recursion Similar questions have already been asked here and here. But I am asking for verification of my proof. Halmos leaves out an "easy" transfinite induction argument, which I have struggled to justify in a long and uneasy prose. Since Halmos mentioned it to be easy, I suspect it must be a slick argument, unlike what I have given. Hence, I am also looking for that.
Statement: Let $X$ and $Y$ be well ordered sets. Then they are either similar to each other, or else one is similar to an initial segment of the other.
My proof attempt:
Let none of $X$, $Y$ be similar to any initial segment of the other. Let $Y$ be nonempty. Then $f$ is a sequence function of type $X$ in $Y$, defined by $f(t)$ being $\min(Y)$ if $\mathrm{range}(t)$ has no proper upper bound, or else the least proper upper bound of $\mathrm{range} (t)$. Let $U\colon X\to Y$ be what transfinite induction associates with this $f$. We show that $U^a$ (this will be shorthand for $U\vert_{s(a)}$ as Halmos uses) is a bijection between $s(a)$ and $s(U(a))$ for all $a\in X$. Let $b\in X$ and let the above hold for all $a < b$.
Showing that $U^b$ is injective:
Let $a_1 < a_2 < b$. Then $U(a_1)\in\mathrm{range}(U^{a_2}) = s(U(a_2))$ and hence $U(a_1) < U(a_2)$.
Showing that $\mathrm{range}(U^b) = s(U(b))$:
Let $y\in s(U(b))\setminus\mathrm{range}(U^b)$. Then $U(a) < y$ for all $a < b$. (Otherwise $y\in s(U(a_0)) = \mathrm{range}(U^{a_0})\subseteq\mathrm{range}(U^b)$ for some $a_0 <  b$.) Hence $y$ is a proper upper bound for $\mathrm{range}(U^b)$ and hence $U(b)\le y$, a contradiction. Hence $s(U(b))\subseteq \mathrm{range}(U^b)$.
Let $y\in\mathrm{range}(U^b)\setminus s(U(b))$. Now, there can't be any proper upper bound for $\mathrm{range}(U^b)$, else $U(b) > y$, contradicting that $y\in s(U(b))$. In these circumstances, we show that $s(b)$ is similar to $Y$, reaching a contradiction and we will be done. Note that we have already shown that $U^b$ is injective as well as order-preserving. It just suffices to show that $Y\subseteq\mathrm{range}(U^b)$.
Let $\tilde y\in Y\setminus\mathrm{range}(U^b)$. We show that $\tilde y$ will hence be a proper upper bound for $\mathrm{range}(U^b)$ and hence get a contradiction. Let $a < b$. Suppose $U(a)\ge \tilde y$. Then $U(a) > \tilde y$ and hence $\tilde y\in s(U(a)) = \mathrm{range}(U^a)\subseteq\mathrm{range}(U^b)$, which is false. Hence we are done.$^1$
Now we show that $U$ is a similarity.
Injectivity and order preservation follow exactly like above. We show that $\mathrm{range}(U) = Y$. Suppose not, and let $y_0$ be the smallest element in $Y$ such that $y_0\in Y\setminus\mathrm{range}(U)$. In this case, we show that $X$ becomes similar to $s(y_0)$, reaching a contradiction. For this, suffice to show that $\mathrm{range}(U) = s(y_0)$. (Injectivity and order preservation already shown for $U$.) Let $y\in Y$. If $y\in s(y_0)$, then $y < y_0$ and hence $y\in\mathrm{range}(U)$. To show other inclusion, suppose that $y\in\mathrm{range}(U)\setminus s(y_0)$. Then $y = U(a)$ for some $a\in X$, and $y > y_0$. Hence, $y_0\in s(U(a)) = \mathrm{range}(U^a)\subseteq\mathrm{range}(U)$, which is false.

$^1$That was a contradiction within a contradiction within a contradiction with a contradiction (4 times)! Phew.
 A: Here is an alternate form of essentially the same proof.
Consider the set $\scr U$ of all subsets $U \subset X \times Y$ which satisfy the following properties:

*

*if $(u,v) \in U$ and $x < u$ in $X$, then there is some $y \in Y$ with $(x,y) \in U$.

*if $(u,v) \in U$ and $y < v$ in $Y$, then there is some $x \in X$ with $(x,y) \in U$.

*if $(u,v), (x,y) \in U$, then $x < u \iff y < v$.

Then

*

*$\emptyset \in \scr U$

*if $U \in \scr U$, with $\pi_1(U) \ne X, \pi_2(U) \ne Y$, then $U\cup \{(\min X\setminus \pi_1(U), \min Y \setminus \pi_2(U))\}$ is also in $\scr U$.

*If $U, V \in \scr U$, then either $U \subseteq V$ or $V \subseteq U$.

*$\bigcup \mathscr U = \{ (u,v) \mid \exists U \in \mathscr U, (u,v) \in U \}$ is in $\scr U$.

The key condition is the third one, which is about as hard to show as your $\operatorname{range}(U^b)=s(U(b))$ proof. The others follow easily. If $U' = \bigcup \scr U$, then either $\pi_1(U') = X$ or $\pi_2(U') = Y$. Otherwise by the second result above, $U'$ would be contained in some larger element of $\scr U$, which is impossible. Thus per condition 3, $U'$ is a bijection, either between $X$ and some subset of $Y$ (per condition 2, an initial segment), or between some subset of $X$ (per condition 1, an initial segment) and $Y$.
