Prove that every totally ordered set has a well-ordered cofinal subset

I thought this was easy until I realized that for a set to be well-ordered, EACH of it's non-empty subsets must have a least element.

Let $A$ be a non-empty totally ordered set. Let $x_0$ be some element of $A$. Define $S=\{x\in A|x\ge x_0\}$. $x_0 \in S$ so $S$ isn't empty.

Now, this seems like it would work. It certainly is totally ordered and cofinal in $A$, but it might not be well-ordered.

For example, if $A=\mathbb R$ then $(x_0 + 1, x_0 + 2)$ (where $()$ denotes an open interval) is a non-empty subset of $S$, but doesn't have a least element.

Solution 1:

Let $\langle X,\le\rangle$ be a non-empty linear order. If $X$ has a maximum element $x_0$, then $\{x_0\}$ is a well-ordered cofinal subset, so assume that $X$ has no largest element. Let

$$\mathscr{W}=\{W\subseteq X:\langle W,\le\rangle\text{ is a well-order}\}\;,$$

and define a relation $\preceq$ on $\mathscr{W}$ by setting $W_0\preceq W_1$ if and only if $W_0$ is an initial segment of $W_1$.

• Prove that $\preceq$ partially orders $\mathscr{W}$.
• Prove that every chain in $\langle\mathscr{W},\preceq\rangle$ has an upper bound in $\mathscr{W}$.
• Prove that a $\preceq$-maximal element of $\mathscr{W}$ is a well-ordered cofinal subset of $\langle X,\le\rangle$.

Solution 2:

By transfinite recursion, we can define a sequence $(a_\alpha)_{\alpha\in\mathrm{Ord}}$ of elements of $A$ (see ordinals) such that $a_\alpha$ satisfies $$\forall\beta,\ \beta<\alpha\implies a_\beta<a_\alpha$$ Each step is possible if and only if $(a_\beta)_{\beta<\alpha}$ isn't cofinal.

But this construction must stop somewhere for there isn't an unlimited number of elements of $A$. That's the point where you get a cofinal sequence, which is well ordered because ordinals are.