Real Numbers are Uncountably Infinite/Proof 2 using Ternary Notation

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Lemma

Let $\sequence {d_n}$ and $\sequence {e_n}$ be infinite sequences in $\set {0, 1}$ such that:

$\exists m \in \N: d_m \ne e_m$

That is, the sequences $\sequence {d_n}$ and $\sequence {e_n}$ are different in at least one term.

Then the ternary representations $D = 0.d_1 d_2 \ldots$ and $E = 0.e_1 e_2 \dots$ represent distinct real numbers.


Proof




Define a mapping $f: \powerset {\N_{>0} } \to \R$ thus:

$\map f S = 0.d_1 d_2 \ldots$, interpreted as a ternary expansion where $\sequence {d_n}$ is the characteristic function of $S$.

That is:

$\ds \map f S = \sum_{i \mathop \in S} 3^{-i}$

By the lemma, $f$ is an injection.

Aiming for a contradiction, suppose that $\R$ is countable.

Then there is an injection $g: \R \to \N$.

By Composite of Injections is Injection, $g \circ f: \powerset \N \to \N$ is an injection.

But this contradicts No Injection from Power Set to Set.

Hence, by Proof by Contradiction, $\R$ is not countable.

$\blacksquare$