Real numbers are uncountable

We pre­sent a var­i­ant of Can­tor’s di­ag­o­nal­iza­tion ar­gu­ment to prove the real num­bers are un­countable. This con­struc­tively proves that there ex­ist un­countable sets note Since the real num­bers are an ex­am­ple of one..

We use the dec­i­mal rep­re­sen­ta­tion of the real num­bers. An over­line ( \(\bar{\phantom{9}}\) ) is used to mean that the digit(s) un­der it are re­peated for­ever. Note that \(a.bcd\cdots z\overline{9} = a.bcd\cdots (z+1)\overline{0}\) (if \(z < 9\); oth­er­wise, we need to con­tinue car­ry­ing the one); \(\sum_{i=k}^\infty 10^{-k} \cdot 9 = 1 \cdot 10^{-k + 1} + \sum_{i=k}^\infty 10^{-k} \cdot 0\). Fur­ther­more, these are the only equiv­alences be­tween dec­i­mal rep­re­sen­ta­tions; there are no other real num­bers with mul­ti­ple rep­re­sen­ta­tions, and these real num­bers have only these two dec­i­mal rep­re­sen­ta­tions.

The­o­rem The real num­bers are un­countable.

Proof Sup­pose, for con­tra­dic­tion, that the real num­bers are countable; sup­pose that \(f: \mathbb Z^+ \twoheadrightarrow \mathbb R\) is a sur­jec­tion. Let \(r_n\) de­note the \(n^\text{th}\) dec­i­mal digit of \(r\), so that the frac­tional part of \(r\) is \(r_1r_2r_3r_4r_5\ldots\) Then define a real num­ber \(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 sur­jec­tive, con­tra­dict­ing our as­sump­tion, and \(\mathbb R\) is un­countable. \(\square\)

Note that choos­ing 5 and 6 as our al­low­able digits for \(r'\) side-steps the is­sue that \(0.\overline{9} = 1.\overline{0}\). %%

Parents:

  • Uncountability

    Some in­fini­ties are big­ger than oth­ers. Un­countable in­fini­ties are larger than countable in­fini­ties.

    • Mathematics

      Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

  • Real number