The fable of the Hilbert Hotel, part 3

Catch up on the story so far….

Seething with anger and embarrassment, Old Man Kronecker could think of nothing any more past running the Hilbert Hotel to the ground.  His original plan of adding a single extra room to the hotel failed to produce a hotel with more rooms, and neither did adding what effectively amounted to adding a complete, second hotel.  Kronecker realized that even if he built a hundred copies of the hotel and appended them to his Kabins, the Hilbert Hotel will still be able to accommodate the guests: the guests from the first set of Kabins would go in Hilbert Rooms 1, 101, 201, 301,…; the guests from the second set of Kabins would take 2, 102, 202, 302,…; the guests from third set of Kabins would take 3, 103, 203, 303,…; and continuing on this way, until the guests from the hundredth set of Kabins filling in the empty rooms 100, 200, 300, 400, …

With a sigh, he tore down in Krocker Kabins, and went back to the drawing board.

The same would be true for an extra thousand hotels, or extra million hotels, or extra billion hotels, or any extra finite number of hotels.  And so Kronecker did better than that: to the single story of the Kronecker Kabins, Old Man Kroncker stacked copy after copy of the Kabins, producing (at the expense of most of his fortune) a massive, infinitely tall high-rise.  He unveiled his new and improved Kronecker Kondos, a building with an infinite number of floors (Floor 1, Floor 2, Floor 3, and so on), each floor with an infinite number of rooms (Room 1, Room 2, Room 3, et cetera).  It was the greatest wonder along Historic Root 66…

…Or so Old Man Kronecker proclaimed.  Kronecker flooded the airwaves with advertisements showcasing the vertically infinite and horizontal infinite nature of the new Kronecker Kondos, with rooms stretching to the horizon, above and beyond.  This building, the adverts proclaimed, put the Hilbert Hotel to shame: it clearly had more rooms than the old Hotel, since one could find an infinite number of copies of the hotel in it.

Now, Mr. Gamow, the proprietor of the Hilbert Hotel, once again responded to the accusations against his venerable hotel, accusing Old Man Kronecker of slander.  “Your Kondos are a hideous eyesore, sir,” snapped Mr. Gamow, “and completely unnecessary too, for the Hilbert Hotel still has room enough for all your guests.”

And so, urged in part by the television news networks (what better way to fill an uneventful 24-hour news cycle?), 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 Kondos.  In front of television cameras, Kronecker invited passersby to stay a spell at the Kondos, 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 first-floor patrons to walk across the street to their corresponding room in the Hotel: Kondo 1 to Room 1, Kondo 2 to Room 2, and so on.  They did this, and sure enough, none of the guests from any of the higher floors of the Kondos had anyplace to go.

The interstate positively surged with displaced patrons of the Kondos.

“Your Hotel is obsolete,” Old Man Kronecker spat.  “Finally!”

“Hardly,” replied Mr. Gamow.  “The problem is not the choice of hotel, but of hotelier.”

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. If you would step outside a moment.”

When all the patrons of the Kondo were back outside, Mr. Gamow pulled out his bull horn and spoke to the masses.  “Everyone, please take a look at your Kondo key please: it should have a floor number and a room number.  By adding extra zeros to the front of either number, you can make them both have the same number of digits.  To find your room in the Hilbert Hotel, just take your floor number and intersperse its digits with your room number.  For example, if you were on Floor 132 in Kondo 456, then your two numbers are

1 2 3
4 5 6

and if we “thread” the digits together we get

1 4 2 5 3 6

and so you’ll be staying in Hilbert Hotel Room 142,536.

“Similarly, if you were on Floor 39 and Kondo 5067, then your two numbers are

0 0 3 9
5 0 6 7

and if we “thread” the digits together we get

0 5 0 0 3 6 9 7

and so you’ll be staying in Hilbert Hotel Room 5,003,697.

“If anyone needs help,” he added, “I’ll be in the office to assist you.  Thank you.”

And so the Kondo guests looked at their room keys, added their extra zeros (as need be), and found their way to their rooms in the Hotel.  And soon the interstate was empty.

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

“I can see you got the guests off the street,” sputtered Kronecker,  “but you must have doubled up some of them in a room or two or…”

“You figure we would have heard a complaint from them by now,” observed Gamow.

“You’ve got audience sympathy,” Kronecker sneered.  “You’re cheating.”

“You think I’ve got two people in a room,” said Mr. Gamow, “but I assure you I do not.  Pick a room, any room, and I shall tell you who’s in it.”

“Room 378,920.”

“Let’s see.  That number has six digits: 3 7 8 9 2 0. If we take every other digit starting with the first we get 3 8 2, leaving 7 9 0. Therefore, that would be the guest from Floor 382, Kondo 790.”

“Room 4,571,000.”

“Let’s see.  That number has seven digits, so let’s add an extra zero at the first to make it 8: 0 4 5 7 1 0 0 0.  If we take every other digit, starting with the first, we get 0 5  1 0, leaving 4 7 0 0.  Therefore, it must be the guest from Floor 510, Kondo 4700.”

They tried this for several more minutes, with Old Man Kronecker giving out room numbers, and Mr. Gamow correctly identifying the unique resident in it.

“Look,” Mr. Gamow said, “this is a very simple algorithm.  Every 6-digit number in the Hotel corresponds to a unique address in the Kondo — the digits in the odd-numbered spots give the floor, and the digits in the even-numbered spots give the room.  Every five-digit number in the Hotel does the same thing, except the odd-spot digits give the room and the even-spot digits give the floor.  Every guest in your massive Kondo has a room set aside for them in my Hotel, and there’s only one resident per room.”

And with that, the Hilbert Hotel became the single greatest news story on the cable networks… well, except for Faux News, who instead ran with the story that Mr. Gamow, who had been caught on camera saying the Islamic-sounding “al-gor i’bn,” was therefore almost certainly a traitor or jihadist, and probably both.

Old Man Kronecker, on the other hand, quietly took the plans for his next building…

…and tore them up into little tiny pieces, and resigned himself to accepting that the Hilbert Hotel was there to stay.

…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 third fable of the Hotel illustrates once more the paradoxical nature of the infinite — that adding an infinite number of copies of an infinite set need not change its cardinality.

If the first fable showed that the set of counting numbers mathbb{Z}^+ has the same cardinality as the superset of natural numbers mathbb{N}, and the second fable showed that it has the same cardinality as the complete set of integers mathbb{Z}, then what does this third fable show us?

Well, if the Hotel is a metaphor for the natural numbers mathbb{N}, then the Kronecker Kondo is a metaphor for the set of ordered pairs of natural numbers mathbb{N} times mathbb{N}; hence, the set of all pairs of counting numbers has the same cardinality as the set of (singleton) counting numbers.  Gamow’s room assignment is based on the fact that any natural integer can be expressed uniquely in the form

z = displaystyle sum_{n=0}^infty z_n cdot 10^n,

where each of the numbers z_0, z_1, z_2, dots are integers between 0 and 9, and all but finitely many of them are 0.  This is the precise way of stating that z_n is the digit in the 10^n‘s digit of the integer z.  Gamow’s “interspersing” or “threading” of the room numbers is given by the function T : mathbb{N} times mathbb{N} to mathbb{N} given by

displaystyle T bigg( sum_{n=0}^infty x_n cdot 10^n, sum_{n=0}^infty y_n cdot 10^n bigg) = sum_{n=0}^infty bigg[ x_n cdot 10^{2n+1} + y_n cdot 10^{2n} bigg].

Its corresponding inverse map is

displaystyle T^{-1} bigg( sum_{n=0}^infty z_n bigg) = bigg( sum_{k=0}^infty z_{2k+1} cdot 10^k, sum_{k=0}^infty z_{2k} cdot 10^k bigg).

A neat consequence of this the fact that the set of nonnegative rational numbers mathbb{Q}' — that is, the set of numbers expressible as fractions, like 1/2 and 114/287 and 4 (which is 4/1) — has the same cardinality as the set of natural numbers. For it is clear that, on the one hand, the set of nonnegative rational numbers has at least the cardinality of the natural numbers, since the function

displaystyle f(n) = frac{n}{1}

is a one-to-one function from mathbb{N} to mathbb{Q}'.  On the other hand, the cardinality of the set of ordered pairs of natural numbers is at least as great as the cardinality of nonnegative rational numbers, since the function

displaystyle g bigg( frac{p}{q} bigg) = (p,q)

is a one-to-one function from mathbb{Q}' to mathbb{N} times mathbb{N}, provided the input fraction is expressed in reduced form.  Since we’ve shown that the latter set has the same cardinality as mathbb{N}, this is equivalent to saying that

  1. The natural numbers have at least the cardinality of the nonnegative rational numbers, and, at the same time,
  2. The nonnegative rational numbers have at least the cardinality of the natural numbers.

These two statements mean that the natural numbers and the set of nonnegative rational numbers have exactly the same cardinality by virtue of a classic result called the Cantor-Bernstein-Schroeder Theorem (here’s a pair of nice proofs at Wikipedia).

In fact, a similar line of argument shows that

  1. The integers have at least the cardinality of (all) the rational numbers, and, at the same time,
  2. The rational numbers have at least the cardinality of the integers.

Hence, we’ve just show that, even though

counting numbers subset integers subset rational numbers,

it turns out that all three of these crucially important sets of numbers have the exact same cardinality!

Is there nothing the Hilbert Hotel cannot fit?

This entry was posted in mathify. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

twenty − thirteen =