This page does not represent the most current semester of this course; it is present merely as an archive.
Before we get to the main proof, let’s do a lemma:
The lemma is easily proven by showing a total injection:
Consider the function defined as . The function is total (it is defined for all ) and injective . Hence, there exists a total injection from to , which means
With this lemma, all we need to prove that is to prove that .
We proceed by contradiction.
Assume . Then there exists a total invertible function . Let be one such function.
Let be defined such that the th digit of is one more than the th digit of . Formally, that means:
Because is a real number and is invertible, there must exist some such that . But by construction the th digit of differs from the th digit of ; formally, that is
That means , which contradicts our definition of and .
Because assuming led to a contradiction, it must be the case that .
Because of our lemma, we know that , which must mean
Why does the above proof technique not work for integers? Because if we try to apply it to integers, we end up with an infinite string of digits on the left side of the decimal point, which is not an integer.
Why does the above proof technique not work for rationals? Because the decimal expansion of any rational repeats, and the diagonal construction of does not repeat, and thus is not rational.
There is no magic to the specific we picked; it would just as well to do a different base, like binary
or to use a different digit-changing rule like
or to grab a different set of digits
etc.