[proofplan] From $X \leq Y$ and $Y \leq X$ we have order-preserving injections $f: X \to Y$ and $g: Y \to X$ onto initial segments. The composition $g \circ f: X \to X$ is an order-preserving injection of $X$ into itself, and its image is an initial segment of $X$. The key rigidity principle — that a well-ordering admits no order-isomorphism with a proper initial segment of itself — forces $g \circ f$ to be surjective, hence bijective. The same argument gives $f \circ g$ bijective. From the two composition bijectivities we deduce that $f$ and $g$ are themselves bijective, hence order-isomorphisms. [/proofplan] [step:Establish a rigidity lemma — no well-ordering is isomorphic to a proper initial segment of itself] Recall that we call a subset $Y \subsetneq X$ of a well-ordering $(X, <)$ a *proper initial segment* if $Y$ is downward closed and not all of $X$. By the [characterisation of initial segments](/theorems/1462), every proper initial segment is of the form $I_a = \{y \in X : y < a\}$ for a unique $a \in X$. [claim:No order-preserving injection $\varphi: X \to X$ sends $X$ into a proper initial segment of itself] Let $(X, <)$ be a well-ordering and $\varphi: X \to X$ an order-preserving injection. Then $\varphi(x) \geq x$ for every $x \in X$, so the image of $\varphi$ cannot be contained in any proper initial segment $I_a$. [/claim] [proof] Let $S := \{x \in X : \varphi(x) < x\}$ and suppose $S \neq \varnothing$. Let $x_0 := \min_X S$; this exists because $X$ is a well-ordering. Set $x_1 := \varphi(x_0)$. By definition of $S$, $x_1 < x_0$, so $x_1 \notin S$ by minimality of $x_0$; that is, $\varphi(x_1) \geq x_1$. On the other hand, $\varphi$ is order-preserving and injective, so $x_1 < x_0$ implies $\varphi(x_1) < \varphi(x_0) = x_1$. This contradicts $\varphi(x_1) \geq x_1$. Hence $S = \varnothing$, i.e., $\varphi(x) \geq x$ for all $x \in X$. In particular, $\varphi$ cannot map $X$ into any $I_a = \{y : y < a\}$, because $\varphi(a) \geq a$ and $a \notin I_a$. [/proof] [guided] The statement of the rigidity lemma is that an order-preserving self-injection of a well-ordering is "expansive": $\varphi(x) \geq x$. The consequence is that the image of $\varphi$ contains $a$ for every $a \in X$ in the sense that $\varphi(a) \geq a$, so the image cannot be confined to a proper initial segment. How could the lemma fail? Only if some $x \in X$ has $\varphi(x) < x$. Well-ordering gives us a *least* such offender: $x_0 = \min S$ where $S = \{x : \varphi(x) < x\}$. Now the proof exploits the minimality two ways. First, $x_1 = \varphi(x_0)$ satisfies $x_1 < x_0$, so $x_1$ is *below* the least offender and therefore cannot itself be an offender: $\varphi(x_1) \geq x_1$. Second, $\varphi$ is order-preserving and injective, so strictly monotone: $x_1 < x_0 \Rightarrow \varphi(x_1) < \varphi(x_0) = x_1$. The two conclusions contradict each other, so $S$ was empty: no offenders, $\varphi(x) \geq x$ everywhere. In particular, for every $a \in X$, $\varphi(a) \geq a$, so $\varphi(a) \notin I_a$, meaning $\varphi$ cannot send $X$ into the proper initial segment $I_a$. [/guided] [/step] [step:Unpack the hypotheses into order-preserving injections whose images are initial segments] The relation $X \leq Y$ between well-orderings means there exists an order-preserving bijection from $X$ onto an initial segment of $Y$. Equivalently, there exists an order-preserving injection $f: X \to Y$ whose image $f(X)$ is an initial segment of $Y$. From $X \leq Y$: fix an order-preserving injection $f: X \to Y$ with $f(X)$ an initial segment of $Y$. From $Y \leq X$: fix an order-preserving injection $g: Y \to X$ with $g(Y)$ an initial segment of $X$. [/step] [step:Show that $g \circ f: X \to X$ is a bijection] The composition $g \circ f: X \to X$ is: - *Order-preserving*: the composition of two order-preserving maps is order-preserving. For $x_1 <_X x_2$, $f(x_1) <_Y f(x_2)$, hence $g(f(x_1)) <_X g(f(x_2))$. - *Injective*: the composition of two injections is an injection. - *Image is an initial segment of $X$*: we show $(g \circ f)(X) = g(f(X))$ is downward closed in $X$. Let $b = g(f(x_0))$ and suppose $c <_X b$. Since $g(Y)$ is an initial segment of $X$ and $b \in g(Y)$, downward closure gives $c \in g(Y)$, so $c = g(y)$ for some $y \in Y$. Because $g$ is order-preserving and injective (hence strictly increasing) and $g(y) = c <_X b = g(f(x_0))$, we have $y <_Y f(x_0)$. Since $f(X)$ is an initial segment of $Y$ and $f(x_0) \in f(X)$, downward closure gives $y \in f(X)$, so $y = f(x)$ for some $x \in X$. Then $c = g(y) = g(f(x)) \in g(f(X))$, as required. By the rigidity claim in the first step, an order-preserving injection $\varphi: X \to X$ cannot have image contained in a proper initial segment of $X$. Since $(g \circ f)(X)$ is an initial segment of $X$ that contains $(g \circ f)(X)$, it cannot be proper — it must be all of $X$. Hence $g \circ f: X \to X$ is surjective, and combined with injectivity it is a bijection. [guided] We want to apply the rigidity lemma to $g \circ f: X \to X$. The lemma has two hypotheses: the map is order-preserving, and it is a self-map of a well-ordering. The conclusion says the image cannot sit inside a proper initial segment. So we need (a) order-preserving (b) the image is *some* initial segment, and then (c) rigidity will upgrade this to "the full set". *(a) $g \circ f$ is order-preserving.* Compositions of order-preserving maps are order-preserving. If $x_1 <_X x_2$, first $f(x_1) <_Y f(x_2)$, then $g(f(x_1)) <_X g(f(x_2))$. *(b) The image $g(f(X))$ is an initial segment of $X$.* We show it is downward closed. Take any $b = g(f(x_0))$ and $c <_X b$. Since $b \in g(Y)$ and $g(Y)$ is an initial segment of $X$, any element below $b$ is also in $g(Y)$. So $c = g(y)$ for some (unique) $y \in Y$. Now, $g$ being order-preserving and injective means it is strictly increasing: $g(y) <_X g(f(x_0))$ forces $y <_Y f(x_0)$. Since $f(x_0) \in f(X)$ and $f(X)$ is an initial segment of $Y$, any $y <_Y f(x_0)$ is also in $f(X)$, so $y = f(x)$ for some $x$. Then $c = g(y) = g(f(x))$ is in the image of $g \circ f$. *(c) Rigidity closes the argument.* The rigidity lemma says that a self-embedding $\varphi: X \to X$ of a well-ordering satisfies $\varphi(x) \geq x$. If $(g \circ f)(X)$ were a proper initial segment, say $I_a$, then $g(f(a)) \in I_a$, meaning $g(f(a)) < a$. But the lemma gives $g(f(a)) \geq a$. Contradiction. So $(g \circ f)(X)$ is not a proper initial segment; the only alternative is $(g \circ f)(X) = X$, i.e., surjective. With injectivity already in hand, $g \circ f$ is a bijection. [/guided] [/step] [step:Show that $f \circ g: Y \to Y$ is a bijection by symmetry] The argument is identical with the roles of $X, Y, f, g$ swapped. The map $f \circ g: Y \to Y$ is order-preserving (composition of order-preserving maps), injective (composition of injections), and has image $f(g(Y))$ which is an initial segment of $Y$ — the proof mirrors the previous step: $f(g(Y)) \subseteq f(X)$ which is an initial segment of $Y$, and downward closure of $f(g(Y))$ follows from downward closure of both $g(Y)$ in $X$ and $f(X)$ in $Y$ as in the previous step with $f, g$ swapped. Applying the rigidity claim to $f \circ g: Y \to Y$, its image must be all of $Y$, so $f \circ g$ is surjective, hence bijective. [/step] [step:Deduce that $f$ and $g$ are bijections] From $g \circ f$ bijective, $f$ is injective (already known) and $g$ is surjective: for any $a \in X$ there is $x \in X$ with $g(f(x)) = a$, so $a \in g(Y)$. Similarly, from $f \circ g$ bijective, $f$ is surjective: for any $b \in Y$ there is $y \in Y$ with $f(g(y)) = b$, so $b \in f(X)$. Thus $f: X \to Y$ is an order-preserving bijection. The inverse of an order-preserving bijection between totally ordered sets is automatically order-preserving: if $b_1 <_Y b_2$ and $f^{-1}(b_1), f^{-1}(b_2) \in X$ satisfied $f^{-1}(b_1) \geq_X f^{-1}(b_2)$, then $b_1 = f(f^{-1}(b_1)) \geq_Y f(f^{-1}(b_2)) = b_2$ (using $f$ order-preserving, with equality only if $f^{-1}(b_1) = f^{-1}(b_2)$, impossible since $b_1 \neq b_2$), contradicting $b_1 <_Y b_2$. Therefore $f$ is an order-isomorphism from $X$ to $Y$, so $X$ and $Y$ are isomorphic as well-orderings. [/step]