[proofplan] We compare the two well-orders by taking the union of all order-isomorphisms between initial segments of $A$ and initial segments of $B$. The key point is that any two such partial comparisons agree on their common domain, so the union is a single order-isomorphism between two initial segments. If both sides still have unused elements, the least unused elements extend the comparison, contradicting maximality of the union. Therefore one side, or both sides, is exhausted; this gives the three alternatives, and [rigidity of well-orders](/theorems/4807) rules out overlap among them. [/proofplan] [step:Show that partial isomorphisms between initial segments agree where both are defined] Let $\mathcal{C}$ denote the collection of all order-isomorphisms \begin{align*} f: I_f &\to J_f \end{align*} where $I_f \subset A$ is an initial segment of $(A,<_{A})$ and $J_f \subset B$ is an initial segment of $(B,<_{B})$. The empty function belongs to $\mathcal{C}$, taking $I_f=\varnothing$ and $J_f=\varnothing$. We first prove that if $f,g \in \mathcal{C}$, then $f(a)=g(a)$ for every $a \in I_f \cap I_g$. Suppose not. Since $I_f \cap I_g$ is an initial segment of the well-ordered set $A$, the set \begin{align*} E := \{a \in I_f \cap I_g : f(a) \neq g(a)\} \end{align*} has a $<_{A}$-least element $a_0$. Assume first that $f(a_0) <_{B} g(a_0)$. Since $g(a_0) \in J_g$ and $J_g$ is an initial segment of $B$, we have $f(a_0) \in J_g$. Since $g: I_g \to J_g$ is surjective, there exists $x \in I_g$ such that $g(x)=f(a_0)$. Because $g$ is order-preserving and $g(x)<_{B}g(a_0)$, we get $x<_{A}a_0$. Since $I_f$ is an initial segment and $a_0 \in I_f$, this gives $x \in I_f$. By the minimality of $a_0$, we have $f(x)=g(x)=f(a_0)$, contradicting injectivity of $f$ because $x<_{A}a_0$. It remains to treat the case $g(a_0)<_{B}f(a_0)$. Since $f(a_0) \in J_f$ and $J_f$ is an initial segment of $B$, we have $g(a_0) \in J_f$. Since $f: I_f \to J_f$ is surjective, there exists $y \in I_f$ such that $f(y)=g(a_0)$. Because $f$ is order-preserving and $f(y)<_{B}f(a_0)$, we get $y<_{A}a_0$. Since $I_g$ is an initial segment and $a_0 \in I_g$, this gives $y \in I_g$. By the minimality of $a_0$, we have $g(y)=f(y)=g(a_0)$, contradicting injectivity of $g$ because $y<_{A}a_0$. Hence no such $a_0$ exists, and the two partial isomorphisms agree on their common domain. [guided] The obstacle in forming a union of partial maps is possible disagreement: two order-isomorphisms between initial segments might both be defined at the same point of $A$. We rule this out by using the well-order on $A$ to look at the first possible disagreement. Let $f,g \in \mathcal{C}$. Thus \begin{align*} f: I_f &\to J_f, & g: I_g &\to J_g \end{align*} are order-isomorphisms, where $I_f,I_g$ are initial segments of $A$ and $J_f,J_g$ are initial segments of $B$. Suppose that $f$ and $g$ disagree somewhere on $I_f \cap I_g$. Define \begin{align*} E := \{a \in I_f \cap I_g : f(a) \neq g(a)\}. \end{align*} Since $A$ is well-ordered and $E \subset A$ is nonempty, $E$ has a least element; call it $a_0$. There are two possible orders between $f(a_0)$ and $g(a_0)$ in the linear order $B$. Suppose $f(a_0)<_{B}g(a_0)$. Because $g(a_0)$ lies in the initial segment $J_g$, every smaller element of $B$ also lies in $J_g$; hence $f(a_0)\in J_g$. Since $g$ maps $I_g$ onto $J_g$, there exists $x\in I_g$ with \begin{align*} g(x)=f(a_0). \end{align*} Now $g(x)<_{B}g(a_0)$, and $g$ is order-preserving, so $x<_{A}a_0$. Since $a_0\in I_f$ and $I_f$ is an initial segment, this also gives $x\in I_f$. The point $x$ lies before the first disagreement $a_0$, so $f(x)=g(x)$. Therefore \begin{align*} f(x)=g(x)=f(a_0), \end{align*} which contradicts injectivity of $f$ because $x<_{A}a_0$. Now suppose instead that $g(a_0)<_{B}f(a_0)$. Because $f(a_0)$ lies in the initial segment $J_f$, every smaller element of $B$ also lies in $J_f$; hence $g(a_0)\in J_f$. Since $f$ maps $I_f$ onto $J_f$, there exists $y\in I_f$ with \begin{align*} f(y)=g(a_0). \end{align*} Now $f(y)<_{B}f(a_0)$, and $f$ is order-preserving, so $y<_{A}a_0$. Since $a_0\in I_g$ and $I_g$ is an initial segment, this also gives $y\in I_g$. The point $y$ lies before the first disagreement $a_0$, so $g(y)=f(y)$. Therefore \begin{align*} g(y)=f(y)=g(a_0), \end{align*} which contradicts injectivity of $g$ because $y<_{A}a_0$. Therefore no first disagreement exists, and $f(a)=g(a)$ for every $a\in I_f\cap I_g$. [/guided] [/step] [step:Take the union of all partial comparisons] Define \begin{align*} F := \bigcup_{f\in\mathcal{C}} f \end{align*} as a subset of $A\times B$. By the previous step, $F$ is the graph of a function. Let \begin{align*} D &:= \{a\in A : \text{there exists } b\in B \text{ with } (a,b)\in F\},\\ R &:= \{b\in B : \text{there exists } a\in A \text{ with } (a,b)\in F\}. \end{align*} Then $D$ is the union of the initial segments $I_f$ with $f\in\mathcal{C}$, and $R$ is the union of the initial segments $J_f$ with $f\in\mathcal{C}$. Hence $D$ is an initial segment of $A$ and $R$ is an initial segment of $B$: for instance, if $a\in D$ and $x<_{A}a$, then $a\in I_f$ for some $f\in\mathcal{C}$, and the initial-segment property of $I_f$ gives $x\in I_f\subset D$; the proof for $R$ is the same with $B$ in place of $A$. We regard $F$ as the map \begin{align*} F: D &\to R. \end{align*} It is surjective by the definition of $R$. We shall use the following one-line fact: if $I$ and $K$ are initial segments of a linear order, then $I\subset K$ or $K\subset I$. Indeed, if $I\not\subset K$, choose $x\in I\setminus K$; then every $y\in K$ must satisfy $y<x$, since $x<y$ would force $x\in K$ by the initial-segment property of $K$, and therefore $y\in I$ by the initial-segment property of $I$. The map $F$ is injective because if $F(a_1)=F(a_2)$, choose $f_1,f_2\in\mathcal{C}$ with $a_1\in I_{f_1}$ and $a_2\in I_{f_2}$. By comparability of initial segments, one of $I_{f_1},I_{f_2}$ contains the other. A member of $\mathcal{C}$ whose domain contains both $a_1$ and $a_2$ then shows $a_1=a_2$ by injectivity of that member. The same comparability of initial segments shows that if $a_1<_{A}a_2$ in $D$, then a single member of $\mathcal{C}$ contains both points in its domain, and therefore \begin{align*} F(a_1)<_{B}F(a_2). \end{align*} To verify order preservation of the inverse direction, let $b_1,b_2\in R$ with $b_1<_{B}b_2$. Choose $f_1,f_2\in\mathcal{C}$ and $a_1\in I_{f_1}$, $a_2\in I_{f_2}$ such that $f_1(a_1)=b_1$ and $f_2(a_2)=b_2$. By comparability of the initial segments $J_{f_1}$ and $J_{f_2}$ of $B$, one of them contains the other, so there is a member $f\in\mathcal{C}$ whose range contains both $b_1$ and $b_2$. Since $f$ is an order-isomorphism, its inverse $f^{-1}:J_f\to I_f$ is order-preserving; hence \begin{align*} F^{-1}(b_1)=f^{-1}(b_1)<_{A}f^{-1}(b_2)=F^{-1}(b_2). \end{align*} Thus $F:D\to R$ is an order-isomorphism between initial segments. [/step] [step:Extend the comparison unless one side is exhausted] We claim that at least one of $D=A$ or $R=B$ holds. Suppose instead that $D\neq A$ and $R\neq B$. Since $A$ and $B$ are well-ordered, the complements $A\setminus D$ and $B\setminus R$ have least elements. Define \begin{align*} a_0 &:= \min(A\setminus D), & b_0 &:= \min(B\setminus R). \end{align*} Because $D$ is an initial segment and $a_0$ is the least element outside $D$, every element of $D$ is $<_{A}a_0$, and every element $a<_{A}a_0$ belongs to $D$. Hence $D\cup\{a_0\}$ is an initial segment of $A$. Similarly, $R\cup\{b_0\}$ is an initial segment of $B$. Define \begin{align*} \widetilde{F}: D\cup\{a_0\} &\to R\cup\{b_0\} \end{align*} by $\widetilde{F}(a)=F(a)$ for $a\in D$ and $\widetilde{F}(a_0)=b_0$. Since every element of $D$ is below $a_0$ and every element of $R$ is below $b_0$, the map $\widetilde{F}$ is an order-isomorphism between initial segments. Thus $\widetilde{F}\in\mathcal{C}$, so its graph is contained in the union $F$. In particular $a_0\in D$, contradicting $a_0\in A\setminus D$. Therefore $D=A$ or $R=B$. [/step] [step:Read off the three possible outcomes] If $D=A$ and $R=B$, then \begin{align*} F: A &\to B \end{align*} is an order-isomorphism, giving the first alternative. If $D=A$ and $R\neq B$, let \begin{align*} b_0 := \min(B\setminus R). \end{align*} The initial-segment property and the minimality of $b_0$ imply \begin{align*} R=\{b\in B: b<_{B}b_0\}. \end{align*} Thus $R$ is a proper initial segment of $B$, and $F:A\to R$ is an order-isomorphism. This gives the second alternative. If $D\neq A$ and $R=B$, let \begin{align*} a_0 := \min(A\setminus D). \end{align*} Then \begin{align*} D=\{a\in A: a<_{A}a_0\}, \end{align*} so $D$ is a proper initial segment of $A$, and $F:D\to B$ is an order-isomorphism. Equivalently, $B$ is order-isomorphic to the proper initial segment $D$ of $A$. This gives the third alternative. [/step] [step:Use rigidity of well-orders to prove that the alternatives are mutually exclusive] We first record the rigidity fact needed for exclusivity: no well-ordered set is order-isomorphic to a proper initial segment of itself. Let $(X,<_{X})$ be a well-ordered set, let $I\subsetneq X$ be an initial segment, and suppose toward contradiction that \begin{align*} h:X&\to I \end{align*} is an order-isomorphism. Let \begin{align*} c:=\min(X\setminus I). \end{align*} Then $I=\{x\in X:x<_{X}c\}$. We show first that $h(x)=x$ for every $x<_{X}c$. If not, let $x_0<_{X}c$ be the least element with $h(x_0)\neq x_0$. If $h(x_0)<_{X}x_0$, then $h(x_0)<_{X}c$, so by minimality $h(h(x_0))=h(x_0)$; injectivity of $h$ gives $h(x_0)=x_0$, a contradiction. If $x_0<_{X}h(x_0)$, then since $x_0\in I$ and $h$ is onto $I$, there exists $z\in X$ with $h(z)=x_0$. The possibilities $z<_{X}x_0$ and $z=x_0$ contradict respectively the minimality of $x_0$ and the assumption $x_0<_{X}h(x_0)$. Hence $x_0<_{X}z$, and order preservation gives \begin{align*} h(x_0)<_{X}h(z)=x_0, \end{align*} contradicting $x_0<_{X}h(x_0)$. Therefore $h(x)=x$ for all $x<_{X}c$. But $h(c)\in I$, so $h(c)<_{X}c$. The preceding paragraph gives $h(h(c))=h(c)$, and injectivity of $h$ gives $h(c)=c$, contradicting $h(c)<_{X}c$. This proves the rigidity fact. Now suppose two of the three alternatives held. If $A$ were order-isomorphic to $B$ and also to a proper initial segment of $B$, then composing an isomorphism $B\to A$ with an isomorphism $A\to I$, where $I\subsetneq B$ is an initial segment, would make $B$ order-isomorphic to the proper initial segment $I$ of itself, contradicting rigidity. The same argument excludes the simultaneous truth of the first and third alternatives. Finally, suppose the second and third alternatives both held. Let $I\subsetneq B$ be an initial segment and let $\phi:A\to I$ be an order-isomorphism. Let $J\subsetneq A$ be an initial segment and let $\psi:B\to J$ be an order-isomorphism. Then $\psi(I)$ is an initial segment of $J$, hence an initial segment of $A$: if $x\in\psi(I)$ and $y<_{A}x$, then $x\in J$ and the initial-segment property of $J$ gives $y\in J$; writing $y=\psi(b)$ and $x=\psi(i)$ with $b\in B$ and $i\in I$, order preservation of $\psi^{-1}:J\to B$ gives $b<i$, so $b\in I$ and hence $y\in\psi(I)$. Also $\psi(I)\subsetneq A$ because $\psi(I)\subset J\subsetneq A$. The composition $\psi\circ\phi:A\to\psi(I)$ is therefore an order-isomorphism from $A$ onto a proper initial segment of itself, contradicting rigidity. Thus the three alternatives are mutually exclusive. Since the preceding steps showed that at least one alternative holds, exactly one holds. [/step]