display | more...

An imaginary hotel, used as a metaphor for the natural numbers in order to demonstrate some features of infinite sets.

The hotel has an infinite number of rooms. Let's say for simplicity they're numbered Room #0, Room #1, Room #2, and so on, all the way up. It's important to remember that there is no last room. So we start learning about how you can do things with infinite sets you can't do with finite sets. The standard first example:

The hotel is full one day. There are no rooms that are free. Every single room is occupied, and someone comes in asking for a room. Can this be done? Sure: announce over the PA system that everyone has to pack up and move one more room down the line. So the occupant of Room #n goes to Room #n+1, all the way down. They can do all this in parallel (neglecting the time it would take for the information to travel all the way down), so in a finite (and possibly short) time, Room #0 is free, and the newcomer can move into it. Why couldn't he just have gone to the free room in the first place? Because there wasn't any! Where did it come from then? Well, there was always another room for each person to move into... It's hard to see because you can't do this with finite sets. Obviously we can handle any finite number of new guests this way: everyone just shift down n rooms.

OK, next example: the equally infinite hotel across the street closes down, and all infinitely many guests (it was full) troop into the lobby demanding rooms, and we're full up also. Can we swing this? Sure. Another announcement: everyone move to the room with the number twice the one you're in now. So Room #0 stays put, Room #1 moves to Room #2, Room #2 goes to Room #4, and Room #n goes to Room #2n. This moves all the current guests into the even-numbered rooms, leaving an infinite number of odd-numbered rooms for the new guests. No problem.

How about this? There are now an infinite number of these hotels, all full... and all but one close down. All the guests converge on the remaining one. Can we do this? Yep. I'm going to need a picture:

```  Hotels     Rooms -->
|
V

0    0-> 1   2-> 3  ...
|   |   |
1    0 <-1   2   3  ...
|       |   |
2    0-> 1-> 2   3  ...
|
3    0 <-1 <-2 <-3  ...
....................
```

Start at Hotel #0, Room #0, and follow the path shown. It keeps going, snaking around. Number the rooms as you go. The first one you get to goes into Room #0 of the remaining hotel, the next one in Room #1, then Room #2, and so on. You'll get to all the guests, and you'll never run out of rooms. We can do this.

Can we handle anything? No. Georg Cantor's diagonal argument proves that there are infinities too big to be counted (which is essentially what we're doing: associating each guest with a (room) number. That's counting). There's a version of it that works with the hotel, but it's less accessible than other versions. You've been warned; maybe you should stop reading here.

The guests decide that the manager of the hotel is far too smug and needs to be taken down a peg or two, by giving him a situation where he couldn't house everyone. And the math professor in Room #42 has an idea:

He organizes meetings among all the guests. All possible sets of guests of all sizes hold meetings. So there's a meeting of zero attendees (the nullset). Each guest holds a meeting of one person (himself). All pairs of guests meet. All triples. All sets of four. All sets of five. And so on, all the way up. Yes, there are infinitely many meetings; that's the point (in fact, the number of meetings is "more infinite" than the number of rooms, as we'll see). At each meeting, someone gets invited to stay at the hotel next New Year's. The invitee may or may not be a current guest, and may or may not be present at the meeting, but they all have to be distinct. The professor will record the invitee for the meeting of zero people, and all the invitees from the other meetings. If everyone invited shows up, the manager is hosed.

Why? Well, consider: each meeting is a meeting of some set of rooms (for simplicity we'll say the rooms are meeting, not the occupants), and elects an invitee. We can consider the invitee to be a room as well: assume the manager can house everyone at New Year's. Then the person invited at the meeting will have a room. So each meeting has some rooms in attendance and invites a room as well.

Some rooms may be present at the meeting which invites them (i.e., that invites the person who will eventually be housed in that room). But some will not be. We know that for certain: no rooms were present at the nullset meeting, so the room that was invited there was not present at the meeting that invited it. Now consider all the rooms that weren't present at the meeting that invited them. That's a set of rooms, and all sets of rooms had a meeting, so somewhere along the line those rooms had a meeting and invited a room. Was that room present at that meeting? Either way you get a contradiction. If the room was present there, then this isn't really the meeting of just those rooms which were not present when they were invited, and we said we're considering just that meeting. If the room wasn't present there, then it wasn't present when it was invited... and thus should have been at the meeting of rooms that weren't present when they were invited! So the only thing to conclude is that the putative housing arrangements for next New Year's can't actually happen. No matter which one you use, the same argument applies to show it didn't work.

There are better ways of showing that paradox, but the Hotel metaphor is quite accessible for some other things, like the earlier parts of this writeup. I warned you the diagonalization part was hard to follow.

Log in or register to write something here or to contact authors.