# What is wrong with this bijection from all naturals to reals between 0 and 1?

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.

• Isn't the range of your function contained in the set of rational numbers? – Kavi Rama Murthy May 22 '20 at 11:46
• This fallacy crops up repeatedly. It can be found in Martin Gardner's "Wheels, Life and Other Mathematical Amusements" from 1983, which is a bunch of collected Mathematical Games columns from Scientific American from approximately the early 1970s. – Prime Mover May 22 '20 at 12:14

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".
• +1. Here $0.01010101\ldots_2 = \frac{1}{3}$ so the original list misses this and many other rationals. It is possible to have a different bijection which has all the rationals in $[0,1)$ but not one which has all the reals – Henry May 22 '20 at 12:04