Maths●●●●●Difficulty 3 of 5

Are some infinities bigger than others?

A full hotel with infinitely many rooms can always squeeze in more guests, yet some infinite crowds will never fit.

▶ Start the story

Yes. In the 19th century, Georg Cantor proved that the real numbers, all the numbers with endless decimals, are more numerous than the counting numbers 1, 2, 3... even though both collections are infinite. In fact, his method implies there's an infinity of different infinities.

The way to compare infinite sets is to pair them up one-to-one. Some infinities that look different turn out to be the same size. Imagine a hotel with infinitely many rooms, all full. A new guest arrives? Ask every guest to move from room n to room n+1: there's no last room, so everyone fits, and room 1 is free. Infinitely many new guests? Move everyone from room n to room 2n, and all the odd rooms open up.

Checking in at Hilbert's Grand Hotel
  1. Step 1: Infinitely many rooms, all full

    Rooms 1, 2, 3... forever.

  2. Step 2: One new guest

    Everyone moves from room n to n+1; room 1 is free.

  3. Step 3: Infinitely many new guests

    Everyone moves from room n to 2n; all odd rooms are free.

  4. Step 4: All infinite 0-1 strings

    No room plan works: the diagonal always leaves one out.

But some crowds never fit. Suppose you claim to have listed every infinite string of 0s and 1s. Cantor builds a new string by flipping the first digit of the first string, the second digit of the second, and so on down the diagonal. The new string differs from every string on your list somewhere, so it isn't on the list. No list can ever be complete: that infinity is bigger.

A grid of rows of 0s and 1s with the diagonal digits highlighted; flipping them produces a new row at the bottom.
Flip the highlighted diagonal digits and you get a sequence that differs from every row on the list.Photo: Cronholm144 · CC BY-SA 3.0

The idea was so shocking that a fellow mathematician, Leopold Kronecker, called Cantor a "corrupter of youth".

Quiz me

0/3

  1. 1.How does Hilbert's full infinite hotel make room for one more guest?
  2. 2.Why can't the new string in Cantor's diagonal argument be on the list?
  3. 3.Why does Cantor's diagonal argument matter beyond infinity?

Recap

Change the nth digit of the nth item on any list, and you've built something the list missed.

Surprising fact · A full hotel with infinitely many rooms can still host infinitely many new guests.

Sources (3)

No source, no claim. Every fact in this lesson (14 claims) cites at least one of these.

  1. [1]Cantor's diagonal argument · Wikipedia
  2. [2]Hilbert's paradox of the Grand Hotel · Wikipedia
  3. [3]Georg Cantor · Wikipedia
More lessons in ➗ Maths (3) See all maths lessons →

One more light on your map.

Get one lesson like this every day, about the things you love. Free, in two or five minutes.

Get the share card for this lesson ↗