Exercise 10.4

Proof. Let $A$ be a set with simple order $\prec$.

$\text{(⇒)}$ Suppose that $\prec$ is not a well-ordering of $A$. Then there exists a nonempty subset $B$ of $A$ such that $B$ has no smallest element. For any $b\in B$ define the set $X_b=\left\{x\in B\mid x\prec b\right\}$. Clearly $X_b\subset B$ and $X_b\ne \varnothing$ for any $b\in B$ since otherwise $b$ would be the smallest element of $B$. Now let $c$ be a choice function on the collection of nonempty subsets of $B$, which of course exists by the axiom of choice. Since $B$ is nonempty there is a $b_0\in B$. It then follows from the principle of recursive definition that there is a function $f:{\mathbb{Z}}_{\text{+}}\to B$ such that

It then is easy to show that $f(n+1)\prec f(n)$ for all $n\in {\mathbb{Z}}_{\text{+}}$, i.e. that the sequence defined by $f$ is decreasing. If we then simply define $g:{\mathbb{Z}}_{\text{−}}\to {\mathbb{Z}}_{\text{+}}$ by $g(n)=-n$ for $n\in {\mathbb{Z}}_{\text{−}}$, it is clear that $f\circ g$ is an order-preserving bijection from ${\mathbb{Z}}_{\text{−}}$ to some subset $C$ of $B$. Clearly also $C\subset A$ since $B\subset A$. Hence the subset $C$ has the same order type as ${\mathbb{Z}}_{\text{−}}$.

$\text{(⇐)}$ Now suppose that $A$ has a subset $B$ with the same order type as ${\mathbb{Z}}_{\text{−}}$. Clearly then $B$ is nonempty and has no smallest element since ${\mathbb{Z}}_{\text{−}}$ does not. The existence of this $B$ shows that $A$ fails to be well-ordered. □

Proof. Suppose that $A$ is a set that is simply ordered by $\prec$ such that every countable subset is well-ordered by $\prec$. Consider any nonempty subset $B\subset A$. Suppose for a moment that the restricted $\prec$ does not well-order $B$. Then it follows from part (a) that $B$ has a subset $C$ with the same order type as ${\mathbb{Z}}_{\text{−}}$. However, clearly $C\subset A$ (since $B\subset A$) and $C$ is countable (since ${\mathbb{Z}}_{\text{−}}$ is countable) and thus it should be well-ordered. As this is impossible since $C$ has the same order type as ${\mathbb{Z}}_{\text{−}}$ (which is clearly not well-ordered), it has to be that the restricted $\prec$ does in fact well-order $B$. Hence $B$ has a $\prec$-smallest element, which shows that $A$ is well-ordered since $B$ was arbitrary. □