I would like to define a well-order on $\mathbb R$. My first thought was, of course, to use $\leq$. Unfortunately, the result isn't well-founded, since $(-\infty,0)$ is an example of a subset that doesn't have a minimal element.

My next thought was to use that $P(\mathbb N)$ is in bijection with $\mathbb R$ and then to use $\subseteq$. Unfortunately, this is not a total (=linear) order.

Now I'm stuck. Could someone show me how to define a well-order on $\mathbb R$? (Using the axiom of choice is permitted.) Many thanks.

Context: This is an exercise in a book I'm currently reading: enter image description here

  • $\begingroup$ Haven't we covered this enough with both actual questions and crank questions? $\endgroup$ – Asaf Karagila Oct 24 '12 at 12:31
  • 4
  • 1
    $\begingroup$ What are the techniques of Chapter 9? $\endgroup$ – Asaf Karagila Oct 24 '12 at 12:34
  • 4
    $\begingroup$ From your book: Everybody should attempt the exercises rated G (general audience). Beginners are encouraged to also attempt exercises rated PG (parental guidance), but may sometimes want to consult their instructor for a hint. It is also a good idea to double-check your solution with the instructor, especially if it looks trivial to you. Exercises rated R (restricted) are intended for mature audiences. The X-rated problems must not be attempted by anyone easily offended or discouraged. $\endgroup$ – Martin Sleziak Oct 24 '12 at 12:38
  • 3
    $\begingroup$ And one more excerpt - which is directly before this exercise: So, if every set admits a wellorder, then every indexed family of sets can be disjointified. But does every set admit a wellorder? As we shall see in Chapter 9, this is indeed true in ZFC. It is far from being obvious though. Try to do the following exercise, but even if you are not easily discouraged, do not spend more than ten minutes on it. $\endgroup$ – Martin Sleziak Oct 24 '12 at 12:40

Assuming the axiom of choice holds, it is possible to well-order every set. In particular the real numbers.

Fix a choice function on $P(\mathbb R)\setminus\{\varnothing\}$, let us denote it by $f$. We now define by transfinite induction an injection from $\mathbb R$ into the ordinals:

Assuming that $r_\alpha$ were defined by all $\alpha<\beta$, define $r_\beta=f(\mathbb R\setminus\{r_\alpha\mid\alpha<\beta\})$. If $\mathbb R\setminus\{r_\alpha\mid\alpha<\beta\}=\varnothing$ then we stop.

We immediately have that $r_\alpha\neq r_\beta$ for $\alpha\neq\beta$; this has to terminate because $\mathbb R$ is a set, and the induction cannot go through the entire class of ordinals; and the induction covers all the real numbers, because we can keep on choosing.

One can appeal to equivalents of the axiom of choice to show existence:

  • Using Zorn's lemma, let $(P,\leq)$ be the collection of well-orders of subsets of the real numbers, ordered by extensions. Suppose we have a chain of such well-orders, their union is an enumerated union of well-ordered sets and therefore can be well-ordered (without assuming the axiom of choice holds in any form).

    By Zorn's lemma we have a maximal element, and by its maximality it is obvious that we have well-ordered the entire real numbers.

  • Using the trichotomy principle (every two cardinals can be well-ordered) we can compare $\mathbb R$ with its Hartogs number $\kappa$ (an ordinal which cannot be injected into $\mathbb R$), it has to be that $\mathbb R$ injects into $\kappa$, and therefore inherits a well-order by such injection.

The list goes on. The simplest would be to use "The power set of a well-ordered set is well-ordered". As $\mathbb N$ is well-ordered, it follows that $\mathbb R$ can be well-ordered.

However no other proof that I know of has any sense of constructibility as the use of a choice function on the power set of $\mathbb R$ and transfinite induction.

  • $\begingroup$ That's what I was looking for. Thank you! $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 12:44

You can’t: it’s consistent with ZF that $\Bbb R$ not be well-orderable. See this answer for starters.

  • 1
    $\begingroup$ So the exercise in my set theory book is a troll. How unpleasant. $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 12:35
  • 2
    $\begingroup$ I think it partly depends on what you mean by "definable." See Joel David Hamkins's answer here: mathoverflow.net/questions/23478/… $\endgroup$ – Jason DeVito Oct 24 '12 at 12:35
  • $\begingroup$ Sorry, I guess I wanted to allow AC. $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 12:36
  • 1
    $\begingroup$ Yeah, the problem with AC is that it doesn't really allow you to "define" stuff in a colloquial or even technical sense, it only asserts that such a thing exists. Even the word "find" here implies a certain kind of assertion of a particular instance. If somebody asked you to "find" a solution to a differential equation, you wouldn't be satisfied with a proof of the existence of a solution. $\endgroup$ – Thomas Andrews Oct 24 '12 at 12:57
  • 1
    $\begingroup$ @Jason: The axiom of choice is not enough, you need more. The collection of all constructible reals (i.e. subsets of $\omega$ which live in $L$, Godel's universe) is a well-ordered set, but its domain is not necessarily $\mathbb R$ if $V\neq L$. $\endgroup$ – Asaf Karagila Oct 24 '12 at 15:05

To repeat Asaf's answer in my own words to test whether I understand it:

Once we have a bijection $f: \mathbb R \to S \subset \mathbf{ON}$, $\mathbb R$ is well-ordered by the relation $r < r' \iff f(r) < f(r')$.

To define a bijection assume the axiom of choice so that there is a choice function $f$ on $P(\mathbb R) \setminus \{\varnothing\}$. Using $f$ define a map $g: S \subset \mathbf{ON} \to \mathbb R $ as follows:

$$ 0 \mapsto f(\mathbb R)$$ $$ n \in \mathbb N \mapsto f(\mathbb R \setminus \{g(0), \dots, g(n-1) \})$$ $$ \beta \mapsto f(\mathbb R \setminus \{g(\alpha) \mid \alpha < \beta \})$$

Then the domain of $g$ is all sets for which $\mathbb R \setminus \{g(\alpha) \mid \alpha < \beta \} \neq \varnothing$, $g$ is injective by construction ($f$ cannot assume a previously assumed function value since they are removed from the set at each step.) and $g$ is surjective also by construction since if $\mathbb R \setminus \{g(\alpha) \mid \alpha < \beta \} = \varnothing$ it means precisely that $f$ has mapped to all of $\mathbb R$.

  • 1
    $\begingroup$ Your argument is mostly correct, but you missed a bit on the surjectiveness of $g$. First you have to argue why the induction stops, otherwise we find an injection from the class $\mathbf{ON}$ into $\Bbb R$; if $\alpha$ is the least ordinal where $g$ cannot be defined on, then $g\colon\alpha\to\Bbb R$ is a bijection, otherwise we could have defined $g(\alpha)$ as well. $\endgroup$ – Asaf Karagila Nov 17 '12 at 21:52
  • $\begingroup$ @AsafKaragila Nice, thank you for completing my argument. $\endgroup$ – Rudy the Reindeer Nov 17 '12 at 21:53
  • $\begingroup$ Matt, well you completed mine... :-) $\endgroup$ – Asaf Karagila Nov 17 '12 at 21:54
  • $\begingroup$ @AsafKaragila Makes fist with left hand, sticks out little finger and lifts it to touch left corner of mouth. $\endgroup$ – Rudy the Reindeer Nov 17 '12 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.