Some infinities are bigger than others.
(Adapted from Martin Gardner): Hotel Infinity has an infinite number of rooms — numbered 1, 2, 3, ….
Marie is working the front desk, happy that the hotel is empty and there is no work to do. But then a bus pulls up for an "Elvis Forever" convention. She is mildly surprised that it's an infinitely long bus (with seats numbered 1, 2, 3, …) — she had no idea Elvis had so many fans. Suddenly grateful she didn't take a job at a mere finite hotel, can easily accomodate all the guests: She gets on the PA, and announces that the passenger sitting in seat #i is booked into room #i.
Note that there is no mysterious "room #∞"; each guest has been given an honest-to-gosh room number.
That busload is taken care of, when one more guest pulls up. She could say the hotel is full and turn the guest away, but this guy is wearing sunglasses and a white suit with rhinestones, speaks with a drawl, and looks like a large tipper.
How can she cleverly re-arrange the current guests, to accomodate one more guest? Remember, there is not any "room #∞"; she has to assign the new guest an actual number, and tell each previous guest their new room number.
A few moments later, a van pulls up with ten (more?) Elvis impersonators. How can Marie accomodate all ten of them?
Word has gotten out that Elvis is in the house, and the press arrives — in another infinite busload! These people live on corporate expense accounts and tip freely, so Marie certainly doesn't want to turn any of them away. She already knows how to accomodate 50,000 of them, or even a googleplex of them, but she wants to book them all into the hotel, without taking forever. How can she do this?
Okay, now Marie is feeling pretty smug, having successfully booked more than two infinite busloads into the hotel. She's amused to note that at dinner time, when all the guests pile into a bus to go to the buffet, only one of the infini-buses is needed. (Each guest takes their current hotel room number and uses that as their seat number.)
She glances out the window at the hotel's infinite parking lot. To her horror, the parking lot has filled up: not only did the dinner bus return (bus #1), but an infinite number of other infini-buses (buses 2, 3, …, each with seats 1, 2, 3, …) have also pulled up, full of strapping young mathematicians screaming "Viva, Las Vegas", ready to hit the slots. ("This must be Heartbreak Hotel Infinity", she sighs.)
Marie is unsure of how to try to book all the guests, but her evil boss walks by and glibly asks her to not only handle all these guests, but to also keep an infinite number of rooms available for any more surprises.
What to do?
A Solution: Marie realizes she can't fit the busloads sequentially one after another (since bus #2, seat #1 must be assigned an actual room number, not something like "room #∞+1".) And, she can't quite try the previous trick of booking one busload at a time (each time interleaving the busload with the current guests); that would take forever! Thinking quickly, she decides to indeed try the idea of interleaving the busloads, but somehow interleaving all the busloads simultaneously.
She decides to put everybody from the first bus in to rooms 21, 22, 23, 24, …. That is, the person who arrived in bus #1, seat #i is assigned to 2i.
For the second bus, Marie can use a similar trick, using rooms 31, 32, 33, 34, …. That is, the person who arrived in bus #2,seat #i is assigned to 3i. After a moment of thought, it's clear that nobody from buses #1 and #2 will be accidentally assigned to the same room.
What about the third bus? She can't stick them into powers-of-4 rooms; those were all already taken up by the powers-of-2 people (from the first bus). Well, okay, she can skip powers of 4 and instead use rooms 51, 52, 53, 54, …. That is, the person who arrived in bus #3, seat #i is assigned to 5i. Again, it is clear that there won't be any conflicting room-assignments among people from buses 1, 2, and 3.
What is a general rule for Marie to announce on the PA, so every bus can unload? There are several options, but Marie stumbles onto this:
The person in bus #i, seat #j will be booked into room #(the i'th prime)j.We are happy with this: It is not hard to argue that under this scheme, no two different people get assigned to the same room (by unique decomposition into primes). Indeed, this also happens to leave many rooms empty, since only perfect-powers-of-primes get booked. (e.g., empty rooms include 6=2×3, 15=3×5, etc.).
Another solution:
| Room # | Bus # | ||||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | … | ||
| Seat # | 1 | 1 | 3 | 6 | 10 | 15 | … |
| 2 | 2 | 5 | 9 | 14 | … | ||
| 3 | 4 | 8 | 13 | … | |||
| 4 | 7 | 12 | … | ||||
| 5 | 11 | … | |||||
| … | … | ||||||
There are several equivalent definitions of countable (or enumerable). Let's follow the above ideas:
Previously showed, informally,
Some additional definitions & notes:
Sets A and B have the same cardinality iff there is a total bijection between them.
Hmmm, all of this suggests there are infinite sets that aren't countable!
We'll show that ℝ is not countable. Even better, we'll show a subset of ℝ, the interval [0,1], isn't countable.
| Decimal positions | |||||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | … | ||
| # | 1 | 7 | 9 | 2 | 0 | 3 | … |
| 2 | 8 | 1 | 1 | 4 | 2 | … | |
| 3 | 2 | 9 | 7 | 4 | 3 | … | |
| 4 | 9 | 3 | 8 | 0 | 1 | … | |
| 5 | 2 | 0 | 0 | 4 | 8 | … | |
| … | … | … | … | … | … | … | |
(Time permitting...) We'll also show that ℕ→ℕ is uncountable. The following is one method. A homework problem effectively asks for a second (closely related) method.
Just a brief intro…
How many possible computer programs are there? Compare that to the size of ℕ→ℕ.
Halting Problem