Wrong with this bijection from all naturals to reals between 0 and 1

diagonalizationreal numbers

I will use binary. I claim to have a bijection $f \colon \mathcal{N} \to \left[ 0, 1 \right)$ where $\mathcal{N}$ is the set of natural numbers $\left\{ 0, 1, 10, 11, 100, \dotsc \right\}$ as follows:

$$
\begin{array}{l|l}
x \in \mathcal{N} & f(x) \in \left[ 0, 1 \right)\\\hline
0 & 0.0 \\
1 & 0.1 \\
10 & 0.01 \\
11 & 0.11 \\
100 & 0.001 \\
101 & 0.011 \\
110 & 0.101 \\
111 & 0.111 \\
1000 & 0.0001 \\
\hspace{.6em}\vdots & \hspace{.9em}\vdots
\end{array}
$$

It's basically the shortlex order.

I claim to have everything on this list. Diagonalization? Go ahead! Constructing a number that differs from $f(i + 1)$ in its $i$-th fractional digit yields $0.11111\!\ldots = 0.\overline{1}$ which is $1$, and that should not be on the list anyway!

Why does this not work? I think it has something to do with integers supposedly not having infinite digits, while reals supposedly do.

Best Answer

If on the right you have $0.01010101 ...$ and so on ad infinitum, on the left you have an infinite number $10101010....$ which is not on your list because an element of the natural numbers is itself not an "infinite number".

So all you can create on the RHS are finitely terminating rationals which is a countable set.

Related Question