One of the slickest proofs of all time is using Georg Cantor‘s 1891 diagonal argument in proving that the real numbers constitute an uncountable set, that is, they cannot be put in a bijective correspondence with . Strictly speaking, Cantor original paper only proved that the set of all -sequences is uncountable. However since it is easy to argue that the set of all such sequences and have the same cardinality, indirectly we get a proof for the uncountable nature of the reals. Moreover, the argument given by Cantor in his proof can be easily modified to give a direct proof for the uncountability of the reals. This is what we do presently.
Theorem: is uncountable.
Proof: We will accept that every real number has a decimal expansion, and it is uniquely determined by if one agrees never to terminate the expansion with an infinite string of ‘s. The proof is based on contradiction, and so we suppose that is not uncountable. Then it must be that is countable and we can make a list of all the elements of along with their decimal expansion as follows:
We now consider the real number which is defined by if and otherwise. It is clear that this number differs from every in the list in at least the ‘th position. Hence this list is incomplete, a contradiction.