Hilbert's hotel: infinities of different sizes

Some infinite collections can be lined up and counted, one, two, three, without end. Others cannot — however you line them up, something is left out. Infinity comes in sizes.

Why it is strange

For finite things, "same size" means "can be paired off with nothing left over." Keep that definition and apply it to infinite collections, and ordinary intuition breaks. A hotel with infinitely many rooms, all full, can still take a new guest. It can take an infinite busload. And yet there is a busload it cannot take. The definition did not change; the objects did.

The mechanism

Hilbert's hotel has rooms numbered 1, 2, 3, and so on, every one occupied. A guest arrives. Ask each guest to move up one room: room 1 to room 2, room 2 to room 3. Every guest still has a room, and room 1 is empty. The hotel was full, and now it has space.

A bus arrives carrying infinitely many passengers, numbered 1, 2, 3, … Ask each guest in room n to move to room 2n. Every even room is now taken and every odd room is free. Passenger k goes to room 2k − 1. Everyone fits. A set you can pair off with the room numbers like this is called countable.

Now a different bus. Each passenger carries an infinitely long ticket of 0s and 1s — every possible such ticket, one passenger each. Try any room assignment at all. Write the ticket of the guest in room 1, then room 2, then room 3, in a list. Now build a new ticket: its first digit is the opposite of the first digit of ticket 1, its second digit the opposite of the second digit of ticket 2, and so on down the diagonal. This new ticket differs from every ticket on the list in at least one place. So its owner has no room. That is Cantor's diagonal argument, and it shows the collection of tickets is uncountable: strictly larger than the rooms.

In one breath

Same size means pairs off with nothing left over. The whole numbers, the even numbers and the room-plus-bus crowd all pair off with each other, so they are the same infinite size. The set of infinite 0/1 strings does not: any attempted pairing leaves a diagonal string out. Infinity has at least two sizes.