Real Numbers are Uncountable/Set-Theoretical Approach: Proof 2

Theorem

The set of real numbers $\R$ is uncountably infinite.

Set-Theoretical Approach: Proof 2

By Cantor's Theorem there is no surjection $\N \twoheadrightarrow \mathcal P(\N)$.

Additionally, we know that the power set of the natural numbers is not countable.

Therefore, if we can show that $\mathcal P(\N)$ injects into $\R$ then there is no injection $\R \hookrightarrow \N$ and $\R$ is uncountable.

To prove the theorem we construct an injection, say $f$.

For a subset $S \subseteq \N$, let $\chi_S$ be the characteristic function of $S$, and let $d_i = \chi_S(i)$ for all $i \in \N$.

If the sequence $(d_i)_{i \in \N}$ does not terminate in an infinite sequence of $1$'s, then $f$ sends $S \subseteq \N$ to the binary expansion of a number in $[0,1]$:

$ 0.d_1d_2d_3d_4\ldots $

If the sequence $(d_i)_{i \in \N}$ does terminate in an infinite sequence of $1$'s, then $f$ sends $S$ to the binary integer:

$d_1d_2d_3\ldots d_k .000\ldots$

where $d_k$ is the last member of the sequence not equal to $1$.

Injectivity of $f$ follows from the uniqueness statement of Existence of Base-N Representation.

$\blacksquare$