7
$\begingroup$

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

  • 0
    Haven't we covered this enough with both actual questions and crank questions?2012-10-24
  • 4
    Duplicate of: http://math.stackexchange.com/questions/150992/a-way-to-well-order-real-line http://math.stackexchange.com/questions/23927/explicit-well-ordering-of-mathbbn-mathbbn http://math.stackexchange.com/questions/137657/is-there-a-well-ordering-of-the-reals-measurable-or-not http://math.stackexchange.com/questions/88757/nice-well-orderings-of-the-reals2012-10-24
  • 1
    What are the techniques of Chapter 9?2012-10-24
  • 0
    @AsafKaragila Versions of the axiom of choice. Why? Do I get a w.o. of the reals with choice?2012-10-24
  • 4
    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.2012-10-24
  • 3
    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.*2012-10-24
  • 0
    @Martin: You beat me to it. Yes, it’s pretty clear that point of the exercise is to get the student to see that the task is going to be difficult at best.2012-10-24
  • 0
    @MartinSleziak Yes, exactly. Every set admits a well-order and my question is whether someone can show me a construction. Should've added the AC tag to avoid confusion.2012-10-24
  • 0
    Actually you should have added this within the body of the question.2012-10-24
  • 0
    If it's still a dupe I'll flag for deletion.2012-10-24
  • 0
    Meh. Actually Asaf's answer is quite neat. Would be sad if it got deleted.2012-10-24
  • 0
    I don't think it is a duplicate, but I do think it is worth to clarify that the use of AC is allowed.2012-10-24
  • 0
    @AsafKaragila Since it's my own question I will refrain from politics and not vote to reopen. I will of course also not vote to close if it gets reopened. : )2012-10-24
  • 0
    What does (X) mean next to an exercise in that book? That this is something you should think about, but perhaps not solve?2012-10-25
  • 0
    @GEdgar: Martin's first comment says that they have some sort of a rating system (like with movies and music), so X-rated questions is supposedly a pornographic question with highly offensive content.2012-10-25

3 Answers 3

9

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.

  • 0
    That's what I was looking for. Thank you!2012-10-24
8

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

  • 1
    So the exercise in my set theory book is a troll. How unpleasant.2012-10-24
  • 2
    I think it partly depends on what you mean by "definable." See Joel David Hamkins's answer here: http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics2012-10-24
  • 0
    Sorry, I guess I wanted to allow AC.2012-10-24
  • 1
    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.2012-10-24
  • 0
    @Thomas: My (perhaps flawed) understand of Joel's response is that you can write down a definition of a particular relation on $\mathbb{R}\times\mathbb{R}$ - it's totally "constructable". What you can't do (without AC) is prove that the definition actually defines a well order.2012-10-24
  • 1
    @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$.2012-10-24
  • 0
    @Asaf: I see. Thanks for clarifying.2012-10-24
  • 0
    @JasonDeVito Who is Joel? Am I missing something?2012-10-24
  • 0
    @Thomas: Joel David Hamkins, whose answer to a question on MathOverflow was mentioned earlier in the comments.2012-10-24
0

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
    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.2012-11-17
  • 0
    @AsafKaragila Nice, thank you for completing my argument.2012-11-17
  • 0
    Matt, well you completed mine... :-)2012-11-17
  • 0
    @AsafKaragila Makes fist with left hand, sticks out little finger and lifts it to touch left corner of mouth.2012-11-17