# 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.

• Are you familiar with transfinite recursion? If not, how about Zorn’s lemma? – Brian M. Scott Jan 20 '15 at 18:13
• @BrianM.Scott I'm familiar with Zorn's lemma. – Luka Horvat Jan 20 '15 at 18:14
• Okay; I’ll sketch an argument that uses it. – Brian M. Scott Jan 20 '15 at 18:15
• Keep picking larger and larger elements until there is nothing bigger left. – user203787 Jan 20 '15 at 21:13

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$.
• @Luka: If you do that, the union of a chain need not be well ordered. Consider, for instance, $\{0\},\{-1,0\},\{-2,-1,0\},\ldots$. – Brian M. Scott Jan 20 '15 at 19:51
• @Luka: Look at the example: the union itself isn’t a subset of any of the elements of the chain. They’re all finite, and it’s infinite. You can only be sure that every finite subset of the union belongs to one of the elements of the chain. – Brian M. Scott Jan 20 '15 at 20:00
• @Luka: I’m afraid not. Take $X=\Bbb R$, and let $0$ be the fixed element. Then you can build the chain $\{1\},\left\{\frac12,1\right\},\left\{\frac13,\frac12,1\right\},\ldots$. – Brian M. Scott Jan 20 '15 at 20:04
• @Luka: You’re welcome. I’ve used similar arguments often enough that I don’t really have to think about that particular problem, and I’ve also used arguments in which I had to be able to extend to the left to get a non-well-order, so the whole cluster of ideas is simply very familiar to me. It’s been over $40$ years since I first encountered the ideas, and I honestly don’t remember my thought processes at the time. – Brian M. Scott Jan 20 '15 at 20:13
• In fact it's simple. You just consider the "natural" order of your elements of W. If all you know about them is that they are subsets of some fixed set, subset is the natural order. If they are ordinals, \in is the natural order. For well-ordered sets, "being an initial segment of" is the natural order. I have yet to encounter an ordinary task (ie, not constructed specially for that purpose:) that requires you to think of some new ordering relation. – Veky Feb 16 '17 at 6:17

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.