Cantor’s diagonal argument

And now for something completely different. I’ve had enough of blogging about the debt ceiling and US fiscal problems. Have some weekend math blogging.

Earlier this year, as I was reading Neal Stephenson’s Cryptonomicon, I got interested in mathematician and computer science pioneer Alan Turing, who appears as a character in the book. I looked for a biography, decided I didn’t really want a biography, and settled instead on Charles Petzold’s The Annotated Turing.

It is a remarkable book. As the subtitle indicates, it is a “guided tour” through Turing’s famous 1936 paper on computability. Literally every word of Turing’s paper appears in the text, bookended and interspersed with introductory material, commentary, and reflection. If you read this book, you will have read Turing’s entire paper, and perhaps understood it.

I am not an especially mathematical economist; I use toy models from time to time, but my view is that big, complex models are not especially illuminating. Nevertheless, I was fascinated with one famous mathematical proof that was offered in the book as introductory material for the problem that Turing was trying to solve. It has rattled around in my brain for the past six months. It is so unsettling that I thought I would share the joy with my readers. The proof is called Georg Cantor’s diagonal argument. First, some background.

Take the set of natural numbers {1, 2, 3, 4, … }. How many members are there in the set? Infinitely many, right? OK, now take the set of real numbers. How many members are there in the set? Infinitely many, right? So far so good.

Here is where it starts to get tricky. The number of members of a set is called its cardinality. If the cardinality of the natural numbers is infinity, and the cardinality of the real numbers is infinity, then do these two sets have the same cardinality? Are there the same amount of natural numbers as real numbers?

Whatever your intuition is about that last question, your intuition will hardly do. We need to be methodical about this. So now lets begin the proof (I’m borrowing liberally without quotation marks from the book, pp.28-29).

Suppose we have devised some way to list all the real numbers between 0 and 1. This list will naturally be infinitely long, and we can write each entry in an infinitely-long decimal form. Here is how it might start, and note that I have marked some digits in bold.

The digits in bold run down the diagonal of this list. Use them to construct a new real number between 0 and 1.

.1531190918...

Like all the other numbers on the list, this number will have an infinite number of digits; this is because the list is infinitely long.

Now increase each individual digit by 1. If the digit is 9, make it 0:

.2642201029...

Is this new number on the original list?

On one hand, it must be, because the list is infinitely long and contains all the real numbers between 0 and 1. The new number is a real number between 0 and 1.

On the other hand, if we work through the number and the list methodically, we will see that it cannot be on the list. Is the new number the first number on the list? No, because the first digit of the number differs from the first digit of the first entry. Is the new number the second number on the list? No, because the second digit of the number differs from the second digit of the second entry. Is the new number the _n_th number on the list? No, because the _n_th digit of the number differs from the _n_th digit of the _n_th entry. Therefore, the new number, a real number between 0 and 1, cannot appear on an infinitely-long list of real numbers between 0 and 1.

We have contradicted ourselves, and that concludes the proof. It is impossible, even in principle, to denumerate the real numbers between 0 and 1. There are not just infinitely many reals between 0 and 1—there are uncountably many. There are so many that they cannot all be placed in correspondence with the natural numbers (i.e., given a spot on an infinitely-long list). Fun, right?

You may be wondering if there is a correspondence between the cardinality of the set of natural numbers and the cardinality of the set of real numbers. You’re in luck; there is! The cardinality of the set of natural numbers is of course infinity, but it is a kind of infinity that is called aleph-null. The cardinality of the set of real numbers (“the cardinality of the continuum”) is 2^(aleph-null)! That is a very big number.

Finally, if you’re still with me, I’ll offer a bonus. We can divide the real numbers into two sets: the algebraic numbers, which are numbers that can be solutions to one-variable polynomial equations with rational or integer coefficients, and transcendental numbers, which cannot be. It turns out that there are countably many algebraic numbers. You might already see where this is going. If there are 2^(aleph-null) real numbers, and aleph-null algebraic numbers, how many transcendental numbers are there? 2^(aleph-null) – aleph-null, which is exactly equal to 2^aleph-null. (If you have difficulty seeing this, try 100 instead of aleph-null: 2^100 – 100 is very close to 2^100, no?). What this means is that “almost all” numbers are transcendental.

If you want to learn how many numbers are computable versus not computable, you could do worse than reading The Annotated Turing. And we now return you to your regularly scheduled economic jeremiads.