Exercise 8.1.10

Proof. $\text{(→)}$ We show the contrapositive of this implication. So suppose that there is a decreasing sequence $⟨a_n\mid n\in \omega ⟩$ in $A$, and let $X$ be the range of the sequence so that clearly $X\subseteq A$ and $X\ne \varnothing$. Now consider any $x\in X$ so that there is a $n\in \omega$ such that $x=a_n$. We then have that $x=a_n>a_{n+1}$ since the sequence is decreasing, noting that clearly $a_{n+1}\in X$. Since $x$ was arbitrary this shows that $X$ has no least element (since we have shown that $\forall <!--\; FUNCTION\; APPLICATION\; -->x\in X\exists <!--\; FUNCTION\; APPLICATION\; -->y\in X(x>y)$ and this is logically equivalent to $\neg <!--\; FUNCTION\; APPLICATION\; -->\exists <!--\; FUNCTION\; APPLICATION\; -->x\in X\forall <!--\; FUNCTION\; APPLICATION\; -->y\in X(x\le y)$, noting that $\neg <!--\; FUNCTION\; APPLICATION\; -->(x>y)$ is equivalent to $x\le y$ since the ordering is linear). Thus, since there is a nonempty subset of $A$ that has no least element, it follows that $(A,<)$ is not a well-ordering.

$\text{(←)}$ We show the contrapositive of this implication as well. So suppose that $(A,<)$ is not a well-ordering. Then there exists a nonempty subset $X$ of $A$ such that $X$ has no least element. By the Axiom of Choice the set $𝒫\left(X\right)$ has a choice function $g$. For any $x\in X$ we define the set $X_x=\left\{y\in X\mid y<x\right\}$.

First we claim that $X_x\ne \varnothing$ for any $x\in X$. Suppose to the contrary that there is some $x\in X$ such that $X_x=\varnothing$. Consider any other $y\in X$. Then it cannot be that $y<x$ for then $y\in X_x$ so that $X_x\ne \varnothing$. So, since the ordering is linear, it has to be that $y\ge x$. But, since $y$ was arbitrary, this would mean that $x$ is the least element of $X$, which we know cannot be since $X$ has no least element! Therefore it has to be that indeed $X_x\ne \varnothing$ for any $x\in X$.

Now we construct a sequence $⟨a_n\mid n\in \omega ⟩$ by recursion:

noting that the recursive step is always valid since $X_{a_n}$ is never empty, as was just shown. It is easy to see that this is a decreasing sequence. Take any $n\in \omega$ so that we have that $a_{n+1}=g(X_{a_n})$. Hence $a_{n+1}\in X_{a_n}$ since $g$ is a choice function. By the definition of $X_{a_n}$ it then follows that $a_{n+1}<a_n$, which shows that the sequence is decreasing since $n$ was arbitrary. Hence we have constructed an infinite decreasing sequence in $A$. □