Cantor’s diagonal proof

Posted in Math by Mike Stay on 2012 August 20

There’s a riddle about a library where the index had two parts, each in its own book. The first index book listed every book whose title appeared between its own covers; nearly every book in the library was listed in this index, since the title is typically on the title page. The other index book, a mere pamphlet really, was for those rare cases where the title was not between the covers of the book. Neither index had a title page, just a list of book titles and what shelf each book was on.

In which book was the first book listed? It could have been listed in itself, which is consistent with the claim that it lists all the books that contain their own titles. Or it could have been listed in the second book and not in itself, which would also be consistent.

The riddle is this: in which index was the second index book listed? If we suppose that the second book did not list itself, then it would be incomplete, since it is a book in the library that does not contain its title between the covers. If we suppose that it did list itself, then it would be inconsistent, since it is supposed to list only those books that do not contain their own titles. There is no way for the second index book to be both consistent and complete.

Georg Cantor was a mathematician who used this idea to show that there are different sizes of infinity! But before I go there, consider the Munduruku tribe of the Amazon, which has no words for specific numbers larger than five; how would a man with eight children tell if he has enough fruit to give one to each child? He would probably name each child and set aside a piece of fruit for them—that is, he would set up an isomorphism between the children and the fruit. Even though he cannot count either set, he knows that they are the same size.

We can do the same thing to compare infinite sets: even though we can’t count them, if we can show that there is an isomorphism between two infinite sets, we know they are the same size. Likewise, if we can prove that there is no possible isomorphism between the sets, then they must be different sizes.

So now suppose that we take the set of natural numbers {0, 1, 2, 3, …} and the set of positive even numbers {0, 2, 4, 6, …}. These sets both have infinitely many elements. Are they the same size? We can double every natural number and get an even one, and halve every positive even number and get a natural number. That’s an isomorphism, so they’re the same size.

How about natural numbers and pairs of natural numbers? Given two numbers like 32768 and 137, we can pad them to the same length and then interleave them: 3020716387; they come apart just as easily.

Since we can take the first number to be the denominator of a nonnegative rational number and the second number to be the numerator, we also find that the size of the set of rationals is the same as the size of the set of natural numbers.

Cantor came up with isomorphisms for each of these sets and thought that perhaps all infinite sets were the same size. But then he tried to come up with a way to match up the natural numbers and infinite sequences of bits, like the sequence of all zeros:

    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

or the sequence that’s all zeros except for the third one:

    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

or the sequence whose nth bit is 1 if n is prime:

    0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ...

or sequences with no pattern at all:

    0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, ...

He tried and tried, but couldn’t figure out a way to make them match up. Then he thought of an ingenious proof that it’s impossible! It uses the same insight as the library riddle above.

Suppose we try to match them up. We write in the left column a natural number and in the right column a binary sequence:

    1: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
    2: 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
    3: 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ...
    4: 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, ...
    5: 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, ...
    6: 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, ...

Consider the diagonal of the table above: 0, 0, 1, 1, 0, 1, … This sequence is number 6 above, and is like the first index book: the sixth bit in the sequence could be either 0 or 1, and it would be consistent.

Now consider the opposite of the diagonal, its “photographic negative” sequence: 1, 1, 0, 0, 1, 0, … This sequence is like the second index book: it cannot consistently appear anywhere in the table. To see that, imagine if we had already assigned this sequence to number 7. (The number 7 is arbitrary; any other number will work just as well.)  Then the table would look like this:

    1: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
    2: 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
    3: 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ...
    4: 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, ...
    5: 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, ...
    6: 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, ...
    7: 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, ...

But look at the seventh bit of sequence 6! It’s supposed to be the seventh bit along the diagonal, and it’s wrong. If we correct it, then the 7th bit of sequence 7 is wrong, since it’s supposed to be the opposite of the 7th bit of sequence 6.

This proof shows that there are too many sequences of bits to match up to natural numbers. No matter how we try match them up, we can always find a contradiction by looking at the sequence defined by the opposite of the diagonal sequence.  And as if two different sizes of infinity weren’t enough, Cantor was able to repeat this process and show that there are infinitely many sizes of infinity, each bigger than the last!

Many influential mathematicians didn’t like this idea, and attacked Cantor personally rather than trying to find fault with his proof.  Religious philosophers misinterpreted his results and equated the idea of multiple infinities with pantheism!  Confronted with so much antagonism, Cantor often fought with depression.

He persevered, however, and later in life was greatly praised for his work. The Royal Society gave him their highest honor, the Sylvester Medal; and no less a mathematician than David Hilbert exclaimed, “No one shall expel us from the paradise that Cantor has created.”


6 Responses

Subscribe to comments with RSS.

  1. Jason said, on 2012 August 20 at 5:33 pm

    Proofs involving infinity are like magic tricks. They hide the difficulties where you can’t see them.
    If we take away the … at the end of each number and consider all 2-bit binary values:

    0: 00
    1: 01
    2: 10
    3: 11

    inverse of the diagonal: 10.

    But 10 is in the list! In order for Cantor’s construction to work on our 4 numbers, each one would have to have 4 bits.

    But if we’re considering 4-bit numbers, we can list 16 of them.

    So for any list of numbers in base b that each have k digits, Cantor’s construction only works if we have no more than k elements in the list. But there are b^k possible elements, and it’s easy to enumerate them all.

    For example, in our example of base 2 values with 2 bits, Cantor only produces an outsider if your list has 2 or fewer elements, even though it’s obvious that our list should have 4 elements.

    So Cantor basically keeps moving the goal posts exponentially — “wait, I need one more digit to make sure my (decimal) number isn’t in your list.” “But if we add one more digit, I can fit 10x as many numbers in my list!”
    So whether you accept Cantor’s argument depends on what you think happens out in those “…”s.
    I’m only comfortable thinking in terms of things I could construct, so I call myself a Constructivist. But it’s kind of like being a skeptic at a revival; it limits the range of conversation topics.

    • Mike Stay said, on 2012 August 20 at 5:52 pm

      Kroenecker began the development of constructivism in response to Cantor. He basically objected to the idea of sequences with no pattern: if you can’t construct the pattern, why should we think it exists? A modern constructivist would say, “There’s no program you could write that would output the bits of such a sequence. In fact, if you consider only those sequences that you can write programs to output, then there are clearly only as many as the natural numbers: each program is a finite string of bits, and if you stick a 1 in front of such a string of bits, you get the binary expansion of a natural number.”

      It all depends on what rules you’re playing by. If you use Zermelo–Fraenkel set theory with the axiom of choice, then Cantor’s proof holds. If you use constructive Zermelo–Fraenkel set theory, then you can’t construct the table, and the proof above suffices to show there’s only one infinity. And the ultrafinitists deny that even the natural numbers are infinite!

      • Jason said, on 2012 August 20 at 5:56 pm

        Okay then I’m definitely going to be an ultrafinitist when I grow up.

      • Mike Stay said, on 2012 August 20 at 5:58 pm

        Hahaha! :D

  2. Douglas Summers-Stay said, on 2012 August 21 at 5:05 am

    I’m okay with people talking about infinities, but I’ve always been uncomfortable with the idea of calling whatever it is that Cantor is measuring “size.” He hasn’t discovered that one infinity is bigger than another, or that there are as many even integers as integers; such concepts as “bigger” and “as many” don’t apply to infinities. I think we ought to use terms like “can be put into a correspondence with” or “any correspondence we can set up will always leave elements out.”

    • Mike Stay said, on 2012 August 21 at 6:58 am

      I don’t understand why you’re uncomfortable with saying one transfinite number is bigger than another when there’s a perfectly good total ordering on them.

Leave a Reply

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

You are commenting using your 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

%d bloggers like this: