The fable of the Hilbert Hotel, part 2

Catch up on the story so far…

Old Man Kronecker was more determined than ever to run the Hilbert Hotel out of business, but his previous plan of adding one more room to the hotel and thereby producing a bigger hotel had failed.  Kronecker also reasoned that even if her were to add a hundred new rooms to the Kronecker Kabins, the Hilbert Hotel would still be able to accommodate the guests: the guests from Kronecker Kabins 1, 2, 3, … could simply be sent to Hilbert Rooms 101, 102, 103, … respectively, leaving the first 100 rooms unoccupied for the “extra” guests, who apparently weren’t that extra at all.

The same would be true for an extra thousand rooms, or extra million rooms, or extra billion rooms, or any extra finite number of rooms.  And so Kronecker did better than that: to Room 0, Old Man Kronecker built (at great cost, admittedly) another copy of the Hilbert Hotel, with rooms labeled -1, -2, -3, …. and so on without end.  He unveiled his new and improved Kronecker Kabins, stretching up and down the expanse of Historic Root 66.

Once again, Kronecker took to the airwaves, advertising the doubly infinite nature of the new Kronecker Kabins, with rooms stretching from horizon to horizon.  This building, the adverts proclaimed, put the Hilbert Hotel to shame, now having double the number of rooms of old Hotel. And once again, Mr. Gamow (the proprietor of the Hilbert Hotel) cried false advertising, arguing that there was nothing new to the Kabins, and that the Hotel still had room enough for all their guests.

And so, once again, the two hoteliers struck a deal: a challenge to see whether the Hilbert Hotel had vacancies enough to house all of the guests of the Kronecker Kabins.  In front of television cameras, Kronecker invited passersby to stay a spell at the Kabins, and soon the rooms were all occupied.  “Now let me show you,” said Old Man Kronecker, “that the Hilbert Hotel is too small!”  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, none of the guests from Kabins 0, -1, -2, -3, and on had any place to go.

As the interstate swelled with an infinity of displaced patrons, Kronecker cackled in triumph.

“Not so fast,” replied Mr. Gamow.

“Look!” exclaimed Kronecker.  “All your rooms are occupied, and you’ve still got an infinity of guests waiting for their rooms.  Your Hotel is too small!”

“The problem,” Mr. Gamow responded quietly, “is not with the property, but with the management.”

He then turned to the throng of displaced guests.  “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.  “Mr. Kronecker has placed you in the wrong room.  Would you please look at your Kronecker Kabin number, double it, and then proceed to that room in the Hilbert Hotel?  Thank you.”  And so the guest from Kabin 1 went to Room 2; the guest from Kabin 2 went to Room 4; the guest from Kabin 3 went to Room 6; and so on.

Once everyone had resettled, the Hotel now had Rooms 1, 3, 5, 7 — in fact, all the odd-numbered rooms — empty.  Mr. Gamow turned to the guests waiting in his office.  “Thank you for your patience.  Now, if you please, would you fine people please look at your Kronecker Kabin number — just ignore the negative sign if you have one — and double it and odd one.  You may check into that room of the Hilbert Hotel.  And so the guest from Kabin 0 went to Room 1, the guest from Kabin -1 went to Room 3, the guest from Kabin -2 went to Room 5; and so on.

Once everyone had settled, the office was empty, and each patrons of the Kabins was nestled in his or her own room int he Hotel.

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

“But that’s impossible!” sputtered Kronecker.  “I had two whole Hilbert Hotels… plus an extra room…”

“Evidently not,” said Gamow.

“No,” argued Kronecker, “you must have missed someone.  Where’s my guest from Kabin 12?” demanded Kronecker.

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

“What about the guest in Kabin -12?”

“He’s in Room 25,” said Gamow.  “Listen, it’s very simple.  Your guest from Kabin N is in my Room 2N if N was positive, and in Room 2|N| + 1 otherwise, so every one of your guests is accounted for.  Moreover, my room R houses your guest from Kabin R/2 if R is even, and your guest from Kabin -(R – 1)/2 if R is odd, 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 triple-fold.

Old Man Kronecker raged in bitter disappointment again.  He realized that even if he added two or three or a hundred extra copies of the hotel to his 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 second fable of the Hotel illustrates once again 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.  And while the previous fabled showed that “adding a finite number” of objects to an infinite set did not actually increase its size, this shows the more surprising result that “adding and infinite number” of objects to an infinite set might be just as ineffective.

Essentially, the Hilbert Hotel is a metaphor for the set of counting numbers , while the new and improved Kronecker Kabins is a stand-in for the set of integers .  Although it seems completely reasonable that the integers contain at least twice as many objects as the counting numbers — there’s essential two 1’s and two 2’s and two 3’s… plus an extra 0 — it turns out that these two sets have the exact same cardinality, as shown by Gamow’s room assignment, which in function form is defined by

.

That this is a bijection can be easily checked by noting that its inverse is given by

.

(A related example is the fact that the set of even counting numbers has the same cardinality as the set of all counting numbers ; the doubling funtion is an example of a bijection from to .)

A generalization of this idea is that the set formed by collecting p distinct copies of the counting numbers still has the same cardinality as the counting numbers. The idea would be to pair all of the elements of the elements of the first copy with those counting numbers who have a remainder of 1 when divided by p — so $1, p+1, 2p+1, 3p+1$ and so on; then pair the elements of the second copy of counting numbers with those counting numbers who have a remainder of 2 when divided by p — so $2, p+2, 2p+2, 3p+2$ and so on; and continue in this way.

To make this precise, let ; hence, every element of takes the form $n_k = latex (n,k)$, where n is a counting number and k is an index between 1 and p.  Said differently, we can think of as the number n from the k-th copy of .  (In some sense, Kronecker’s new and improved Kabins are a model of .)  We can then define a function by

.

The corresponding inverse function is a little clunky to write out: to compute , first compute the division problem to work out the quotient q and remainder r.  Then

(We’ll leave it as a exercise to you to see how these formulas could be simplified if we used the set of natural numbers rather than the counting numbers as our default “counting” set.)