(from Hilbert's Grand JavaScript School)
Bertie goes home, exhausted, and dreams that having graduated everyone at the end of Day Five, things are busier than ever. In his dreams he imagines an infinite number of galactic superclusters, each containing an infinite number of galaxies, each containing an infinite number of stars, each containing an infinite number of worlds, each containing an infinite number of oceans, each containing an infinite number of aircraft carriers, each containing an infinite number of buses, each containing an infinite number of students.
He awakens and reasons that what he is dealing with are powers of infinity. A simple infinity is infinity to the first power. Two infinities (buses and students) is infinity to the second power. Three infinities (aircraft carriers, buses, and students) is infinity to the third power. And so forth up to galactic superclusters, infinity to the eighth power.
He quickly observes that no matter what finite power he chooses, he can put the total number of students into a one-to-one correspondence with the countably infinite number of seats in his auditorium. But then he wonders... What if he has infinity raised to the power of infinity students to seat?
He imagines some kind of crazy infinite series of ever-greater cosmological containers, universes contained within the atoms of other universes, time and space folding over unto itself. In such a crazy circumstance, can all the students be accommodated?
Good question.
Presume there is some algorithm that makes it possible. In that case, every student from the infinity to the power of infinity students can be assigned to one of the seats, numbered 0, 1, 2, .... To describe how that works, we'll need a way of identfying each student.
The list of infinities can be put into a correspondance with the natural numbers, it might look something like this:
| Infinity | Number |
|---|---|
| Seat on bus | 0 |
| Bus | 1 |
| Aircraft Carrier | 2 |
| Ocean | 3 |
| Planet | 4 |
| Star | 5 |
| Galaxy | 6 |
| Supercluster | 7 |
| ... | ∞ |
Each student has a unique, infinitely long vector of numbers. For example, Alice might have seat6 on bus 42 on Aircraft Carrier 14, and so on (we haven't identified her ocean number, planet number, or any of the other numbers, but obviously she has them). Her vector would be [6, 42, 14, ...]. Meaning, she has a 6 in the position 0, a 42 in position 1, a 14 in position 2, and so on with the other numbers filled in appropriately. Each student has a unique vector just like this, but with different numbers, and it follows that every possible vector represents a student that must be seated.
Now we have hypothesized that there is some wonderful method, maybe diagonalization, maybe something else, that puts the students into a one-to-one correspodance with seats numbered 0, 1, 2, .... That means that we can put all the possible vectors into a one-to-one correspondance with the numbers.
If we can prove that there is at least one vector that is left out when the vectors are put into a one-to-one correspondance with the numbers, we can prove that it is not possible to put all the vectors into a one-to-one correspondance with the countably infinite numbers.
So let's say that Bertie seats all the students from infinity to the power of infinity students. We will locate at least one student who has not been seated. Let us go to seat zero. Say that "Fred" is sitting there. We ask Fred "What is in position zero of your vector?"
Fred may answer, 637. Fine. We pick any number except 637, and we put that in position zero of a new vector: [18, ...]. We haven't filled in the rest of the vector, but it seems obvious that there are an infinite number of vectors that do not start with 637, and since every such vector represents a student, there are an infinite number of students that are not sitting in seat 0.
Now we move to the next seat and say hello to Stephanie. "What is in position one of your vector?" Stephanie answers 12. We put any number except 12 in position one of our vector, it might now be [18, 934]. Once again, we know that there are an infinite number of vectors that do not contain a 637 in position 0, and also do not contain a 12 in position 1. So we know that each of those infinite number of vectors represents a student that is not in seat 0 and is also not in seat 1.
We move to the next seat, and repeat the process, and keep going for every seat in the auditorium.
What we are building is a vector where the number at each position of the vector differs from that number belonging to the student in that numbered seat. Therefore, we know that this vector does not belong to any of the students in the auditorium. Just as we know that the vector represents a student not in seat 0 and not in seat 1, we know they aren't in 2, aren't in seat 3, and in fact aren't in any of the countably infinite seats.
If someone claims it belongs to, say the person in seat 65537, we can say "no, because it differs from that person's vector in position 65537. Our vector differs from every seated student's vector, and therefore it represents a student that has not been seated.
And we can do this no matter what method is used to seat the students. Thus proving that no method will work.
This establishes that countable infinity raised to the power of countable infinity is uncountable infinity. It is larger in some fundamental sense than countable infinity. In fact, it is uncountably larger than countable infinity. How do we know this?
Well, consider this. How many numbers can we put in position zero of a vector representing a student who is not in the auditorium? Countable infinity minus one, any number except 637. That's countable infinity. Same for position one, position, two, and so on up to position countable infinity.
So the number of students not in the auditorium is countable infinity times countable infinity times countable infinity... countable infinity times. In other words, there are countable infinity raised to the power of countable infinity students not seated in the auditorium no matter what algorithm we use to seat students.
This proves that uncountable infinity is uncountably larger than countable infinity. And it matches our intuition: It can't be a finite number of students larger than countable infinity, because countable infinity plus a finite number is still countable infinity. And it can't be a countably infinite number of students larger than countable infinity, because countable infinity plus countable infinity is still countable infinity.
Thus we know that infinity raised to the power of infinity is uncountably larger than our countable infinity.
I first read this proof in One, Two, Three, Infinity. I was a young boy, and the discussion of countable and uncountable infinities fascinated me, as did the rest of the book. Like many others, I think I was spurred to an interest in mathematics and science by its ability to explain complicated things in easy language.