I'm Joel David Hamkins, and I'd like to tell you about the Parable of Hilbert's Hotel. I'm a New Yorker, and I noticed one day a grand hotel going up across the street, one with infinitely many rooms. It was quite an elegant establishment: each suite occupied an entire floor, beginning with room zero at the bottom, then room one, room two, room three, and so on, with no top room, extending upward just as the natural numbers do.
The remarkable thing about this hotel is that it was completely full. In every single room, there was a guest in residence.
A new guest arrived at the hotel wanting to check in, but the hotel was completely full: no rooms were available. He approached the manager, who pondered the request for a moment and said, "Just give me a second." Remarkably, the manager was able to accommodate the new guest even though the hotel was completely full.
The way the manager achieved this was by sending a message to all of the current guests. When guests had originally checked in, they signed a form containing fine print stipulating that the manager might ask them to change rooms at some point during their stay, and they were obligated to comply. The manager's instruction was simple: the guest in room N should move to room N plus one.
Everyone shifted up by one room simultaneously. The guest in room zero moved to room one, the guest in room one moved to room two, the guest in room two moved to room three, and so on. Because the rooms continue without bound through the natural numbers, there is no top room, so no one was displaced. Every guest still had their own private room, and doubling up was never an option in this hotel.
After this transformation, room zero was empty, because no one had moved into it. The new guest could therefore be accommodated in room zero.
The next weekend, a large crowd of a thousand people arrived outside the hotel. All the current rooms were still occupied, yet a thousand new guests had arrived all at once and wanted to check in. The manager said, "Just a second," and was indeed able to accommodate all of them.
He did so simply by issuing a single instruction to all current occupants: the person in room N should move to room N plus 1,000. If everyone shifts up by 1,000 rooms, each guest still has their own private room, because this is a one-to-one function from the natural numbers to the natural numbers. The shift vacates all of the first thousand rooms, which then become available for the new guests.
In this way, even though the hotel was completely full when a thousand new guests arrived, the manager was able to accommodate everyone.
The next scenario to consider is the arrival of Hilbert's bus, a very large bus with infinitely many seats, numbered zero, one, two, three, four, and so on. The bus was completely full, with a passenger in every single seat, and all of those passengers wanted to check in to Hilbert's Hotel. The difficulty is that the hotel was already full. The trick of shifting every current guest up by the number of new arrivals no longer works, because we would need to shift up by infinity. Every room number in the hotel is a finite number, and it makes no sense to speak of a room numbered infinity plus two: there is no such room. The puzzle, then, is how the manager can accommodate everyone on Hilbert's bus despite the hotel being full.
Here is one elegant solution. The manager instructs every current guest in room N to move to room 2N, that is, to double their room number. The guest in room zero stays in room zero, the guest in room one moves to room two, the guest in room two moves to room four, the guest in room three moves to room six, and so on. After this shift, all current guests occupy the even-numbered rooms, leaving every odd-numbered room vacant.
The manager then assigns each bus passenger in seat S to room 2S + 1, which is always an odd number. The passenger in seat zero checks into room one, the passenger in seat one checks into room three, the passenger in seat two checks into room five, and so on. In this way, the bus passengers fill the odd-numbered rooms while the previous guests occupy the even-numbered rooms, and every individual is accommodated without any two guests sharing a room.
There is no doubling up because the bus passengers and the previous guests occupy entirely disjoint sets of rooms. Each seat number maps to its own private odd-numbered room, making this a one-to-one assignment. Both the original guests of the hotel and all the passengers from Hilbert's bus therefore receive their own private suite.
The next weekend, a certain event occurred. Hilbert's train arrived. Hilbert's train has infinitely many cars, car zero, car one, car two, car three, and so on, and furthermore, each train car is like Hilbert's bus in that it has infinitely many passengers: seat zero, seat one, seat two, seat three, and so on. Every train car has infinitely many passengers, and all of them want to check in to Hilbert's Hotel.
In a sense, each train car is like an entire copy of Hilbert's Hotel, since there are just as many passengers in each car as there are guests currently in the hotel. We have, in effect, infinitely many Hilbert's Hotels' worth of guests, and we want to fit them all into one Hilbert's Hotel. The manager says, "I can accommodate you, just give me a moment."
The manager must answer two questions: which room should the current guest in room N go to, and which room should the passenger in car C, seat S go to? One approach we have already seen is to free up infinitely many rooms by directing the current guest in room N to move to room 2N. Doubling every guest's room number clears all the odd-numbered rooms, leaving infinitely many vacancies for the train passengers.
Now the train passengers must each be assigned an odd-numbered room in a way that avoids any doubling up, since the hotel's policy is that every guest receives their own private suite. One elegant solution is to direct the passenger in car C, seat S to room 3C × 5S. This number is guaranteed to be odd, because three and five are both odd, their powers are odd, and the product of two odd numbers is odd: there is no factor of two in the prime factorization.
The deeper question is whether two different passengers could be assigned the same room. The answer is no, and the reason is precisely the uniqueness of prime factorization. Any room number of this form has a unique factorization into primes, which determines a specific number of threes and a specific number of fives. Given the room number, one can recover exactly which train car and which seat the passenger came from, by reading off the exponent of three and the exponent of five respectively. The assignment is therefore one-to-one.
In this way, even though we had infinitely many train cars each carrying infinitely many passengers, we can fit everyone into Hilbert's Hotel without doubling up any train passengers or disturbing the previous guests. It is quite remarkable.
The next weekend brought a huge crowd of runners to the hotel. They were there for the big race, the half marathon. Every runner had a number on their racing bib, and every such number was a fraction P over Q. There was runner one-half, runner three-quarters, runner five-seventy-seconds, and so on, so that all the positive fractions appeared on a racing bib. These runners chose the half marathon rather than the full marathon, naturally, because they have an affinity for fractions. The question is: can the manager accommodate all of the positive rational numbers in Hilbert's Hotel?
If you think about it, the half-marathon situation with fractions P over Q is actually very similar to the Hilbert's train case, which also involved two numbers. Here, every runner is identified by two integers, the numerator P and the denominator Q, just as in the train case every passenger was identified by a car number and a seat number. The two situations can therefore be handled in much the same way.
We first move the current guest in room N into room 2N, freeing up all the odd-numbered rooms. We then assign runner P over Q to the odd-numbered room 3P × 5Q, using the prime factorization trick. Because prime factorizations are unique, we can always recover the fraction from the room number: the numerator is simply the exponent of 3 and the denominator is the exponent of 5. This guarantees that no two different runners are ever assigned the same room.
It is worth noting that this assignment does not fill every room; some rooms remain empty. Room 13, for instance, is unoccupied: it is not even, so it holds no original guest, and since 13 is itself prime it cannot be expressed in the form 3P × 5Q, so it holds no runner either. One can ask: what is the first empty room after this transformation? Room 1 is empty, because it would require P = 0, and we stipulated that all fractions are positive, so P = 0 never occurs. Room 3 is likewise empty, since that would require Q = 0, which is also excluded. Analyzing exactly which rooms are occupied and which are not, depending on whether their room numbers can be expressed in the required form, is itself an interesting problem to consider.
Hilbert's Hotel is really about the concept of countability. A set is said to be countable if it can be placed into one-to-one correspondence with a set of natural numbers. But placing a set into one-to-one correspondence with a set of natural numbers is exactly a room-assignment function for that set: each individual from the set gets assigned a number, and that number is their room. It is therefore correct to say that a set is countable if and only if it fits into Hilbert's Hotel.
This definition includes all finite sets, since any finite number of guests can obviously be accommodated in the hotel. Finite sets thus fall under the definition of countable, and we want to include them. When people wish to exclude the finite case, they speak instead of countably infinite sets, sets that are infinite and yet still fit into Hilbert's Hotel. The train-car passengers, the bus passengers, and the runners, that is, the set of fractions, are all countably infinite sets, because every one of those sets fits into Hilbert's Hotel.
There is another illuminating way to think about countability. If a set is countable and non-empty, then its elements can be enumerated in a sequence indexed by the natural numbers. If the set is finite, the enumeration can be given with repetition; if it is infinite, the enumeration proceeds without repetition. In either case, every non-empty countable set can be listed in a sequence indexed by the natural numbers, and this is a quite robust way of thinking about the concept of countability.
Let us think about the nature of countable sets and what kind of closure properties they exhibit. If we have a countable set and add one more element to it, the result is still countable. This is precisely the basic Hilbert's Hotel situation: we had a countable set of current hotel occupants, one new guest arrived, and we were still able to accommodate everyone by shifting the existing guests up and placing the newcomer at the bottom. Therefore, adding a single element to a countable set leaves it countable.
This is easy to see directly with the enumeration idea as well. If we have a list exhibiting that a set is countable, and we have one additional element b, we can enumerate the new set simply by placing b at the front. The indices of all subsequent elements shift accordingly, but the point is that the enlarged set can still be placed on a list. Adding one element to a countably infinite set yields a set that is again countable.
There is another closure property that countable sets satisfy: if you have two countable sets, their union is still countable. This is exactly the Hilbert's bus situation, in which the first countable set represents the hotel occupants and the second represents the bus passengers, and yet the union of all those people still fits into Hilbert's Hotel. The same conclusion follows directly from the enumeration concept.
Suppose we have one countable set listed as A0, A1, A2, A3, … and a second countable set listed as B0, B1, B2, B3, …. We can combine these into a single list by interleaving the two sequences: A0, B0, A1, B1, A2, B2, A3, B3, and so on. Every element from both lists appears in this single enumeration, which shows that the union of two countable sets is itself countable.
This interleaving procedure is precisely what we did when solving the Hilbert's bus problem. The As correspond to the current hotel guests, who are placed into the even-numbered rooms, and the Bs correspond to the bus passengers, who are placed into the odd-numbered rooms in between. The solution to Hilbert's bus and the proof that the union of two countable sets is countable are, at their core, the same argument.
The union of two countable sets is countable. It follows from this, for example, that the integers, the natural numbers together with the negatives, form a countably infinite set. The integers, usually denoted by the double-struck ℤ, contain 0, 1, 2, 3, and so on, along with the negatives −1, −2, −3, and so on. At first glance, this set does not have the right form to be a list in the required sense, since a set is countable if it can be indexed by the natural numbers, whereas the integers extend infinitely in both directions.
The key observation is that this apparent obstacle is easily overcome using an interleaving argument. The natural numbers themselves form a countably infinite set, and the set of negative integers (call it ℤ⁻) is also countably infinite, since one can simply reverse the natural ordering of the negatives to enumerate them in the manner of the natural numbers. Having expressed the integers as the union of these two countably infinite sets, it follows immediately that the integers are countably infinite.
Alternatively, one can exhibit the enumeration directly: take 0, then 1, −1, 2, −2, 3, −3, and so on. This is an enumeration of all the integers, not in their usual order, but in this interleaved order, and that is perfectly acceptable. It demonstrates that the set of integers is a countable set.
What would be the analog of the Hilbert's train situation? With that aim in mind, let us consider a slightly different version of the problem. Let us think about pairs of natural numbers, that is, the set ℕ × ℕ. If we picture the natural number lattice, with coordinates zero, one, two, three, four, and so on along each axis, then every grid point in this lattice corresponds to a pair of natural numbers. For example, the point (3, 1) has x-value 3 and y-value 1, while the point (1, 3) has x-value 1 and y-value 3. The question is: how many grid points are there in the natural number lattice, or equivalently, how many pairs of natural numbers are there?
There are several ways to answer this. One approach is to apply the Hilbert's train solution directly, assigning each pair (n, m) to the number 3n × 5m. This gives a one-to-one correspondence between pairs of natural numbers and individual natural numbers, and it works precisely because of the uniqueness of prime factorization. There is, however, a more geometric approach worth describing.
Starting at the origin, we trace a winding path through the lattice that traverses successive diagonals, doubling back each time. This path visits every grid point exactly once, moving through all points whose coordinates sum to zero, then all points whose coordinates sum to one, then two, and so on. No matter which grid point you choose, the path will eventually reach it. We can therefore enumerate the grid points in the order they appear along this path, associating each grid point with its position: the zeroth point, the first, the second, and so on, corresponding to the natural numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, and so forth.
This diagonal enumeration assigns a unique natural number to every pair of natural numbers, establishing a one-to-one correspondence between ℕ × ℕ and ℕ. The conclusion is that the number of pairs of natural numbers is the same as the number of natural numbers: there are countably many pairs of natural numbers.
There is a slight improvement to the winding-path argument that Georg Cantor devised, and it is worth discussing briefly. Consider the natural number lattice once more: the grid points whose coordinates are pairs of natural numbers, with axes running zero, one, two, three, four, and so on in each direction. In Cantor's method, instead of traversing each diagonal by going both up and down, we always travel up along each diagonal. We begin at the origin, follow the first diagonal upward, skip to the next diagonal and follow it upward, and continue in this fashion indefinitely.
Labeling the points in the order we encounter them, zero, one, two, three, four, five, and so on, every lattice point eventually receives a unique natural number. This gives a one-to-one correspondence between pairs of natural numbers and natural numbers. What makes Cantor's approach especially elegant, however, is that this bijection can be expressed by an explicit polynomial formula.
Given a lattice point (x, y), we count how many points precede it along the path. Each completed diagonal contributes a fixed number of points: the first diagonal has one point, the second has two, the third has three, and so on. The point (x, y) lies on the diagonal where the coordinate sum equals x + y, so the number of points on all earlier completed diagonals is the sum one plus two plus three, all the way up to x + y. Within the current diagonal, exactly y points precede (x, y), since the diagonal is traversed upward and y measures how far along it we have traveled.
The sum one plus two plus three up to x + y is a triangular number, given by the well-known closed form (x + y)(x + y + 1) / 2. Adding the remaining y points, the total number of predecessors is exactly (x + y)(x + y + 1) / 2 + y. This is the Cantor pairing function: it maps every pair of natural numbers (x, y) to a unique natural number, and every natural number is the image of exactly one such pair.
This formula is polynomial in both x and y, expanding it yields terms in x², xy, and y². This is a marked improvement over the earlier approach using 3x · 5y, which was not a bijection because many natural numbers were left out, and which was exponential rather than polynomial in x and y. A pairing function, in general, is any function that takes pairs of objects and returns individual objects in a one-to-one and onto fashion, and the Cantor pairing function is a particularly clean and computable example of one.
Let us return to the question of the rational numbers. The claim is that the set of rational numbers is countable. We already know this in a sense, because we already placed the half-marathon runners into Hilbert's Hotel, and to be countable means precisely to fit into Hilbert's Hotel, that is, to be equinumerous with a subset of the natural numbers. But let us think about it more directly.
Every positive rational number is determined by two natural numbers: it can be written as a fraction p/q, and so it corresponds to a point in the upper quadrant of the natural number lattice. Every positive rational number lands somewhere on this lattice, and we have already shown that the collection of all lattice points is a countable set, since it is equinumerous with ℕ. Therefore the set of positive rational numbers is also countable.
We have already observed several closure properties of the countable sets. If you have a countable set, even a countably infinite one, and you add one more point to it, the result is still countable. We also observed that if you take two countable sets and form their union, putting all their elements together, the result is again countable. What I want to establish now is that if you have countably many countable sets, their union is still a countable set.
More precisely, suppose we have sets A0, A1, A2, and so on, each of which is countable. Then the union of all these sets, taking every element from every one of them and collecting them together, is itself a countable set. It may seem surprising at first that you can take infinitely many countable sets, combine them all, and still end up with only countably many elements. But this is in fact exactly right.
If you think about it a little further, you may recognize that this is precisely what we did with Hilbert's train. We had separate train cars, each carrying passengers, and we combined them all into Hilbert's Hotel. The union of all the passengers across all the train cars is a countable set, and that is exactly the content of that argument.
We can also see this in terms of the natural number lattice I have drawn several times now. Consider the grid points arranged in rows and columns, with columns indexed 0, 1, 2, 3, and so on. Each column contains infinitely many grid points. We assign A0 to the zeroth column, A1 to the first column, A2 to the second column, and so on, so that each set gets its own private column. We have already established by several different proofs that the total number of grid points in the entire lattice is countable. Therefore, the union of all the elements across all the sets An is still just a countable set.
There is a very subtle point to make about the union claim. The assertion is that if you have countably many countable sets, then their union is countable. That is true by the argument presented, but something was quietly smuggled in at a certain point: an appeal to the axiom of choice, which we will discuss in another lecture. In fact, we know that the axiom of choice is genuinely needed to prove that a countable union of countable sets is countable.
The appeal to choice may have seemed invisible, because the grid points themselves are countable by an explicit formula. The Cantor pairing function is a definable bijection between pairs of natural numbers and natural numbers, so no choices are required there. Each of the sets in question is countable, and so each can be laid off onto a column of the grid, and it may not seem as though any choice is being invoked in doing so for any single set.
But if one thinks a little more carefully about exactly that feature, there are in fact many different ways to enumerate a given countably infinite set onto a given column. What is required is that, for each set in the collection, one selects a particular enumeration, a particular way of placing it onto its designated column. That selection, made once for each n, is precisely an appeal to the axiom of countable choice. Only after all those choices have been made can one invoke Cantor's argument about the winding path through the grid, or equivalently the pairing function, to conclude that the union is countable.
This subtle point is not merely a technicality; it is provably necessary. It is consistent with the axioms of set theory in the absence of the axiom of choice that a countable union of countable sets need not be countable.
Let me consider a slightly revised version of what we proved earlier. We showed that the set of pairs of natural numbers is countable. The claim now is that if A and B are countable, then A × B is countable. The Cartesian product A × B is the set of all pairs (a, b) where a ∈ A and b ∈ B.
One way to think about this is to regard the elements of A and B as letters in an alphabet, perhaps an infinite alphabet, so that each element of A × B is a two-letter word whose first letter comes from A and whose second letter comes from B. The claim, then, is that if A and B are countable, the set of all such two-letter words is also countable.
This is easy to see: if A and B are each countable, they are each equinumerous with a set of natural numbers, and therefore A × B is equinumerous with a subset of ℕ × ℕ. The result then follows immediately from our earlier observations about the natural number lattice. With this word idea in hand, we can now do something more interesting.
Suppose A is a countable set. We think of the elements of A as letters and form words of any finite length from them. This collection is usually denoted A*, the set of all finite words over the alphabet A. When mathematicians use the word "word" here, they simply mean any finite sequence of letters from A, not a word in the linguistic sense. For instance, the string ZZYQP is not an English word, but it is a word in this sense. We also allow the empty word, the sequence of length zero containing no letters at all, and it counts as a word alongside all the one-letter words, two-letter words, three-letter words, and so forth.
The claim is that A* is countable: the set of all finite words over a countable alphabet is itself a countable set. To see this, note that the set of words of length one, which we may write A1, is countable because there are only countably many letters. The set of two-letter words, A2 = A × A, is countable because it is the product of two countable sets. The set of three-letter words, A3, is countable because every three-letter word is obtained by appending a single letter to a two-letter word, making it again a product of two countable sets. Continuing in this way, An is countable for every n, since it is obtained by taking the product of A with the countable set An−1.
We also have A0, which contains just the empty word, usually denoted ε. Every finite word belongs to exactly one of the sets A0, A1, A2, A3, …, according to its length. Therefore A* is the union of these sets. Since we have countably many countable sets, their union is countable, and so A* is countable. Even a countably infinite alphabet yields only countably many finite words.
There is a second way to present this argument, using prime factorization. Suppose the alphabet is countably infinite, with letters enumerated as a1, a2, a3, …, starting the index at one. A word w in A* is a finite sequence of such letters; if the letters appearing in w have indices k0, k1, …, kn, we can assign w the natural number 3k0 · 5k1 · 7k2 · 11k3 · … · pnkn, where pn denotes the (n+1)-th prime. Because the indices are all positive (we started the enumeration at one), every exponent in this product is a positive integer, and the uniqueness of prime factorization guarantees that different words are assigned different numbers. Given the number, we can recover the sequence of exponents and hence the sequence of letters, so the assignment is injective.
It is worth noting why starting the index at one matters. If we had allowed index zero, then a letter a0 appearing at the end of a word would contribute a factor of p0 = 1, which is invisible in the product. We could not then distinguish a word ending in a0 from the same word with that final letter removed, violating injectivity. One fix is simply to start the enumeration at one; another is to include an additional prime factor encoding the length of the word, serving as a stop marker. Either way, the map becomes injective, every word receives a distinct natural number, and we conclude once again that A* is countable.
Let me conclude with a little foreshadowing by returning to Hilbert's Hotel. As you may recall, Hilbert's Hotel has infinitely many rooms: room zero, room one, room two, room three, and so on. Now, the hotel happens to be situated on the water, and one weekend, after all the previous guests from the bus, the train, and the marathon had been accommodated, a new vessel arrives at the dock. Cantor's Cruise Ship pulls in, and it is full of passengers.
Every passenger on Cantor's Cruise Ship carries a ticket bearing a serial number, and those serial numbers are precisely the real numbers. There are, of course, the integer passengers, zero, one, two, three, and so on, who might be thought of as the elite first-class travelers. There are also passengers with fractional tickets, such as one-half and three-fourths, along with their negative counterparts. Beyond those, there are passengers bearing algebraic numbers, such as the square root of two or the cube root of five.
But the ship carries still more: the transcendental numbers, passengers whose tickets read π, e, and so forth. In short, every real number is the serial number of some passenger on Cantor's Cruise Ship, and they all wish to check in to Hilbert's Hotel. The captain approaches the manager and asks: can you accommodate us all?
That is the puzzle I would like you to think about before our next lecture, when we will return to it and discuss what Cantor himself had to say. Thank you very much.