Can you get a room in an infinitely large, yet fully booked, hotel? There are a lot of rooms to count in Hilbert’s Grand Hotel, an infinite number of them to be exact. A common understanding of infinity is that it is at the end of counting, the last room. Start at one and end at infinity after a long walk down the hall. There are, however, many more numbers than just 1, 2, 3, etc; so how many of those are there? This is where the notion of thinking of “infinity” as the end of counting becomes complicated. Infinity is specifically bigger than any number you can count to, meaning regular intuition of math stops working. If there were a million rooms in a hotel and all were full, you couldn’t get a room; not a billion or even a trillion. But with infinite rooms, you can certainly get a room in the hotel, just tell everyone to move down by one, and you take the first room.
Now imagine a rather large group of new guests comes, infinitely large actually; how could anyone possibly give all these guests a room? Unlike when you got a room, Hilbert can’t just shift everyone over by infinite rooms. How about another, not hotel related, question, “how many even numbers are there? Odd?” It may be clear that there are the same number of evens as odds, because each make up half of the natural numbers. What if I told you that there are the same number of even numbers as natural numbers. I can hear you thinking, “How can this be?! It’s obviously half as many!” This can be explained by taking each counting number and doubling it; there will be only even numbers and you’ll never run out of numbers because there is no last counting number to double. This idea can be used to fit infinitely more guests into the hotel; scale the room numbers and fit an infinite number of guests between all the current guests. So now Hilbert knows how to add an infinite number of guests into the hotel. He should be done now, right? Wrong.
Word of Hilbert’s extremely spacious hotel has now attracted even more guests than before, an infinite number of buses, each carrying an infinite number of guests, arrive. Once again, the previous methods fail as the room numbers cannot scale by infinity. To fit this many guests, it requires some clever mathematical tricks. One possible solution is to send guests to powers of prime numbers; for example, the guests in room i go to room 2i and those in the first bus in seat n go to 3n, continued for infinite prime numbers for each bus. Another creative solution is to interweave the numbers representing the bus and the seat with the first digit of each, the second digit of each, etc to assign the new room numbers. Each of these methods is able to send any guest represented by a pair of natural numbers (a,b) to a single natural number in the hotel. There are many more possible solutions to this particular section of the problem, an interesting question for the reader’s consideration.
There was a single bus left over after Hilbert somehow found rooms for the infinite busses of infinite guests; however, the guests on this last bus don’t have seat numbers, rather they are all identified by an infinitely long name. It may, at first, seem like a doable task for the expert room arranger; however, this is an impossible task. Unlike the buses of guests, you cannot count these named guests. Since previous groups had a first and second guest, it was possible to fit them into the hotel using the clever tricks explained previously. The group of named guests is simply too large to fit into the hotel. Consider an infinite list of these infinitely long names of the guests. If you generate a new name by changing the first letter of the first name, second letter of the second name, and continue for all the names, you will get a new infinitely long name that is not in the list. You can always “find” new names that make the list even longer. Even if you arranged the names in alphabetical order, you could simply “make” more names in between those names, making it impossible to order and number the new group. Since the members of the group cannot be properly assigned natural numbers, none of the previously explored tricks can fit them into the hotel. Defeated, the hotel manager resigns on the spot, having made all the money he could need from the admission of the previous infinite guests.
Hilbert’s hotel is an example of the difference in cardinality, or size, of sets. Groups with the same or less cardinality as the room numbers could fit, but even then there was an infinite group too large for the infinite hotel. This is illustrated by numbered guests being able to fit into numbered rooms, but named guests could not fit because infinitely more names could always be generated from any infinite list. The number of rooms is considered to be infinite, but “countably’’ infinite, meaning it corresponds in a one-to-one relationship with the counting numbers. As touched on when covering the named guests, the group of guests could not be counted, and therefore could not be admitted. This larger, continually generated infinity, is referred to as “uncountably” infinite, since it cannot be in a one-to-one relationship with counting numbers. The notion of different size infinities is crucial in the study of different sets of numbers.
The technique used to fit guests into Hilbert’s hotel is a valid approach to other, arguably more mathematical, questions. For example, does there exist a function that sends the interval [0,1) to (0,1) with everything in the latter interval being “hit” by a unique number in the previous interval. It turns out that there is. The function exists by “shifting” all the numbers that can be represented by 1/n over to 1/(n+1), sending 0 to ½, and sending the rest of the numbers to themselves.
The existence of a function that sends any set to any other set given by every element of the second set being “hit” by a unique element in the previous set means that the sets have the same cardinality. These functions can be used to compare the sizes of different sets; many of these comparisons require interesting tricks of grouping and moving infinitely large sets around, like those presented in both problems.