# Difference between $\mathbb{Q}$ and $\mathbb{R}$ - countability proof

We know $\mathbb{Q}$, the rational numbers, is countable; the real numbers is not.

My professor in the course of real analysis proved the title by showing

$\{0,1\}^{\mathbb{N}}$ is not countable, where $\{0,1\}^{\mathbb{N}}$ is sequences of $0$'s and $1$'s indexed by $\mathbb{N}$.

Proof:

1. Suppose there is an enumeration of $\{0,1\}^{\mathbb{N}}$ (by contradiction)
2. For example:
$s_1 = s_1(1), s_1(2),s_1(3),...$
$s_2 = s_2(1), s_2(2),s_2(3),...$
$s_3 = s_3(1), s_3(2),s_3(3),...$
3. Construct $S=\{s(1),s(2),...\}\in \{0,1\}^{\mathbb{N}}$ by $s(i)=1-s_i(i)$.
4. $S$ is not in our enumeration of $\{0,1\}^{\mathbb{N}}$, i.e., $S \neq s_i, \forall i$

The proof is simple; however, my question is what is the relation between $\{0,1\}^{\mathbb{N}}$ and $\mathbb{R}$?
What is the relation between this proof and the title?

• $\{0,1\}^{\Bbb N}$ closely resembles the interval $[0,1)$, when written in binary. – Arthur Sep 30 '15 at 23:45
• You can form a bijection between $(0,1)$ (the interval), and all of $\Bbb R$. Now we can consider a real number in $(0,1)$ as being identified by its binary expansion in terms of powers of $\frac{1}{2}$. – David Wheeler Sep 30 '15 at 23:45

One can identify $\{ 0,1 \}^{\mathbb{N}}$ with $P(\mathbb{N})$, where $i \in f(s)$ if $s_i=1$. You can then identify $P(\mathbb{N})$ with $[0,1]$ through the map:
$$A \mapsto \sum_{i \in A} 2^{-i}.$$
This amounts to binary expansion of a number in $[0,1]$. This is not quite a bijection, because for instance $1/2$ has two binary expansions, namely $0.1000...$ and $0.0111...$. But a modification of this at countably many values, or alternately using this as part of a Schroder-Bernstein argument, gives a bijection.
• $1$ is a bad example, since you should only consider expansions with $0$ as the integral part. But $\frac12$ is a good example instead. – Asaf Karagila Sep 30 '15 at 23:48
• I am a bit confused about $0.100000.... \mapsto 2^{-1} + 2^0 + ....$. However, $2^0=1$, how to get $1/2$? – sleeve chen Oct 1 '15 at 0:17
• @sleevechen $\{ 2,3,\dots \}$ corresponds to $0.0111...=1/2$. But so does $\{ 1 \}$. – Ian Oct 1 '15 at 0:19