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:
- Suppose there is an enumeration of $\{0,1\}^{\mathbb{N}}$ (by contradiction)
- 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),...$ - Construct $S=\{s(1),s(2),...\}\in \{0,1\}^{\mathbb{N}}$ by $s(i)=1-s_i(i)$.
- $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?
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.