Logical question while trying to prove a theorem about comparing well-ordered sets

Question

I'm reading Set theory of Jech. I try to prove Thm 2.8 for myself but I'm not sure if the first step of my proof is correct. So the theorem affirms that if $W_1$ and $W_2$ are two well-ordered sets, then exactly one of the three cases holds：i) $W_1$ is isomorphic to $W_2$, ii) $W_1$ is isomorphic to an initial segment of $W_2$, iii)$W_2$ is isomorphic to an initial segment of $W_1$.

I want to define a function that maps the least element $x_1$ of $W_1$ to least element $y_1$ of $W_2$, and then the least element $x_2$ of $W_1\backslash \{x_1\}$ to least element $y_2$ of $W_2\backslash \{y_1\}$, and continue like this until of one the sets $W_1$ and $W_2$ is exhausted.

But I'm not sure if the above definition works if both of the sets $W_1$ and $W_2$ are uncountable (otherwise I could use induction). That is, I don't know if I can really reach the last step where either all elements of $W_1$ are taken or all elements of $W_2$ are taken.

Could you tell me if this is correct and why? Thanks!

Answer 1

Define $f:W_1\to W_2$ recursively by setting $$ f(\min W_1) = \min W_2 \quad\text{and}\quad f(x) = \min (W_2\setminus f(I_x)),\ x\in W_1,$$ where $I_x:=\{y\in W_1 \mid y<x\}$ is the initial segment of $x$. From here there are a few things to worry about:

1) How do we know that $W_2\setminus f(I_x)$ is nonempty? We should first assume that $W_2$ is not isomorphic to an initial segment of $W_1$.

2) How do we know that defining a function recursively like this is valid? It's certainly intuitive, but the details can get a bit messy (especially when we jump to transfinite recursion).

3) Once we accept that $f$ is a well-defined function, then we need to show that it is an order isomorphism.

---

If you assume choice (thanks Henning Makholm), then I recommend trying an argument by Zorn's lemma. The ideas you have with using transfinite induction are great, but the beauty of Zorn's lemma is that you can avoid these obstructions.

Answer 2

You're right that the procedure you describe may fail to exhaust all elements of $W_1$ and $W_2$ if they are infinite (they don't even have to be uncountable). Instead, how about something like this:

Call a partial function from $W_1$ to $W_2$ "good" if it is an order isomorphism from an initial segment of $W_1$ to an initial segment of $W_2$.

Prove that any two good functions agree on the intersection of their domains. (Namely, there cannot be a first element that they disagree on).

The union of all good maps is therefore a partial function $W_1\to W_2$. Prove that it is itself a good map. Call it $f$.

Now either the domain of $f$ is all of $W_1$ or its range is all of $W_2$. (Otherwise we could map the first unused element of $W_1$ to the first unused element of $W_2$ and get a larger good function, contradicting the fact that $f$ is the union of all good functions).

But this means exactly that we're in one of the three situations in your claim.

Answer 3

First, a few preliminary results: If $<_A$ is a well-order on A then (1).There is no order-isomorphism $f$ from $A$ onto a proper initial segment of $A.$ (Consider the least $a\in A$ such that $f(a)<a.$ )... (2). The only isomorphism from $A$ onto $A$ is $id_A.$ (Consider the least $a\in A$ such that $f(a)\ne a$ and consider $f^{-1}a.$)... (3). If $(A,<_A)$ and $(B,<_B)$ are well-orders and $f,g$ are isomophisms from $A$ onto $B$ then $f=g.$ (Consider that $g^{-1}f$ is an isomorphim of $A$ onto $A$ and apply (2).)

Let $(A,<_A)$ and $(B,<_B)$ be well-orders.

For $a\in A$ let $(-,a]_A=\{a'\in A: a'<_A a \lor a'=a\}.$

For $b\in B$ let $(-,b]_B=\{b'\in B: b'<_B b \lor b'=b\}.$

Let $A'$ be the set of those $a\in A$ for which there exists an order-isomorphism $f_a:(-,a]_A\to (-,b]_B$ for some $b\in B.$

Let $B'$ be the set of those $b\in B$ for which there exists an order-isomorphism $g_b:(-,b]_B\to (-,a]_A$ for some $a\in A.$

We can readily show that $A'=A$ or $A'=(-,a]_A\setminus \{a\}$ for some $a\in A,$ and that $B'=B$ or $B'=(-,b]\setminus \{b\}$ for some $b\in B.$

From (1),(2), and (3) if $a\in A'$ then $f_a$ is unique, and if $b\in B'$ then $f_b$ is unique. So by the Axiom of Replacement we obtain the sets $F=\{f_a(a):a\in A'\}$ and $G=\{g_b(b): b\in B'\}.$

We can readily show $h(a)=f_a(a)$ is an isomorphism from $A'$ to $F$ and that $j(b)=g_b(b)$ is an isomorphism from $B'$ to $G.$

I will leave the rest to you.