Real numbers are uncountable

We present a variant of Cantor’s diagonalization argument to prove the real numbers are uncountable. This constructively proves that there exist uncountable sets note Since the real numbers are an example of one..

We use the decimal representation of the real numbers. An overline ( \(\bar{\phantom{9}}\) ) is used to mean that the digit(s) under it are repeated forever. Note that \(a.bcd\cdots z\overline{9} = a.bcd\cdots (z+1)\overline{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: \mathbb Z^+ \twoheadrightarrow \mathbb R\) is a surjection. Let \(r_n\) denote the \(n^\text{th}\) decimal digit of \(r\), so that the fractional part of \(r\) is \(r_1r_2r_3r_4r_5\ldots\) Then define a real number \(r'\) with \(0 \le r' < 1\) so that \(r'_n\) is 5 if \((f(n))_n \ne 5\), and 6 if \((f(n))_n = 5\). Then there can be no \(n\) such that \(r' = f(n)\) since \(r'_n \ne (f(n))_n\). Thus \(f\) is not surjective, contradicting our assumption, and \(\mathbb R\) is uncountable. \(\square\)

Note that choosing 5 and 6 as our allowable digits for \(r'\) side-steps the issue that \(0.\overline{9} = 1.\overline{0}\). %%


  • Uncountability

    Some infinities are bigger than others. Uncountable infinities are larger than countable infinities.

  • Real number