This evening I was telling my friend Gerry about the recent blog thread here that included Euclid’s proof of the infinity of prime numbers. Gerry said that he was glad it was so easy to show that there are infinitely many prime numbers, but he was still unhappy that he hasn’t been able to explain to anybody, in a simple way, why there are more real numbers (eg: numbers that have an infinite number of decimal places, like 0.3278594…) than there are counting numbers (numbers like 1, 2, 3, …).
I told Gerry that in fact there is a simple way to explain this. By an interesting coincidence, the proof that Georg Cantor came up with of this in 1874 was in some ways the same proof that Euclid had used 2700 years earlier for primes. Actually what is amazing is that it took twenty seven centuries for somebody to realize that Euclid’s method could be applied to this other question.
To make things simpler, Cantor considered only real numbers between zero and one. He asked: How many real numbers are there between zero and one (eg: 0.7, 0.23528315…, etc)? Are there more such real numbers than there are counting numbers? If you can make an infinite list of all the real numbers between zero and one (a first one, a second one, and so forth), then you’ll have shown that no, there aren’t more such real numbers than there are counting numbers.
Cantor proved that yes, there are more real numbers between zero and one than there are counting numbers. He basically adapted the same method that Euclid had used more than two thousand years earlier for primes – the idea that we talked about yesterday – except he upped the ante by letting the list be infinite.
Assume that you have an infinite list of all the real numbers between zero and one. So on your list there’s a first number, a second number, a third number, all the way up to infinity. The question is: Is every possible real number between zero and one contained on your list?
If you can find even one real number between zero and one that’s not on your list, then that means that it’s impossible to list all the real numbers between zero and one. In other words, that there must be more real numbers between zero and one than there are counting numbers.
It’s the same thing that Euclid had done – Euclid had said: “Let’s make a finite list of what we claim are all the prime numbers. Now let’s use that list to show that there must be at least one prime number that’s not on the list. Once we do that, we’ve proven that there is no finite list containing all the prime numbers. So there must be an infinite number of prime numbers.”
Similarly, Cantor said: “Let’s make an infinite, but countable, list of what we claim are all the real numbers between zero and one. Now let’s use that list to show that there must be at least one real number between zero and one that’s not on the list. Once we do that, we’ve proven that there is no countably infinite list containing all the real numbers between zero and one. So there must be an uncountably infinite number of real numbers between zero and one.”
Here was Cantor’s trick to produce a number that’s not on the list: it’s a very simple, elegant trick. Let’s say you have such a list. Each of the numbers on your list can be written in decimal form. Maybe your list looks something like this:
1) 0.73289473682958…
2) 0.32562839727636…
3) 0.27462849637426…
…
To make things easier to understand, let’s show the list again, but this time highlight the 1/10ths place in the first list entry, the 1/100ths place in the second list entry, the 1/1000ths place in the third list entry, and so on:
1) 0.73289473682958…
2) 0.32562839727636…
3) 0.27462849637426…
…
To construct a number between zero and one that’s not on the list, just make a new number that has a different digit in the 1/10ths place from your first list entry, a different digit in the 1/100ths place from your second list entry, a different digit in the 1/1000ths place from your third list entry, and so on.
For example, the new number you construct, to three decimal places, might look like: 0.835… (I’ve just added one to each of the highlighted digits – pulling out the “7”, “2”, 4″, etc., and replacing each one with a digit that’s one greater).
So here we have a real number that’s clearly between zero and one, but isn’t on your list. And you can use the same recipe to build such a number for any such list that you try to make.
And so, just as Euclid showed around 300 BC that there are an infinite number of prime numbers, Georg Cantor in 1874 came up with a very simple and elegant way to show that there must be more than one kind of infinity: The real numbers between zero and one form a bigger infinity than do the counting numbers 1,2,3,….
How cool is that?