14
$\begingroup$

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.

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

2 Answers 2

Reset to default
14
$\begingroup$

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$.
$\endgroup$
26
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Brian M. Scott
    Commented Jan 20, 2015 at 19:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – Brian M. Scott
    Commented Jan 20, 2015 at 20:00
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Brian M. Scott
    Commented Jan 20, 2015 at 20:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Brian M. Scott
    Commented Jan 20, 2015 at 20:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Veky
    Commented Feb 16, 2017 at 6:17
7
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .