According to Wikipedia:

Although a room can be found for any finite number of nested infinities of people, the same is not always true for an infinite number of layers, even if a finite number of elements exists at each layer.

The set of real numbers, and the set of guests in this example, is uncountably infinite.

(Emphasis mine.)

I understand Cantor's diagonal arguments, and thus why we can't fit uncountably many guests into a hotel with countably many rooms. However, I don't understand how countably many layers of nesting, with finitely many elements in each layer, ends up with uncountably many elements.

How can we prove that the number of guests in this example (countably many layers of nesting, finite elements on each layer) is uncountable?

(Inspired by this question.)


Say that the people arrive in 2-seat coaches, and the coaches arrive on ferries that each carry 2 coaches, and the ferries were flown in on space ships that each carried 2 ferries, and the space ships came from planets that each sent 2 space ships, etc. ad infinitum.

Then each person can be identified by an infinite sequence of $0$'s and $1$'s indicating which seat they were in, which coach they were in, which ferry they were in, etc. For instance, if someone sat in the 0th seat of the 1st coach on the 0th ferry on the 0th's spaceship... then they can be identified with the sequence $(0,1,0,0,\dots)$.

We can further identify these infinite sequences with infinite binary expansions. So $(0,1,0,0,\dots)$ would be identified with $0.0100\dots$. Finally, we can identify such binary expansions with real numbers in $[0,1]$, which we know is uncountably infinite. Hence the number of guests arriving is uncountably infinite.

There's a bit of a technicality here, because some binary expansions may correspond to the same real number. For instance, $0.0111\dots = 0.1000\dots = \frac{1}{2}$. However, this is not a problem for the argument because this just tells us that the cardinality of the set of guests is at least as large as the set $[0,1]$.

| cite | improve this answer | |
  • 2
    $\begingroup$ Note for OP - this is not finite numbers of people arriving in each layer, but an infinite number of layers before you reach any of the people. $\endgroup$ – Mark Bennet Sep 21 '19 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.