book a room in a FINITE hotel online!
One of the gee-whiz examples from introductory set theory is the puzzle of the infinite hotel. The infinite hotel was popularized by the Göttingen mathematician David Hilbert (1862-1943) and is often called the Hilbert Hotel. The goal of the example is to prove that n = (n+1) when n = ∞. My opinion is that the example does not accomplish this goal. As this article has a different interpretation of the hotel, I chose to call the owner of the hotel Al.
Al has a very busy infinite hotel on a port that serves an infinite number ships a day.
On a crowded Friday night, the bellhop noticed that all the rooms in the infinite hotel were full! It was a busy night and another ship pulled in. The captain from the ship demanded a room.
The bellhop, being a common man, was confounded and said: "I am sorry, the infinite hotel is full."
Al, the hotel owner, had a larger transfinite consciousness. He was waiting for this the problem to arise, and burst into the room saying: "No problem, sir, this is an infinite hotel and we can easily handle this minor set back."
Al instructed the bellhop to go to room one and have that guest switch to room two. The bell hop would then go to room two and tell the room two guest to switch to room three. He repeats this process an infinite number of times. Voila, the process would create an empty room for the new guest, and happiness rained on earth.
Al's Infinite Hotel is often given as proof that adding one unit does not change the "size" of an infinite set. Surely, if there is an example involving an intellectual cripple, like a bellhop, then the proof must be true.
If the teacher moves quickly to the next example, the infinite hotel is a convincing argument; However, if the teacher drops an eraser and the students accidentally start to think, the example can take a turn for the worst. As we all know, students who think often turn into intuitionalists.
Hilbert's infinite hotel example seems like a convincing proof that all infinite sets are the same size. It is convincing until one gets into the nitty gritty of defining the procedure for moving people from one room to the next.
To make the problem work, the guests must either step into the hall, or there is a moment in each transaction where there are two people in the same room.
Lets add the simple rule to the hotel that at no time can two guests occupy the same room at the same time. This rule creates a problem in the very first room since the old guest has to be out of the room before the new guest can enter. This rule applies to every single room in the hotel.
Look at the sequence of events: Event n must occur before n-1, which occurs before n-2, which occurs before n-3...which occurs before event 2 which must occur before event 1.
This is a reverse causality. For Al's Infinite Hotel to work as advertised, an event must take place at infinity before the guest shift can occur! This event at infinity is problematic as the event involves a guest moving into an empty room. This contradicts the assumption that all the rooms are full.
We now have multiple problems: Transfinite theorists cannot simply claim that the guests stand in the hallway between room transfers. The goal is to show that you can fit ∞ + 1 guests in ∞ rooms. If you designed an algorithm where the guest in room one steps into the hallway to make room for the new guest, and guest two steps into the hallway for guest one, etc., you will find that you didn't put n+1 guests in n rooms. At any given instance, what you have is n guests in n rooms and one unfortunate sot left in the hall.
Now, I've stayed in hotels where there is a doorway between rooms. These doors to adjacent rooms are convenient for groups because they allow people to move between rooms without going through the hall. Expecting large groups, Al designed the infinite hotel so that in each room there is a door to the room to the immediate right.
Al respects the privacy of his guests. So he programmed these doors so that a guest cannot enter another room if it is occupied. The following model shows the rooms where square brackets mark doors, and an x marks a guest.
[x] [x] [x] [x] [x] [x] [x] [x] [x] ...
This is a simple rules based system. All the rooms operate by the same rule. You cannot open the door to the right if the room is occupied. By definition, all rooms are occupied, so no-one can open the door to the room to the right.
Hilbert's model has guests moving between the rooms simultaneously. Our rule that a guest cannot open the door to the room at the right if a guest is in the room prevents simultaneous movement. By definition, there is always someone in the adjoining room. No one can open a door to start a transfer.
Simultaneous moves cannot work.
Having people stand in the doorway between transfers doesn't work either. The doorway then serves as a temporary holding tank like the the hallway.
The infinite hotel model sounds promising, but it seems to fall apart as we try to define the process of moving between rooms.
Lets step into the hallway for a moment...
The final model for explaining the hotel is to have all the guests step into the hallway, then back into a room.
The goal of the infinite hotel is to prove that n = n+1 where n is infinity.
Looking closer at this model, we find the following numbers:
n people step out of n rooms into the hallway. The new guest steps into the hallway. That means that there is now n+1 people in the hallway. These n+1 people step into n+1 rooms.
We see n people stepping out of n rooms, and n + 1 people stepping into n+1 rooms. There is no way to construct the model so that n+1 people step directly into n rooms. The set of rooms that people exit is different from the set people enter.
Looking at the difficulties of moving guests between rooms, transfinite theorists fall back and say that it doesn't matter if the proof can be constructed. The proof just is. All that matters is that you can map the original configuration of guests to a new configuration of guests. Yet, this statement falls apart because mapping is itself a construction. The item below shows a mapping form the original sets of rooms to a new room. The symbol L indicates the lobby, N is the new guest, the symbol gx is a guest and rx is a room:
Rooms: L r1 r2 r3 r4 r5...rn rn+1... Original: N g1 g2 g3 g4 g5...gn gn+1... Mapping: \ \ \ \ \ \ \ \ New: N g1 g2 g3 g4... gn+1 gn+2...
The mapping is always implying the existence of one more room than the original number of guests. The mapping doesn't put n+1 guests in n rooms, it puts n+1 guests in n+1 rooms.
This illusion of the infinite hotel occurs as the result of the unbound nature of infinity. It is not proof that n=n+1. Far from proving that sets are the same size, the difficulties we have in constructing the model indicate that the sets are different sizes, or at least shows that we cannot simply translate our finite notion of size to the infinite.
Many of the problems we see with infinite sets occur in arbitrarily large sets. An arbitrarily large set is a finite set that can automatically expand as needed. This brings us to Garb's Arbitrarium. The Arbitrarium is a arbitrarily large hotel. The hotel is extremely large, but still finite. The most amazing thing about the hotel is that it expands as needed.
One day the Arbitrarium is full. There are n rooms in the hotel and n guests in the n rooms. A new guest shows up at the hotel and asks for a room. Garb confidently presses the majic button behind the desk. The guests in the hotel hear the familiar sound of creaking timbers and shuttering rafters as the Arbitrarium resizes. There is now a new room in the hotel. Garb can have all of the guests in the hotel shift so that the new guest gets to sleep in room one.
Garb's Arbitrarium is unbound like Al's Infinite Hotel, but it is very clear that n != n+1. New rooms appear in Garb's establishment as needed.
The big difference between the Arbitrarium and the Infinite Hotel, of course, is that the Arbitrarium has a defined last member. The Arbitrarium is unbound. There is no upper limit to its size. As such, the Arbitrarium is potentially infinite. The Arbitrarium shows clearly that, for potentially infinite sets, the set of rooms containing n guests is different from that containing n+1 guests.
I bring up the Arbitrarium as it shows the expanding of capacity as a distinct operation.
Al's Infinite Hotel seems to make sense because the Infinite Hotel is by definition unbounded. The infinite series does not have an end. Circles have the same property. You can go around and around in circles forever. Circles do not have ends, so we can examine unbounded behaviors simply by examining circles.
As it happens, Carl's Circular Courtyard demonstrates the same unbounded behavior as Al's Infinite Hotel. Carl is from a middle class family and could not raise the seed capital to build an infinite hotel. He built a modest inn with 240 rooms in a circle around a courtyard.
Carl was cheap, he never bothered spending the money for door signs. The room are indistinguishable and none have numbers.
The Courtyard is full, but another guest arrives at the doorstep. Carl, who loves the smell of money, instructs the bellhop to start at a random room and to move the guest in a circle around the courtyard.
Carl pays his bellhop less than Al; so Carl's bellhop is less efficient. It takes Carl's bellhop 10 minutes to move a guest from room A to room B.
Now, notice that our rooms are in a circle around a courtyard. The bellhop can't tell the difference between the rooms, but since he always moves to the left he can perform the job without getting lost.
We know there are 240 rooms and it takes 10 minutes per transfer. The bellhop will complete his loop in a single day. That is good. It means that the guests won't be disturbed more than once a day.
Carl's Circular Courtyard provides a finite model for discussing unbounded sets. It appears that Carl is able to accommodate 241 guests in his 240 room hotel; however the people watching the bellhop would see that there was always one room in the state of disruption.
Carl charges the 241 guests for the night. On receiving complaints, the Better Business Bureau decides to investigate. They see Carl charging for 241 rooms and how he claims everyone had a room for the night. The clerk from the BBB gets confused with Carl's convoluted paperwork, then says that Carl can only charge a guest if the guest's head is lying on a pillow in the hotel at precisely midnight.
Alas, Carl's design for his Circular Courtyard runs aground, because his model was dependent on the fact that one guest would be standing in the hallway at all times while the bellhop moves customers from room to room.
Fortunately, Al sees Carl's problems. Having a superior transfinite mind (and a transfinite credit line to boot) Al buys the Circular Courtyard. In a major remodeling effort that cost an infinite number of dollars but was completed in less than an instant, Al adds an infinite number of stories onto the Circular Courtyard. He designs the floors to work in a spiral so that the door from 240th room leads to the 241st room, which is above the 1st room. The 242 room is above the 2nd room. The 481st room is above the 241st room, and so on.
Having borrowed an infinite number of dollars, Al realizes he needs an infinite number of guests. He hires an internet marketer to send out an infinite number of unsolicited emails. Although only one in fifty thousand people respond to the spam campaign, it is a success and the hotel fills to capacity.
The thugs at the BBB hear the hotel is full. Looking to create trouble, the head of the BBB goes to the Courtyard and asks for a room. Al says, "But of course?"
Unfortunately, Al has not had time to hire a new bellhop. He sends a lesser bellhop with a mind still trapped by the confines of Aristotelian logic to move the guests from room to room. The bellhop has a hot date and is motivated to complete the job, but now matter how quickly he moves, there is always one guest standing in the hall. Not only that, they are standing in the hall next to a room that is above one of the 240 original rooms. Taking mod 240 of the spiral hotel, we see that it is much like the circular hotel.
The head of the BBB is not impressed. However, Al learns that if he joins the local BBB, they really won't push the issue to terribly hard.
Al's Infinite Hotel is often given as proof that adding one unit to an infinite set does not change its size. In our computer age where students are familiar with writing programs and database applications will realize that example falls flat.
Al's Infinite Hotel runs into the same challenge that database programmers run into when they try to maintain ordered lists. Lets say I have a database with an ordered list and I want to switch the position of item 1 and item 2. This transfer would involve two steps:
UPDATE Item SET key = 1 WHERE key=2;
UPDATE Item SET key=2 WHERE key=1;
This database challenge is full of peril. Executing the first command violates the primary key index on the Item table.
To perform such a feat, the database programmer usually introduces an interim step where they change the key to a temporary value, just as the infinite hotel is dependent on having the guests step into the hallway for a moment.
Just to recap, Hilbert's Infinite Hotel model is dependent either on having a hallway or on having two users in the same room.
If we allowed two people in the same room, the transition between rooms would look as follows: (the rooms are numbered r1, r2 ... The guests are numbered g1, g2, .... I will add a new guest called g0 into r1).
g0 enters r1 => two people (g0,g1) in r1 g1 enters r2 => two people (g1,g2) in r2 g2 enters r3 => two people (g2,g3) in r3 g3 enters r4 => two people (g3,g4) in r4 ...
Think about it. This sequence continues forever. It does not add a room. The double up model creates a situation where there are always two people in one of the rooms.
On to the hallway model. Let's design our sequence so the guest stand in the hallway between transfers:
g1 steps into hall, g0 steps into r1 => g1 in hallway g2 steps into hall, g1 steps into r2 => g2 in hallway g3 steps into hall, g2 steps into r3 => g3 in hallway ...
This second method doesn't create a room, it creates a situation where there always one person in the hallway.
Having all the guests step out of their rooms into the hallway, then back into a room does not transfer n+1 people into n rooms. It creates a situation where n+1 people step into n+1 rooms. The room the set the exit is different from the set they reenter.
The fans of Hilbert often recommend tossing Einstein's Theory of Relativity to the wind saying that the guests all step between the rooms simultaneously. In a rule based system, the simultaneous transfer fails as well. Are rules are that a guest can't shift to the new room if it is occupied. All the rooms are occupied. Hence, in a rules based system, the guests cannot shift. Having the guests stay in the doorway for an instant between transfers is the same as having them stand in the hallway.
Regardless of how you try to construct a model of the the infinite hotel, the result appears elusive, and never comes close to proving that statement that n = n + 1 where n is infinity.
The Infinite Hotel is gee-whiz mathematics at its worse. No-one has ever created a complete infinite set. The size of an incomplete set is unknown. Since it would be impossible to find a way to move the guests in an infinite hotel without either doubling up or making a poor fool stand in the hall, I think it is better to say that adding one to an unknown creates an unknown that is one larger than the previous unknown value rather than trying to build a fantasy world where n = n+1.
By the way, did I mention that Al's Infinite Hotel fits on the head of a pin, and that all the guests are angels, and that the reason the hotel is so crowded is because Al hires a great country western band, and that there is line dancing on Friday nights? Yep, the model provides as much insight into mathematics as contemplating the number of angels line dancing on the head of a pin.
Rate This Article
Descriptive Mathematics - - Diagonal Method - - Sponsors - - Index
Infinite hotels are overrated
Book a room at a finite hotel