Cantor Visits Hilberts Hotel

This page has been
Tagged As Maths

Pondering on infinity ...

The Hotel

Suppose I have a big hotel. Really big. Really really big. There are lots and lots and lots of rooms. In fact, every room has a unique number on the door, and every positive whole number appears as the room number of some room. That means that for every number you can think of, the number of rooms in the hotel is bigger.

Call the rooms R1, R2, R3, etc.

The Delegates

Suppose I also have a very large number of delegates for a conference. Each delegate is assigned a room,and there are no rooms left unoccupied. Each delegate keeps his or her room key with them at all times. We'll call the delegates D1, D2, D3 in the obvious way.

Committee meeting after meeting after meeting ...

Now at this conference there are many, many committees that have to convene. In fact, every possible committee. Someone in their infinite wisdom decides that each committee should get its own room for its meetings, so someone else spends a sleepless night drafting an assignment of each committee to a different room.

The problem is, they can't. Let me explain why.

Let's think about the committee C that's made up of displaced persons. For each delegate Di, if they are on the committee that convenes in their room, leave them out of C. If they are not in the committee that convenes in their room, put them in C.

So C is the committee of those delegates displaced when their room is used for a committee meeting.

The committee of displaced persons meets in room ... ?

Where does committee C meet?

If C convenes in Rn, then let's think about Dn, and ask if they are on committee C. If Dn is on C, then it's because they are displaced when C meets. But that means they are not on the committee meeting in Rn, so they're not in C.

That's a contradiction. So Dn must not be on C. Hence Dn is not displaced when C meets, so they must be on the committee in Rn. Which is C. So they are on C.

Another contradiction. So C can't meet anywhere.

So starting with an assignment of committees to rooms, any assignment, we've shown that there must be at least one committee left out.

What?

If we now think about the collection of all possible committees, we can see that every time we try to assign them to rooms, at least one must remain unassigned. We can never pair off committees to rooms. As with cups and saucers, if whenever you pair them up you always, always have a saucer left over, there must be more saucers than cups.

So in some sense, there must be more committees than hotel rooms. And this is true, even though there are infinitely many hotel rooms.

Like in Vegas ...