Why does axiom of choice not imply the set of real numbers is countable?

Question

The axiom of choice implies all sets can be well ordered. If that is true, you can well order the set of real numbers and the set of the integers. Now, why can one not just pair the set of real numbers off as follows: start at the smallest integer pair it with the smallest real, pair the second smallest integer with the second smallest real, etc. I’m aware of Cantor’s proof that the reals are not countable. I’m just wondering if that depends on the axiom of choice in someway or if the aforementioned pairing is flawed.

Answer 1

To understand the issue better consider $\mathbb N^2$ with the dictionary order. That means that $(a,b) \leq (c,d)$ if and only if either $a <c$ or $a=c$ and $b \leq d$.

Then $(\mathbb N^2 , \leq)$ is a well ordered set.

Now, let us run through your argument, with this set instead of $\mathbb R$.

You pair the numbers the following way: $$1 \leftrightarrow (1,1) \\ 2 \leftrightarrow (1,2) \\ 3 \leftrightarrow (1,3) \\ ...\\ n \leftrightarrow (1,n) \\ ...$$

This does not create a bijection for obvious reasons.

Answer 2

Your pairing is flawed: after you’ve paired up the integers with some initial segment of the reals in their well-ordering, an uncountable collection of reals will remain unpaired. To put it another way, you can well-order the integers so that each integer has only finitely many predecessors; in any well-ordering of the reals, however, there are uncountably many real numbers with infinitely many predecessors.

The proof that $\Bbb R$ is uncountable does not depend on the axiom of choice.