Cantor Visits Hilberts Hotel
Pondering on infinity ...
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.
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.
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
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 ...
You might like to see the page about StackingBlocks,
or the one about BallsInBarrels.
Links to this page /
Page history /
Last change to this page
Recent changes /
Edit this page (with sufficient authority)
All pages /
Change password /