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}$.


  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?

  • 1
    $\begingroup$ $\{0,1\}^{\Bbb N}$ closely resembles the interval $[0,1)$, when written in binary. $\endgroup$ – Arthur Sep 30 '15 at 23:45
  • 1
    $\begingroup$ 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}$. $\endgroup$ – 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.

  • $\begingroup$ $1$ is a bad example, since you should only consider expansions with $0$ as the integral part. But $\frac12$ is a good example instead. $\endgroup$ – Asaf Karagila Sep 30 '15 at 23:48
  • $\begingroup$ I am a bit confused about $0.100000.... \mapsto 2^{-1} + 2^0 + ....$. However, $2^0=1$, how to get $1/2$? $\endgroup$ – sleeve chen Oct 1 '15 at 0:17
  • 1
    $\begingroup$ @sleevechen $\{ 2,3,\dots \}$ corresponds to $0.0111...=1/2$. But so does $\{ 1 \}$. $\endgroup$ – Ian Oct 1 '15 at 0:19

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.