Exercise WO.4

Proof. First, we can assume that $A$ and $B$ are disjoint since, if not, we can form $A^{\prime }=\left\{(x,1)\mid x\in A\right\}$ and $B^{\prime }=\left\{(x,2)\mid x\in B\right\}$, which clearly are disjoint and have the same order types as $A$ and $B$ if ordered in the same way. So let $\prec$ be the order on $A\cup B$ as in Exercise 10.8 with all the elements of $A$ before the elements of $B$. From the exercise, we know that $A\cup B$ is well-ordered by $\prec$. Now, clearly the identity function $i_B$ with $A\cup B$ as the range is an order-preserving function from $B$ to $A\cup B$ so that $B$ is the same order type as $A\cup B$ or a section of $A\cup B$ by Exercise WO.3.

If $B$ has the same order type as $A\cup B$, then there is a an order-preserving bijection $g:A\cup B\to B$. Let $b$ be the smallest element of $B$ so that $y=g(b)\in B$. Since $b$ is the smallest element of $B$, clearly the section $S_b=\left\{x\in A\cup B\mid x\prec b\right\}=A$. Also clearly $g(A)=g(S_b)=S_y=\left\{x\in B\mid x<y\right\}$ so that $A$ has the same order type as a section of $B$ since $g$ preserves order.

If $B$ has the same order type as a section of $A\cup B$ then there is an order-preserving bijection $f:B\to S_{\alpha }$ for some $\alpha \in A\cup B$. If $\alpha \in A$ then clearly $S_{\alpha }$ lies entirely in $A$ and is a section of $A$ so that $B$ has the same order type as a section of $A$. So now suppose that $\alpha \in B$. If $\alpha$ is the smallest element of $B$ then again it has to be that $S_{\alpha }$ lies in $A$ and is in fact the entirety of $A$ so that $B$ and $A$ have the same order type. If $\alpha$ is not the smallest element of $B$ then $S_{\alpha }$ contains elements of both $A$ and $B$. So let $b$ be the smallest element of $B$ so that $b\in S_{\alpha }$, and let $y\in B$ be such that $f(y)=b$, which exists since $f$ is surjective. We also have that $S_b=A$ since $b$ is the smallest element of $B$. It then follows that $f(S_y)=S_b=A$ since $f(y)=b$ so that $A$ has the same order type as the section $S_y$ of $B$ since $f$ preserves order.

Hence in all cases, one of the desired results always follows. To show that exactly one of these is the case, note that if $A$ and $B$ have the same order type then clearly it cannot be that $A$ has the same order type as a section of $B$ since then $B$ would also have the same order type is its own section, which would violate Exercise WO.2 part (b). Similarly, $B$ cannot have the same order type as a section of $A$ since then $A$ would have the same order type as its own section. Now suppose that $A$ has the same order type as a section $S_b$ of $B$. Then $A$ and $B$ cannot have the same order type since then $B$ would have the same order type as its section $S_b$. Also, $B$ cannot have the same order type as a section $S_a$ of $A$ since then the section $S_b$, and therefore $A$, would have the same order type as a smaller section of $A$. An analogous argument shows the result when $B$ has the same order type as a section of $A$. □

Proof. Suppose that $A$ has the same order type as a section of $B$. Then there would be a bijection from $A$, an uncountable set, to a section of $B$, which is countable. A similar contradiction arises if $B$ were to have the same order type as a section of $A$. By part (a), the only remaining possibility is that $A$ and $B$ have the same order type as desired. □