Larger infinities and the diagonal proof

It's time to continue my probably never-ending series on infinite sets.

A brief review (see here)

Consider Hilbert's Hotel, which has an infinite number of rooms, one for each positive integer (1, 2, 3, ...).  If we take the set of all rooms in Hillbert's Hotel, we can assign that set a "cardinality" which is sort of like the number of objects in the set.  However, a cardinality doesn't have to be a number; it can be infinite.  Two sets of objects have equal cardinality if they can be shuffled around and matched one to one.  For example, if we take all the guests from two infinite hotels, we can shuffle them around and fit them in one infinite hotel.  Therefore, we can say one hotel has the same cardinality as two hotels.

The question is, "Can we build a hotel which has greater cardinality than Hilbert's Hotel?  Is there a 'larger' infinity?"

Unfortunately, I'm going to have to drop the hotel analogy, because it will become cumbersome before long.

The Diagonal Proof

Let's consider the set of real numbers between 0 and 1.  That includes both the rational and irrational numbers.  Each number can be expressed as an infinite decimal expansion.

Examples:
1/2 = 0.50000000...
1/3 = 0.33333333...
π - 3 = 0.14159265...

Some of these numbers (ie the rational numbers) repeat themselves, while others (ie the irrational numbers) never repeat themselves.

Now let's compare the set of real numbers between 0 and 1 to the set of positive integers (1, 2, 3, ...).  Do these sets have the same cardinality?  They both have infinite cardinality, so why not?  Maybe there's a way to shuffle the positive integers and match them one to one with the real numbers.  Why don't we just try it and find out?

1 → 0.50000000... = 1/2
2 → 0.33333333... = 1/3
3 → 0.14159265... = π-3
4 → 0.70710678... = sqrt(1/2)
5 → 0.69314718... = ln(2)
6 → 0.71428571... = 5/7
...

It looks like I still have a long ways to go before I hit every single real number between 0 and 1, but who's to say that it can't happen?  Crazier things have happened in mathematics.  But it turns out that this particular task is impossible.  Let me show you one number that we will never hit.

First, take the first digit of the first number, the second digit of the second number, the third digit of the third number, and so on.

1 → 0.50000000... = 1/2
2 → 0.33333333... = 1/3
3 → 0.14159265... = π-3
4 → 0.70710678... = sqrt(1/2)
5 → 0.69314718... = ln(2)
6 → 0.71428571... = 5/7
...
Result: 0.531145...

Now, take each digit, and add one to it.  If it's a 5, change it to a 6.  If it's a 9, change it to a 0.

Result: 0.642256...

This number will never get hit.  It can't be hit by the first number because the first digit doesn't match.  It can't be hit by the second number because the second digit doesn't match.  It can't be hit by the Nth number because the Nth digit doesn't match.  This is Georg Cantor's so-called Diagonal Proof.

No matter how we shuffle around the numbers, I will always be able to construct such a number that will never get hit.  In conclusion, the set of real numbers will always be larger than the set of integers.  We say that the real numbers has a larger cardinality than the set of positive integers.*

A digression on the Continuum Hypothesis

The Continuum Hypothesis states that there is no set which has cardinality greater than the positive integers and lesser than the real numbers.  It was conjectured by Georg Cantor in 1877, but he had no proof.

We still have no proof of the Continuum Hypothesis, but now we know why.  Mathematicians have proven that the Continuum Hypothesis is impossible to prove or disprove without taking new assumptions.  If you have trouble wrapping your head around that, rest assured that you are not alone.

*Incidentally, the set of rational numbers has the same cardinality as the set of positive integers.  The set of irrational numbers has the same cardinality as the set of real numbers.

Next time: Power sets and the Barber paradox!

The series on infinite sets:
Hilbert's Hotel
Doubling the Sphere
Larger infinities and the Diagonal Proof
Power sets and the Chef Paradox  
The unmeasurable set