Cantor's theorem using binary notation

Question

One version of Cantor's theorem states there are more real numbers than natural numbers. A common proof is like this: Suppose we have a bijective map $f: \mathbb{N}\to \mathbb{R}$. This can be thought of as an infinite sequence of real numbers. WLOG we can assume the real numbers are in $(0,1)$. Then we can make a list of their decimal representations; for example,

.1598302417545...

.1428571428571...

.11320864521217388..

.999999000...

.718281828459045..

...

We then create a new number $z$ as follows. Find the nth digit of the nth number on this list, call it $a_n$. Then to get the nth digit of $z$, if $a_n$ is 0, change it to 1; if it is 1 change it to 2, and so forth, and if it is 9 change it to 0. Then $z$ is different from every number on this list, because it differs from the nth number in the list in the nth decimal place. In this case, $z=0.25409...$

There is one hitch to this argument. There could be more than one representation of a real number between 0 and 1; for example, 0.49999... = 0.5000000. So while this proves $z$ is different from all the representations on the list, it could be the same number as one of the numbers on the list. Here is an example, using binary representation. Let the list be $1/2, 1/4, 3/4, 1/8, 3/8, 5/8, ...$ enumerating the dyadic rationals. In binary this is:

0.1000000...

0.0100000...

0.1100000...

0.0010000...

0.0110000....

...

Then $z$ is 0.0011111... . But this is the same as 0.01, which is already on the list.

Can Cantor's argument be reworked to use binary representation and avoid this difficulty?

Answer 1

A way to fix the decimal version is if $a_n$ is $1$ then change it to $2$, if it's anything else then change it to $1$. The constructed number will still differ from everything in the list but it won't end in all $0$s or all $9$s.

The same trick does not work in base $2$ but you could handle the bits in pairs. Change $01$ to $10$ and anything else to $01$. You might consider this cheating, as it is really working in base $4$.

Answer 2

Another way to handle the binary case is to let $D=\{d_n:n\in\Bbb N\}$ be the set of dyadic rationals in $(0,1)$. For $n\in\Bbb N$ and $i\in\{0,1\}$ let $d_n^{(i)}$ be the binary representation of $d_n$ that ends in an infinite string of $i$s. Define a new function

$$g:\Bbb N\to[0,1):n\mapsto\begin{cases} f(n/3),&\text{if }n\equiv 0\pmod 3\\ d_{(n-1)/3}^{(0)},&\text{if }n\equiv 1\pmod 3\\ d_{(n-2)/3}^{(1)},&\text{if }n\equiv 2\pmod 3\,. \end{cases}$$

(Note that my $\Bbb N$ includes $0$.)

Now diagonalize the new list $g$: the resulting number disagrees somewhere not only with each number in the original list, but also with both representations of each dyadic rational in $(0,1)$, so it cannot be any $f(n)$ even in disguise, so to speak.

It does not matter that $g$ is not a bijection. Indeed, $f$ need not be a bijection. The argument shows that for any function $f:\Bbb N\to[0,1)$ there is a real number in $[0,1)$ that is not equal to $f(n)$ for any $n\in\Bbb N$, and thus in particular there is no bijection between $\Bbb N$ and $[0,1)$.