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$ May 22, 2020 at 11:46
  • 1
    $\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$ May 22, 2020 at 12:14

1 Answer 1

7
$\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$ May 22, 2020 at 11:50
  • $\begingroup$ @Mees de Vries Heh! Silly me. Corrected it. $\endgroup$ May 22, 2020 at 11:59
  • 3
    $\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, 2020 at 12:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .