The unique isomorphism between well-ordered sets

order-theoryproof-verification

This is an important theorem so I try to give it a shot by myself. Does it look fine or contain flaws. I'm pleased to receive suggestion!


Definition: Let $(W, <)$ be a linearly ordered set. $I$ is an initial segment of $W$ $\iff$ $I\subsetneq W$ and $\forall a \in I:x < a\implies x\in I$.

Theorem: Let $(W_1,<_1)$ and $(W_2,<_2)$ be well-ordered sets. Then exactly one of the following statements must hold.

(1) $W_1$ and $W_2$ are isomorphic

(2) $W_1$ is isomorphic to an initial segment of $W_2$

(3) $W_2$ is isomorphic to an initial segment of $W_1$

In each case, the isomorphism is unique.


My attempt:

Lemma 1: Suppose that $(W,<)$ is well-ordered and that $I$ is an initial segment of $W$. Then $I=\{x\in W\mid x<a\}$ for a unique $a\in W$.

Proof: It is easy to verify this Lemma.

As a result, $W[a]:=\{x\in W\mid x<a\}$ is called the initial segment of $W$ given by $a$.

Lemma 2: Suppose that $(W,<)$ is well-ordered and that $f:W\to W$ is an increasing mapping. Then $f(x)\ge x$ for all $x\in W$.

Proof: If $X=\{x\in W\mid f(x)<x\}\neq \emptyset$, then $X$ has a least element $a$. It follows that $f(a)<a$ and thus $f(f(a))<f(a)$. Then $f(a)\in X$ and $f(a)<a$. This contradicts the minimality of $a$.

Lemma 3: No well-ordered set is isomorphic to an initial segment of itself.

Proof: Assume the contrary that $f$ is an isomorphism between $W$ and $W[a]$ for some $a \in W$. Then $f$ is an increasing function from $W$ to $W[a]$ and thus $\forall x\in W:f(x)\ge x$ by Lemma 2. On the other hand, $f(a)\in W[a]$ and thus $f(a)<a$. This is a contradiction.

Lemma 4: Each well-ordered set has only one automorphism, the identity mapping.

Proof: Let $f$ be an automorphism of $W$. Then $f^{-1}$ is an automorphism of $W$. It follows that $\forall x\in W: f(x)\ge x$ and $f^{-1}(x)\ge x$ by Lemma 2. Then $\forall x\in W: f(x)\ge x$ and $x\ge f(x)$. Hence $\forall x\in W:f(x)=x$ and thus $f=\operatorname{Id}_{W}$.

Lemma 5: Suppose that $(W_1,<_1)$ and $(W_2,<_2)$ are well-ordered and are isomorphic. Then the isomorphism between $W_1$ and $W_2$ is unique.

Proof: Let $f$ and $g$ be isomorphisms between $W_1$ and $W_2$. Then $g^{-1}$ is an isomorphism between $W_2$ and $W_1$. It follows that $f\circ g^{-1}$ is an automorphism of $W_2$ by Lemma 4. Then $f\circ g^{-1}=\operatorname{Id}_{W_2}$ and thus $f=g$.


We proceed to prove our main theorem.

Uniqueness of the isomorphism

  • $W_1$ and $W_2$ are isomorphic

The uniqueness is asserted by Lemma 5.

  • $W_1$ is isomorphic to an initial segment of $W_2$

Suppose that $W_1$ is isomorphic to $W_2[a_2]$ for some $a_2\in W_2$ and to $W_2[a'_2]$ for some $a'_2\in W_2$ where $a_2<_2 a'_2$. It follows that $W_2[a_2]$ is isomorphic to $W_2[a'_2]$ where $W_2[a_2]$ is an initial segment of $W_2[a'_2]$. This contradicts Lemma 3.

  • $W_2$ is isomorphic to an initial segment of $W_1$

This case is similar to the previous one.

Mutual Exclusiveness

  • (1) and (2) both happen

Then $W_2$ is isomorphic to an initial segment of $W_2$. This contradicts Lemma 3.

  • (1) and (3) both happen

Then $W_1$ is isomorphic to an initial segment of $W_1$. This contradicts Lemma 3.

  • (2) and (3) both happen

Then $W_1$ is isomorphic to an initial segment of $W_1$. This contradicts Lemma 3.

Existence

We define a relation $f$ as follows $$f=\{(x,y)\in W_1\times W_2\mid W_1[x] \text{ is isomorphic to } W_2[y]\}$$

  1. $f$ is a mapping

If $(x,y),(x,y')\in f$, then $W_1[x]$ is isomorphic to $W_2[y]$ and $W_1[x]$ is isomorphic to $W_2[y']$. Then $W_2[y]$ is isomorphic to $W_2[y']$. Hence $y=y'$ by Lemma 3.

  1. $f$ is injective

If $(x,y),(x',y)\in f$, then $W_1[x]$ is isomorphic to $W_2[y]$ and $W_1[x']$ is isomorphic to $W_2[y]$. Then $W_2[x]$ is isomorphic to $W_2[x']$. Hence $x=x'$ by Lemma 3.

  1. $\forall x,x'\in W_1:x<_1 x'\implies f(x)<_2 f(x')$

Let $h$ be the isomorphism between $W_1[x']$ and $W_2[f(x')]$. Then $h\restriction W_1[x]$ is the isomorphism between $W_1[x]$ and $h[W_1[x]]$. Then $h[W_1[x]]$ and $W_2[f(x)]$ are isomorphic, whereas $h[W_1[x]]$ and $W_2[f(x)]$ are both initial segments of $W_2$. Then $h[W_1[x]]=W_2[f(x)]$ by Lemma 3.

$x<_1 x' \implies W_1[x] \subsetneq W_1[x'] \implies h[W_1[x]] \subsetneq h[W_1[x']] \implies h[W_1[x]] \subsetneq W_2[f(x')] \implies W_2[f(x)] \subsetneq W_2[f(x')] \implies f(x)<_2 f(x').$

From 1, 2, and 3, $f$ is an isomorphism between $\operatorname{dom}f$, a subset of $W_1$ and $\operatorname{ran}f$, a subset of $W_2$.

  • $\operatorname{dom}f=W_1$

Then $f$ is an isomorphism either between $W_1$ and $W_2$, or between $W_1$ and an initial segment of $W_2$.

  • $\operatorname{dom}f\neq W_1$

For $x\in\operatorname{dom}f$ and $z <_1 x$: Let $h$ be an isomorphism between $W_1[x]$ and $W_2[f(x)]$. Then $h\restriction W_1[z]$ is the isomorphism between $W_1[z]$ and $h[W_1[z]]$. Then $z\in \operatorname{dom}f$. This result combining with the fact that $\operatorname{dom}f\neq W_1$ implies $\operatorname{dom}f$ is an initial segment of $W_1$.

Assume the contrary that $\operatorname{ran}f\neq W_2$. By similar reasoning: $\operatorname{ran}f$ is an initial segment of $W_2$. It follows that $\operatorname{dom}f=W_1[a]$ for some $a\in W_1$ and $\operatorname{ran}f=W_2[b]$ for some $b\in W_2$. Hence $f$ is the isomorphism between $W_1[a]$ and $W_2[b]$. This implies $a\in\operatorname{dom}f=W_1[a]$ and thus $a<a$. This is a contradiction. Hence $\operatorname{ran}f=W_2$.

Best Answer

I think the proof of unique order isomorphism can be simpler.

Let $W, Y$ be well ordered sets and $f,g : W \rightarrow Y$ be order isomorphisms. By definition $f, g$ are bijective and preserve order between $W$ and $Y$.

Let $A := \{w \in W | f(w) \neq g(w)\}$. $A$ itself is well ordered, hence it has a least element say $a$. We have $a \in A$. Suppose $f(a) < g(a)$. As g is bijective $$\exists a' \in W, g(a') = f(a) \\ \implies g(a') <g(a) \\ \implies a' < a \\ \implies f(a') < f(a) \\ \implies f(a') < g(a') \\ \implies a' \in A \;\;\;\;\text{a contradiction.}$$ Hence $A = \phi$ and $\forall w \in W, f(w) = g(w)$.

Related Question