Tuesday, 15 June, 2004

Let me share an insight I had today walking home from work. It involves Cantor's proof that the cardinality of the reals is not equal to cardinality of the integers.

Here's the proof in short. A set is the same size (cardinality) as another set if it is possible to pair off the members of the set such that:

1. You have a single element from both sets in each pair.
2. No element can be used in more than one pair.
3. Every element can be paired with every other element; there are no over elements

This pairing can be done arbitrarily. The nature of the pairing doesn't matter terribly at all.. just the fact they can be paired.. For example the set {Orange, chair, Cow} is equal in size to {1,30,19.5} because I can put 1 with Orange, 30 with chair and 19.5 with Cow. I could have equally put Chair with 1, Cow with 30 and 19.5 with Orange

This isn't terribly earth shattering with sets of finite size , however things get a lot more interesting when we consider sets of infinite size.

First we have to define infinity:

Definition: A set is infinite in size if I can find a subset that has the same cardinality as the parent set.

Example: The set of whole numbers are infinite because I can take a subset, like the set of Odd numbers and pair each whole number with an odd number and not miss any.

 Whole Numbers: 1 2 3 4 5 .. Odd Whole Numbers: 1 3 5 7 9 ..

That list will go on forever and we'll have a one-to-one pairing between the odd and whole numbers. we've therefore proved the set of whole numbers is consistent with our definition of infinity.

What about the set of real numbers? Well, these too are infinite in supply. Imagine we have two lines A and B. B is half the length of A. We can construct B from A by removing half of the line A so it is safe to call B a subset of A. We can map each point on the line B to each point on the line A by multiplying the distance of that point along B by 2 to give distance of the corresponding point on line A. Every single point is covered and none are missed.

The question now is are these two infinities the same size? As you've probably already guessed the answer is no.

If whole numbers and the reals are the same size we should be able to pair off each real with a whole number such that the three criteria stated above are met. I now show that such as pairing is impossible.

First, assume we could construct such a pairing. Rather than considering all of the real numbers we'll take a subset of them namely all the reals less than one but greater than zero.

Whole Number Real Number
10 .2 97 41 3..
20 .9 75 21 1..
30 .7 49 05 8..
40 .5 70 01 9..
50 .8 14 51 2..
.. ..

This list goes on forever but eventually every single real number will be paired with an integer. Or will it? Is it possible to construct a real number that isn't on the list even when that list is infintely long? Yes. Here's how. See the numbers marked in bold? Imagine that we continue on that diagonal right to the bottom of the list. Let us construct a new number, r, such that each digit of r is different to it's bolded partner in the list.

So the first bolded digit is 2. Let the first digit after the deciminal point of r equal 1 . The second bolded digit is 7. Let the second bolded digit is 7, so let the second digit of r equal 1. The 3rd bolded digit is 9 so let the 3rd digit of r equal 1. The fourth bolded digit of r is 0, so let the fourth digit of r equal 1. The 5th bolded digit is 1 so let the 5th digit of r equal 0 and so on. So we get r=0.11110... The question now is does this number appear in the list? No. r differs from the first real in the list in the first digit, the second real in the second digit, the third real in the third digit the fourth real in the fourth digit.. and so on and so on. The real is nowhere in the list since it differs from every real in the list in at least one digit. This means that the assumption that such a mapping exists is incorrect. The sizes of the real numbers and the whole numbers are different even though both are infinite in size Why does this proof work? I don't think this proof by itself does enough to convince the reader of the truth it's trying to demonstrate. I find a useful method for understanding a proof is to try the same technique against entities that it shouldn't work with. I then try to understand why the proof fails and hope that gives some insight in to the orignal proof.

An obvious question might be why can't we apply this diagonal argument to the whole numbers and arrive at a new number that isn't in the list of whole number? Well the diagonal process works on the whole of the list. The whole numbers beating on the door of infinity at the bottom of list will be infinitely long. Since our process dictates that each digit must be different in at least one digit to every number in the list this implies that our new number is infinite in size. A number of infinite size is not an whole number as it doesn't obey Peano's axioms.

What of the set of rational numbers (numbers where one whole number is divided by another non-zero whole number) are they the same size as the reals or are they the same size as the integers? We can infact put the rationals in a one to one correspondence with the whole numbers. How you ask?

1 2 3 4 1/1 1/2 1/3 1/4 2/1 2/2 2/3 1/2 3/1 3/2 3/3 3/4 4/1 4/2 4/3 4/4

Suppose the above table extended in both directions off to infinity. That list certainly contains every single rational number one can construct. We can pair each integer off with a single element of this table as follows. Start at 1/1, we pair this with 1, go down to 2/1 (pair it with 2) the diagonal up to 1/2 (pair it with 3) then right to 1/3 (pair with 4) then down diagonally left to 2/2 (carry on counting) and 3/1, then down to 4/1. Go up digonal right to 3/2, 2/3 and 1/4 then you'd move right to 1/5 then down diagonal left to 1/2, 3/3, 5/2.. and so on. If you continued this infinite process you would get through the entire table without missing any entries.

This correspondence isn't one-to-one as required for the sets to be equal in size because the table contains many duplicated values. If we remove all the duplicate values then this puts the whole numbers and the rationals on a one-to-one mapping. They are equal in size.

So what are the consequences of the fact there are more reals than whole numbers? Well, we can encode any sentence in the english language as an whole number. We can make A=1, B=2, C=3 and so on (not forgetting to include punctuation marks) then we just substitute each letter for it's number to make a single huge number. Since the set of reals is bigger than the whole numbers this implies there are more real numbers than you can name. Even if you had an infinite list of names it still wouldn't be big enough to name every real. This leads us directly to a very profound statement. We can encode a computer program in English which can in turn be encoded into a whole number. A portion of these programs (but still infinite hehe) will be programs for computing the values of various numbers, such as pi. However, there are more real numbers than there are programs. So we're left with the weird realisation that most of the real numbers are incomputable.

In fact, if you randomly chose a real number then there is zero probability (yes zero) that you will pick a computable real. We're back to the argument of whether a number really exists if you can't compute it. We saw a brief glimpse of such a beast in the proof that the reals are bigger than whole numbers - the real that we constructed to prove the result is incomputable. We can't even obtain an approximation of that number yet it's existence is unquestionable. If you don't like that particular example try Omega. It's the probability of a random program halting - it's incomputable and it's real.

When someone has a problem with the square root of minus one send them to this blog entry. I think the square root of minus one is quite tame concept in comparison to the idea of an incomputable number.

Simon.

21:13:51 GMT | #Maths | Permalink