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.
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ You will run out of integers before you run out of real numbers. Imaging your argument but with the set of natural numbers and the set $\{1,2,...,10^{10^{10^{10}}}\}$; you argument isn't complete until you show that you don't run out of one set before finishing the pairing process. $\endgroup$– user208649Commented Apr 20, 2020 at 2:23
-
$\begingroup$ Cantor's theorem has an extremely direct proof. Give me a function, I'll build you a real number not in its range. When confronting with these doubts about it, one should always ask themselves "how does it apply to this proof". Where is the axiom of choice being used? We are given the function $f\colon\Bbb{N\to R}$, so no choice there. There's no choice of reals, since they are given by the function, and there's no choice in their decimal expansion. And there's no choice in constructing the diagonal real. So... no choice. $\endgroup$– Asaf Karagila ♦Commented Apr 20, 2020 at 7:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Where did you map $0$, though? :-) $\endgroup$– Asaf Karagila ♦Commented Apr 20, 2020 at 7:29
-
$\begingroup$ @AsafKaragila Well there is always the philosp[hical discussion: is $0 \in \mathbb N$? Some people say yes, some people say no....;) Depending on the convention, the answer changes $\endgroup$– N. S.Commented Apr 20, 2020 at 17:53
-
$\begingroup$ Sure, some people say that $0$ is a natural numbers, and others are simply wrong! :P $\endgroup$– Asaf Karagila ♦Commented Apr 20, 2020 at 17:54
$\begingroup$
$\endgroup$
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.
answered Apr 20, 2020 at 2:23