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

  • 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$.

  • 0
    @AsafKaragila Makes fist with left hand, sticks out little finger and lifts it to touch left corner of mouth.2012-11-17