1
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ Isn't the range of your function contained in the set of rational numbers? $\endgroup$ – Kavi Rama Murthy May 22 '20 at 11:46
  • $\begingroup$ 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. $\endgroup$ – Prime Mover May 22 '20 at 12:14
5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ N.B.: You seem to have mixed up left/right, in your first sentence. $\endgroup$ – Mees de Vries May 22 '20 at 11:50
  • $\begingroup$ @Mees de Vries Heh! Silly me. Corrected it. $\endgroup$ – Prime Mover May 22 '20 at 11:59
  • 1
    $\begingroup$ +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 $\endgroup$ – Henry May 22 '20 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.