How to Define a Well-Order on the Real Numbers

axiom-of-choiceelementary-set-theoryorder-theorywell-orders

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

Best Answer

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.

Related Question