# The fable of the Hilbert Hotel, part 1

The counter-intuitive aspects of infinity have popped up in both in my math classes this semester, such as the construction of plane regions with an infinite length and height but a finite area, or solids with an infinite surface area but a finite volume. As a consequence of these mind-bending ideas, I’ve more or less had the following conversation several times this semester with some of my more inquisitive students. I figured since I seem to have this talk every semester, I’d put it down here at komplexify for future reference.

Down on one particularly long and straight stretch of Historic Root 66 lies the Hilbert Hotel.  From the outside, it doesn’t look like much: just a long, single story dwelling with rooms labelled 1, 2, 3, and so on, all connected to a central PA system, adorned with a large billboard that reads The Hilbert Hotel.  It was designed in the 1880s by the famed (and chronically depressed) architect G. Cantor and built in the 1940s by D. Hilbert, where it earned its fame as a roadside attraction for its habit of always having a room available for travelers: not just 24 hours a day or 7 days a week or even 52 week a year, but even, it was said, when all of its rooms were already occupied.  In fact, the proprietor of the Hotel, a Mr. Gamow, was fond of saying that since they’d never run out of rooms before, he’s simply changed the sign to permanently read “Yes! Vacancies.”

Now across the highway lived Old Man Kronecker, a grumpy old coot who despised the Hilbert Hotel.  Regressive, finitist, and virulently anti-(axiom-of)-choice, Kronecker made his fortune sanding off the edges of sharp corners and then designing elliptical furnishings to fit them.  He despised the gaudy illuminated sign and the comings and goings of people at all hours of the days, calling Cantor an “architectural charlatan” and claiming the hotel  was corrupting the youth.  Kronecker wanted to be rid of the hotel, and he decided the most satisfying way to do it would be to run Mr. Gamow out of business, and so he set his sights on that…

To that end he took a chunk of his fortune and built a mirror-image copy of the Hotel on his side of the road — a single line of rooms labelled 1, 2, 3, and so one without end — but with a single change: he affixed to the side of Room 1 an extra room, labelled 0.

And so Kronecker opened the new Kronecker Kabins with a massive advertising campaign noting that with its new Zeroth Room, it now had an even more rooms than the Hilbert Hotel.  Well, Gamow didn’t take that sitting down, accusing Kronecker of doubly false advertising: first, by insinuating that the Hotel had ever run out of room in the past (quoting the words of Hilbert, who said “Let no one be expelled from this hotel that Cantor has created”), and second, by claiming that the Kronecker Kabins had more rooms than the Hilbert Hotel.

Eager to avoid a lawsuit, Kronecker struck a deal with Gamow: a challenge to show that the Hotel had fewer rooms than the Kabins.  In front of television cameras, Kronecker invited passersby to stay a spell at the Kabins, and soon the rooms — including Room 0 — were all occupied.  “Now let me show you,” said Old Man Kronecker, “that the Hilbert Hotel has one room too few!”  And with that, he asked each of his patrons to walk across the street to their corresponding room in the Hotel: Kabin 1 to Room 1, Kabin 2 to Room 2, and so on.  They did this, and sure enough, the guest from Kabin 0 had no place to go.

“Ha ha!,” exclaimed Kronecker!

“Not so fast,” replied Mr. Gamow.

Gamow turned to the displaced guest.  “Our motto is Yes! Vacancies.  Please give me a moment.”  With that, he turned on the PA system, allowing him to speak to all the rooms in the Hotel at once.  “Excuse me everyone,” he began.  “Could I trouble each one of you to move one room over?”  And so the guest from Kabin 1 went to Room 2; the guest from Kabin 2 went to Room 3; the guest from Kabin 3 went to Room 4; and so on.  Once everyone had resettled, Gamow showed the extra guest to the now unoccupied Room 1.

Voila,” said Gamow.  “There is room enough in the Hilbert Hotel for all your guests.”

“But that’s impossible!” sputtered Kronecker.  “I had an extra guest in Kabin 0.”

“Whom I placed in my Room 1,” said Gamow.

“But what about my guest in Kabin 1?” demanded Kronecker.

“He’s in my Room 2,” said Gamow.

“But… what about guest in Kabin 2?”

“He’s in Room 3,” said Gamow.  Sensing this conversation might go on a while, he added “Listen, it’s very simple.  Your guest from Kabin N is in my Room N+1, so every one of your guests is accounted for.  Moreover, my room R houses your guest from Kabin R-1, so every one of my rooms is accounted for.  Therefore, your Kabins and my Hotel have exactly the same number of rooms.”

And with that, the popularity of the Hilbert Hotel grew overnight.

Old Man Kronecker spat in disappointment.  He realized that even if he added two or three or a hundred new rooms to the Kabins, the Hilbert Hotel would still be able to accommodate the extra guests.

And that’s when Kronecker hatched a new plan…

…to be continued

Afterword.

The Hilbert Hotel was originally conceived by George Gamow in his 1947 book One Two Three… Infinity.  I’ve taken his iconic metaphor and transformed it from a gala-metropolitan high-rise it into a 1950s-era roadside motel, but have otherwise kept the spirit of place intact, which is to illustrate many of the counter-intuitive properties of infinite sets.

This first fable of the Hotel illustrates that when it comes to infinite sets, the whole need not be greater than the part; that is, that an infinite set many have as many elements as a proper subset of itself.

How does one tell if two collections have the same number of objects?  Well, one way is to count each collection and compare, but this is fraught with peril even without the additional headache of one of them being having infinitely many objects: haven’t you even “lost count” of something due to an unexpected interruption, and had to start all over again?

A better way might be to pair the objects up: take one object from the first collection — call it Set A — and one from the second collection — call it Set B — and put them together on the side.  Repeat this over and over again, pulling out a single object from Set A and a single object from Set B and setting them aside together.  If it happens that Set A runs out of objects before Set B does — that is, there is an object in Set B that cannot be paired with one in Set A — then we can conclude that Set B has more objects in it than Set A, even though we cannot say exactly how many there are.  Similarly, if it happens that Set B runs out before set A, then Set A must have more objects that Set B.  And if they should run out at the same time — so that every element of Set A is paired with one, and only one, element from Set B — then we can conclude Set A and Set B have the same number of elements, even if we cannot say precisely what that number is.

More mathematically precise, we say that two sets $A$ and $B$ have the same number of elements (or the same cardinality) if there exists a 1-to-1 correspondence between them, that is, a bijective (i.e. both one-to-one and onto) function $p : A to B$.  The function $p$ makes precise the notion of pairing off from above.  If a set $S$ has the same cardinality as the set ${ 1, 2, 3, dots, n-1, n }$ for some positive integer $n$, then we say it has n elements, and the function $p : { 1, 2, dots, n } to S$ is effectively “counting off” the elements.  We say a set is finite if is has n elements for some non-negative natural number n, and it is true that in the realm of the finite, the cardinality of a set $S$ is always greater than the cardinality of any of its proper subsets.

A set that is not finite is called infinite, and the set $mathbb{Z}^+ = { 1, 2, 3, 4, dots }$ of positive integers — the set of counting numbers — is the most familiar example.  This Hilbert Hotel is a metaphor for precisely this set.  The set of natural numbers $mathbb{N} = { 0, 1, 2, 3, dots }$ adds 0 to the counting numbers; this is the idea behind the Kronecker Kabins.

It is clear that $mathbb{Z}^+$ is a proper subset of $mathbb{N}$ — the former set lacks the number zero — and so in some sense it is a “smaller” set.  We might guess that, based on our familiarity with finite sets, it must have a smaller cardinality.  However, the function $p : mathbb{N} to mathbb{Z}^+$ defined by $p(n) = n+1$ is a bijection (its inverse is $p^{-1}(r) = r - 1$), and so we must conclude, counter-intuitive as it may be, that the two sets have the same cardinality.

That is, for infinite sets, sometimes the whole is just a big as the part!

This entry was posted in mathify. Bookmark the permalink.