Cantor's proof is as brilliant as it is simple.# Proof: What does countability mean?
(related to Proposition: Real Numbers are Uncountable)
We want to show that the set $\mathbb R$ of real numbers is uncountable. We will show that this is true even for the real interval $[0,1]\subset\mathbb R.$
* Suppose, $[0,1]$ is countable.
* Therefore, by definition of countability, there is an injective function $f:[0,1]\to\mathbb N$.
* Suppose that we can list the values of this function in some hypothetical way:
\[
\begin{array}{rcl}
(\underline{0}.0379357232\ldots)&\rightarrow&1\\
(0.\underline{7}112223358\ldots)&\rightarrow&2\\
(0.9\underline{4}80483777\ldots)&\rightarrow&3\\
(0.00\underline{8}4973921\ldots)&\rightarrow&4\\
(0.009\underline{5}857262\ldots)&\rightarrow&5\\
(0.0399\underline{0}39551\ldots)&\rightarrow&6\\
(0.23964\underline{3}9345\ldots)&\rightarrow&7\\
\vdots
\end{array}
\]
* Now, consider the real number $r$ built by the underlined digits in the diagonal.1
* Now, define a new real number $s$ by changing in $r$ every digit after the comma in an arbitrary way.2
* Note that we cannot find any value \(n\in\mathbb N\) such that $f(s)=n$.
* Thus, although we have found a new real number, $f$ is not injective.
* This is a contradiction to the hypothesis.
* Thus the number of real numbers $0\le r\le 1$ is uncountable.
Parts: 1
