Can $\mathbb R$ be enumerated after all?

Question

I understand that the real numbers are innumerable, they cannot be put in bijection with the natural numbers. But assuming ZFC, a well-order of $\mathbb R$ can be achieved and thus there is a 'first' real number, and after that a successor to that first, and so on... and since a well-order is a total order (every pair of elements are comparable), it seems to me like I can exhaust all of the real numbers in that way. Clearly I must be missing something, so what is it?

Answer 1

As you say, a well-ordering of the reals would give you $r_0,r_1,...$ where $r_i$ is the unique successor of $r_{i-1}$. But the proof that the reals aren't enumerable shows that the well-ordering won't be exhausted by $r_i$ for $i\in\mathbb{N}$. Rather, we have to keep going: there's $r_\omega$ the least element of $\{x\in\mathbb{R}:x>r_i\forall i\in \mathbb{N}\}$, $r_{\omega+1},...$ and repeating again after infinitely many more numbers $r_{2\omega},...,r_{n\omega},...,r_{\omega^n},...,r_{\omega^\omega},...$ I haven't gotten anywhere near the end of the countable ordinals people have seen fit to describe, but this should give the basic idea that a well-ordering of a general set can be much more complicated than the usual well-ordering of $\mathbb{N}$. The basic issue is this: taking successor repeatedly can never generate more than a countable set.

It seems worth mentioning that there are lots of well-orders even of countable sets that aren't exhausted by the successor process. For instance, order $\mathbb{N}$ by $2,3,4,...,1$. Or $2,4,6,...,1,3,5,...$. Or $1,2,4,6,...,3,9,15,...,5,25,35,...,...$. These are orders that look like the initial segment of $\mathbb{R}$ preceding $r_{\omega+1},r_{2\omega},$ and $r_{\omega^2}$ in the above paragraph.

Answer 2

Well-orders are not a property unique to the natural numbers. Consider $A=\Bbb N\cup\{x\}$ (where $x$ is not a natural number). Now consider the following order on $A$:

$$a<_Ab\iff\begin{cases} a<b & a,b\in\Bbb N\\ b=x & \text{otherwise}\end{cases}$$

How does this order look like? It looks like writing all the natural numbers, and after exhausting all of them we write $x$. So something like this: $$0,1,2,\ldots,n,n+1,n+2,n+3,\ldots\ ,x$$

Why am I bringing this up? Well, I am bringing this up because while it's obvious that $A$ is countable, if you start anywhere in the $\Bbb N$-part of $A$, and start taking successors, you will still never get to the point $x$. At most you will get to cover all (or an end segment of) $\Bbb N$. But not $x$.

So what did we learn? We learn that well-orders can have elements which are not successors, at all, and these are called limit points. So when we well-order $\Bbb R$ we have the first element, and its successor, and so on. But after exhausting what we can by using the successor function, we still haven't counted the first limit point.

Now you might argue "well, let's add that limit point and resume with the successor operation. Surely that will do the trick!", but again the answer is no. For two reasons. The first is that at some point you will reach a point which is a limit point of limit points (and then limit of limits of limits and so on), and at each of these points you will have to "increase the complexity" of your enumeration, until you can't even describe it anymore with a reasonable definition.

The second reason, which is far the more convincing, is that for an uncountable well-order the set of limit points and the set of successor points have the same cardinality (which is the same cardinality as the well-order itself). So the argument that "surely by adding a couple of limit points and we'll be able to finish" fails because you have to add a lot of limit points.