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:
* 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.