In 1874, Georg Cantor proved a result that shook the world of mathematics: that no infinite sequence, no matter how cleverly constructed, can contain every real number. His proof was so controversial that it nearly ruined his career. Famed French mathematician Henri Poncare described Cantor’s ideas as a “grave disease”. Cantor’s former professor Leopold Kronecker called Cantor a “scientific charlatan” and “corrupter of youth”. Cantor even briefly considered swapping fields to philosophy.
At this point, any math-history enthusiast worth their weight in black-board chalk will likely guess what proof I am referring to: Cantor’s famed diagionalization argument. The only problem is, they’d be wrong.
The diagionalization argument, which can be used to prove the same result, wasn’t published for another 17 years until 1891. In fact, Cantor’s original proof relied on nothing but standard elementary number theory.
The Theorem: There is no sequence of real numbers containing every real number.
Recall that the real numbers include non-fractions like and . The theorem claims that for every infinite sequence of real numbers, there must be some real number not in the sequence. Notice that the same can’t be said for the integers. For example, the sequence contains every integer. In fact, the same can’t even be said for pairs of integers; if you’re clever you can construct a sequence containing all the ways there are to pair up two integers. Since every rational number can be written as a fraction of two integers, it follows that one can also list off all the rational numbers. So the fact that such a list cannot be made for the reals should, apriori, be kind of surprising.
Cantor’s Original Proof: Suppose there is a sequence containing every real number. In other words, for every real number , there is some position such that . Create two variables and (top and bottom) initialized to be the first two elements of the sequence. For simplicity, we will assume . Start looking at the elements in the sequence. Each time we encounter an element between and , change one of the two variables to take on that element’s value. Each time alternate which variable takes on a new value. Keep track of the values of and as and .
For example, if the sequence is , then and would start off as and . The first element between and that we find is , leading us increase to . The next value in the list between and (now and ) is , leading us to decrease to . The next value in the list between and (now and ) is , leading us to increase to . The process continues on forever (and, in general, the elements of the list won’t all be integers like in this example). In particular, if really does contain every real number then the process will never stop and we will always find new numbers between and .
At this point, Cantor asked a crucial question. What is ? In particular, because is a strictly increasing sequence which is bounded above by , the limit exists and is well defined.
Cantor realized that this leads to a problem. In particular, it turns out must remain between and at all times. Indeed if for some , then since is strictly increasing cannot be . And if for some , then since can never exceed any value takes on, it follows that .
The problem, Cantor realized, is that if must always remain between and , then there is no way that can appear in the sequence. In particular, if does appear, then when we reach in the sequence , we will advance one of or to take its value (since is between and ). But then once we advance both and one more time (increasing and reducing ), will no longer be between them. This shows that cannot appear anywhere in the list, which, in turn, implies that the list cannot contain all real numbers after all, a contradiction.