We present a variant of Cantor's diagonalization argument to prove the real numbers are uncountable. This constructively proves that there exist uncountable sets ^[1].

We use the decimal representation of the real numbers. An overline ( ) is used to mean that the digit(s) under it are repeated forever. Note that $a . b c d \dots z ¯ ¯ ¯ 9 = a . b c d \dots (z + 1) ¯ ¯ ¯ 0$ (if $z < 9$ ; otherwise, we need to continue carrying the one); $\sum_{i = k}^{\infty} 10^{- k} \cdot 9 = 1 \cdot 10^{- k + 1} + \sum_{i = k}^{\infty} 10^{- k} \cdot 0$ . Furthermore, these are the only equivalences between decimal representations; there are no other real numbers with multiple representations, and these real numbers have only these two decimal representations.

Theorem The real numbers are uncountable.

Proof Suppose, for contradiction, that the real numbers are countable; suppose that $f : Z^{+} ↠ R$ is a surjection. Let $r_{n}$ denote the $n^{th}$ decimal digit of $r$ , so that the fractional part of $r$ is $r_{1} r_{2} r_{3} r_{4} r_{5} \dots$ Then define a real number $r^{'}$ with $0 \leq r^{'} < 1$ so that $r_{n}^{'}$ is 5 if $(f (n))_{n} \neq 5$ , and 6 if $(f (n))_{n} = 5$ . Then there can be no $n$ such that $r^{'} = f (n)$ since $r_{n}^{'} \neq (f (n))_{n}$ . Thus $f$ is not surjective, contradicting our assumption, and $R$ is uncountable. $□$

Note that choosing 5 and 6 as our allowable digits for $r^{'}$ side-steps the issue that $0. ¯ ¯ ¯ 9 = 1. ¯ ¯ ¯ 0$ . %%

^{^︎}
Since the real numbers are an example of one.

Posts

Wikitag Contributions

Comments