# What's wrong with this "proof" that $\mathbb{R}$ is enumerable?

The fake proof:

• We know that $$\mathbb{R}$$ is uncountable, hence we cannot enumerate over it.
• But what we do know is that $$\mathbb{Q}$$, the set of rationals, is countable, and even denumerable.
• We also know that we can construct $$\mathbb{R}$$ through what are called Dedekind cuts.
• We choose to let the partition itself denote a new number and go forth to define mathematical operations on it as to be compatible with the rest of the numbers (mainly $$\mathbb{Q}$$ and our new number $$x$$)

Sidenote: I think so far this is standard, and contains nothing false. The actual argument starts below this line.

• Let us denote the set containing $$x$$ as $$S_1 := \mathbb{Q}\cup\{x\}$$. For convenience, the superscript of $$S_1$$ is how many new such numbers we have added through the cuts.

• Since $$\mathbb{Q}$$ is countable, we can enumerate over every single rational $$q\in\mathbb{Q}$$ to produce an $$r\in\mathbb{R}$$. Do this process $$n$$ times and you end up with $$S_n = \mathbb{Q}\cup{x_1}\cup{x_2}\cup\dots\cup{x_n}$$.

• But $$S_n$$ is also enumerable since it has a finite more elements than $$\mathbb{Q}$$.

• Hence - After enumerating over the entirety of $$\mathbb{Q}$$ - Start enumerating over the entirety of $$S_{|\mathbb{N}|}\setminus\mathbb{Q}$$

• Now we will end up with even newer numbers to put in our set, which we will now call $$S_{n = |\mathbb{N}|,k}$$ where $$n$$ represents the enumeration over $$\mathbb{Q}$$ and $$k$$ represents the enumeration over $$S_{|\mathbb{N}|}\setminus\mathbb{Q}$$. Do this ad infinitum and you will eventually describe $$\mathbb{R}$$.

I know I went wrong somewhere, I just don't know where.

• "After enumerating over the entirety of $\mathbb{Q}$" if you continue listing elements that is no longer an enumeration. There is no problem anywhere else. You are producing maps from ordinals to the real numbers. In the sentence that you highlighted you are allowing yourself to use ordinals larger than the ordinal of the natural numbers. Sure, you can (assuming the well-order principle) get a bijection between some ordinal and the real numbers.
– plop
Jul 14, 2020 at 20:39
• @plop Correct me if I'm wrong - but one can always accommodate inside a bijection between countable sets a finite amount of new elements, so I'm not sure if I understand how it's no longer an enumeration... Jul 14, 2020 at 20:44
• When you have enumerated the entirety of $\mathbb{Q}$ you have a bijection from $\mathbb{N}$ to $\mathbb{Q}$. You can append the new elements appending new elements to $\mathbb{N}$. Like $\infty\mapsto x_1$, $\infty+1\mapsto x_2$. The actual names that are used are $\omega_0\mapsto x_1$, $\omega_0+1\mapsto x_2$.
– plop
Jul 14, 2020 at 20:48
• Just go read about ordinal numbers. Yes, you have (as a given, not by any algorithm) a bijection between the real numbers and an ordinal number (assuming the aiom of choice. Oops, above I said well ordering principle). No, that ordinal number is not going to be bijective to $\mathbb{N}$.
– plop
Jul 14, 2020 at 20:50
• Enumerable is existence of a bijection with $\mathbb{N}$. What I am saying is that the claim that $S_n$ is enumerable is not wrong, since it can be mapped to $\mathbb{N}$ as I said. As my first comment was saying, it is the highlighted step what is the problem.
– plop
Jul 15, 2020 at 12:47

"Do this ad infinitum and you will eventually describe $$\mathbb{R}$$."
• Yes - uncountably in the sense it exceeds $\omega_0$, but not in the sense you run out of ordinals - right? I don't think you can run out of ordinals... ever. Am I wrong on this? Jul 16, 2020 at 2:42
• The procedure (if you're careful enough on how you adjoin new numbers, you did not actually make that part of your attempt precise) can suceed after $\omega_1$ steps, where $\omega_1$ is the least uncountable ordinal. Jul 16, 2020 at 10:51
• The procedure may never succeed if, if your example, you never add $\sqrt{42}$ to your sets. You need some guarantee that every real will eventually be added. Jul 16, 2020 at 10:52