The Proof That Shook The World Had No Diagonals

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 a_1, a_2, \ldots containing every real number.

Recall that the real numbers include non-fractions like \pi and \sqrt{2}. 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 0, 1, -1, 2, -2, 3, -3, \ldots 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 a_1, a_2, a_3, \ldots containing every real number. In other words, for every real number r, there is some position i such that a_i = r. Create two variables t and b (top and bottom) initialized to be the first two elements of the sequence. For simplicity, we will assume b < t. Start looking at the elements in the sequence. Each time we encounter an element between t and b, 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 b and t as b_1, b_2, \ldots and t_1, t_2, \ldots.

For example, if the sequence is 1, 6, 8, 3, 2, 11, 5, 4, \ldots, then t and b would start off as b_1 = 1 and t_1=6. The first element between b and t that we find is 3, leading us increase b to b_2 = 3. The next value in the list between b and t (now 3 and 6) is 5, leading us to decrease t to t_2 = 5. The next value in the list between b and t (now 3 and 5) is 4, leading us to increase b to b_3 = 4. 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 a_1, a_2, \ldots really does contain every real number then the process will never stop and we will always find new numbers between b and t.

At this point, Cantor asked a crucial question. What is L =\lim_{i \rightarrow \inf} b_i? In particular, because b_1, b_2, \ldots is a strictly increasing sequence which is bounded above by t, the limit L exists and is well defined.

Cantor realized that this leads to a problem. In particular, it turns out L must remain between b and t at all times. Indeed if L <b_i for some i, then since b is strictly increasing L cannot be \lim_{i \rightarrow \inf} b_i. And if L > t_i for some i, then since b can never exceed any value t takes on, it follows that \lim_{i \rightarrow \inf}b_i \le t_i < L.

The problem, Cantor realized, is that if L must always remain between b and t, then there is no way that L can appear in the sequence. In particular, if L does appear, then when we reach L in the sequence a_1, a_2, \ldots, we will advance one of b or t to take its value (since L is between b and t). But then once we advance both b and t one more time (increasing b and reducing t), L will no longer be between them. This shows that L cannot appear anywhere in the list, which, in turn, implies that the list cannot contain all real numbers after all, a contradiction.

Advertisements

Published by

William Kuszmaul

I am an MIT Ph.D. student in the computer science department. My research focuses on algorithms and combinatorics.

4 thoughts on “The Proof That Shook The World Had No Diagonals”

  1. I have gone through the proof multiple times, and I don’t see why it wouldn’t work for rational numbers. I know how to demonstrate that the rational numbers map onto the integers, so this proof can’t work for rational numbers. I just don’t know why.

    Also, the proof seems to assume the answer, that there are always numbers between b and t.

    Like

    1. Good Questions! Let me try to answer both.

      The reason the proof doesn’t work over the rationals is that, for the rationals, it’s not a contradiction for the limit L to not appear in the sequence. Indeed, as long as L is irrational, then it shouldn’t appear in the sequence.

      To answer the second question (about the numbers between b and t), it’s true that the proof does observe there always will be future numbers that are between the current values of b and t. But note that this is different from assuming there is a single number that will always remain between b and t (without b and t every getting so close to each other that the number eventually stops being between them). The latter is what the limit L would have to do, which would be a contradiction since no number in the list can remain between b and t forever.

      Does that make sense?

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s