Uncountably Infinite Nuts

Oops, missed one

An Excuse to Learn German

Many people know there are more real numbers than counting numbers, and some don't. Some even find the results contentious or unsettling. Here, rather than getting into the social ramifications of this concept, I'd like to run through the operative part of the most well known proof. I will talk about the diagonal argument.

The diagonal argument, as far as I know, was first introduced by Georg Cantor in his 1891 article "Über eine elementare Frage der Mannigfaltigkeitslehre". I wasn't able to find a pdf copy of the original paper, but Jan scared up this excerpt from a book about Cantor and written by Ernst Zermelo in 1932...I think I can trust the source. The 1891 proof wasn't actually Cantor's first proof that real numbers are more numerous than counting numbers, but it is prettier than his 1874 effort.

The construction of the diagonal argument is pretty simple. Consider a gambler, recently relieved of his mortal obligations. When he arrives in hell, the devil delivers his twisted punishment. The ex-man is to flip a coin for the rest of time. In mathematical terms, the results of this eternal obsession would look like: $$\text{game}_1=\text{toss}_{1,1},\text{toss}_{1,2},\ldots,\text{toss}_{1,n},\ldots$$

It so happens, that the entry queue to the wrong side of the Styx is rather long, and Satan has to streamline his process. So, every wayward gambler, for all time, gets the same compulsory trigger thumb (hey, it's original to them). $$ \begin{array}{c} \text{game}_1=\text{toss}_{1,1},\text{toss}_{1,2},\ldots\text{toss}_{1,n},\ldots\ \\ \text{game}_2=\text{toss}_{2,1},\text{toss}_{2,2},\ldots\text{toss}_{2,n},\ldots\ \\ \vdots \\ \text{game}_m=\text{toss}_{m,1},\text{toss}_{m,2},\ldots\text{toss}_{m,n},\ldots\ \\ \vdots \end{array} $$

Now, it would seem perfectly reasonable to think that infinitely many sinners would produce every possible permutation of coin tosses. However, imagine a game where the first toss went the opposite way from the first toss of the first gambler. Then the second toss went different from the second toss of the second gambler. And, the third toss went differently from the third toss of the third gambler, and so on. The game would be different from every game in the list. Meaning, infinitely many games won't account for all possible results.

My favorite part of this proof is the reveal. Up to this point, there has been no need to explicitly evoke real numbers or counting numbers. The argument doesn't need them. However, as anyone who has tried to write the decimal form of $^1/_3$ will testify, the digits of a real number can go on forever. So, it's not too hard to see the sequence of tosses as the fractional digits of a binary number. What's cooler, is that by starting with one game, and then defining another, and another, we use precisely the same construction method as the counting numbers; they're built-in to the problem. The journey from assumptions to theorem isn't a laborious slog, it's over before you realize you've started. Needless to say, I like it.