How many: countable or continuum
Hilbert's hotel, numbering pairs along diagonals, and the question of which infinity a set has: countable or the continuum.
How to solve it
Two sets are equally large if there is a one-to-one correspondence between them. A set is countable if its elements can be numbered: first, second, third… There are as many integers, even numbers and rationals as natural numbers. The real numbers, though, are more — that is the continuum.
Step by step
- Hilbert's hotel: follow the moving rule. If residents moved from $n$ to $2n$ and new guests took $2k - 1$, an even room holds a former resident and an odd one a guest.
- Pairs along diagonals: the pair $(a, b)$ lies on the diagonal with sum $a + b$; before it come $1 + 2 + \ldots + (a + b - 2)$ pairs, and on its own diagonal it is the $a$-th.
- Cardinality: if the elements can be written in an infinite list (integers, multiples, rationals, pairs, finite words) it is countable. An interval, a line, infinite sequences of digits — the continuum.
Common mistakes
- Thinking there are “half as many” even numbers as natural ones. There are as many: $n \leftrightarrow 2n$.
- Getting the direction of a move in the hotel wrong: it matters which room goes to which.
- Being off by one in the diagonal number: pairs with sum $2$ form the first diagonal.
- Thinking there are more rationals than natural numbers because there is always another one in between. They can be numbered — countable.