Some infinities are bigger than others

There are more numbers between 0 and 1 than there are whole numbers altogether — even though the whole numbers go on forever. Some infinities are genuinely bigger than others.

That sentence sounds like it can't possibly mean anything. Infinity is infinity, surely — the biggest thing there is? Yet in 1891 Georg Cantor proved, with an argument short enough to fit on a postcard, that infinity comes in sizes [1]. His contemporaries called the work a disease and a corruption of mathematics. Today it is bedrock.

The whole story rests on one disarmingly simple question: what does it actually mean to count? In this paper we check into a hotel that is always full but always has room, learn to count without numbers, and then meet the most famous four-line proof in mathematics. The ending is genuinely strange: almost every number is one that nobody can ever name.

I. The full hotel with a free room

Picture a hotel with infinitely many rooms — room 1, room 2, room 3, and so on without end. Tonight, every room is occupied. A traveller arrives and asks for a room. A normal hotel would turn them away. But the manager simply announces: "Everyone move up one room, please." The guest in room 1 moves to room 2, the guest in room 2 to room 3 — in general, room $n$ moves to room $n+1$. Every existing guest still has a room, and room 1 is now empty. The traveller checks in. The full hotel had room for one more.

Ten minutes later, an infinite coach pulls up, carrying passengers numbered 1, 2, 3, … forever. One spare room per announcement won't do. The manager doesn't blink: "Everyone move to double your room number." Room 1's guest goes to room 2, room 2's to room 4, room $n$'s to room $2n$. Every guest lands in a room of their own — and every odd-numbered room is now free. There are infinitely many of those, so coach passenger $k$ takes odd room $2k-1$. The full hotel just absorbed an infinite crowd.

This thought experiment comes from a 1924 lecture by David Hilbert, and its moral is that our finite intuitions — "full means no room", "part is smaller than whole" — simply do not survive contact with infinite sets. If we want to compare infinities, we need a sharper tool than intuition.

II. Counting is pairing

Here is the sharper tool. When you count five sheep, what you are really doing is pairing sheep with the numbers 1 to 5, using each number once and missing no sheep. Cantor's insight was that the pairing is the essence of counting, and pairing works even when the sets are infinite:

Two sets are the same size if their members can be paired off perfectly — nothing left over on either side.

The hotel already showed us something shocking in this language. Pairing $n \leftrightarrow 2n$ matches the whole numbers perfectly with just the even numbers. Nothing is left over on either side, so by our definition the evens — "half" the whole numbers! — are exactly the same size of infinity. The same trick works for the integers: list them as $0, 1, -1, 2, -2, 3, -3, \ldots$ and they pair with $1, 2, 3, 4, 5, 6, 7, \ldots$ perfectly. A set that can be paired with $1, 2, 3, \ldots$ like this is called countable: its members can be arranged in a single unending queue.

Surely the fractions break this? Between 0 and 1 alone there are infinitely many of them, and between any two fractions sit infinitely more. There isn't even a "next" fraction after $\tfrac{1}{2}$. Yet the fractions form a queue too. Arrange every positive fraction in a grid — one row for each numerator, one column for each denominator — and no fraction escapes: $\tfrac{p}{q}$ sits in row $p$, column $q$. Now walk the grid diagonal by diagonal, zig-zagging so that we sweep every diagonal in turn, and skip any fraction we have already met in disguise (we skip $\tfrac{2}{2}$ because it equals $\tfrac{1}{1}$):

Each diagonal is finite, so every fraction gets swept up after finitely many steps: the queue reads $\tfrac{1}{1}, \tfrac{1}{2}, \tfrac{2}{1}, \tfrac{3}{1}, \tfrac{1}{3}, \tfrac{1}{4}, \tfrac{2}{3}, \tfrac{3}{2}, \ldots$ and every fraction has a definite position in it. The fractions are countable. At this point a reasonable person concludes that every infinite set is countable and the phrase "bigger infinity" is empty. Cantor thought so too — until he tried the decimals.

III. The list that cannot exist

Now for the crown jewel. Consider all the decimal numbers between 0 and 1 — not just the tidy fractions, but every unending decimal expansion: $0.500000\ldots$, $0.141592\ldots$, $0.101001000\ldots$ and the rest. We ask: can these be arranged in a queue?

Suppose someone claims they have done it. They hand us a complete infinite list: a first decimal, a second, a third, and so on, and they swear every decimal between 0 and 1 appears somewhere. For instance, it might begin:

$$\begin{aligned} 1 &: 0.\mathbf{1}23456\ldots \\ 2 &: 0.5\mathbf{5}5555\ldots \\ 3 &: 0.71\mathbf{8}281\ldots \\ 4 &: 0.314\mathbf{1}59\ldots \\ 5 &: 0.1010\mathbf{0}1\ldots \end{aligned}$$

We will now build a number that cannot be anywhere on their list — whatever their list is. The recipe looks only at the diagonal: the 1st digit of the 1st number, the 2nd digit of the 2nd, the 3rd of the 3rd, and so on (shown in bold above). Define a new number $d$, digit by digit:

For the $n$-th digit of $d$: look at the $n$-th digit of the $n$-th number on the list. If that digit is a 5, write 6. Otherwise, write 5.

For the list above, the diagonal reads $1, 5, 8, 1, 0, \ldots$, so $d = 0.56555\ldots$ — but the point is the rule, not this example. Where can $d$ live on the list? It can't be the 1st number: it differs from it in the 1st digit, by construction. It can't be the 2nd: it differs in the 2nd digit. In general $d$ disagrees with the $n$-th listed number at the $n$-th decimal place, so it is not the $n$-th entry for any $n$:

Yet $d$ is certainly a decimal between 0 and 1. So the list — sworn to be complete — is missing a number. And nothing here depended on which list we were handed: any proposed list of the decimals manufactures its own fugitive. No queue can ever contain them all. (One technical whisker: some numbers wear two decimal disguises, like $0.4999\ldots = 0.5$ — a fact we prove in another article. Our recipe dodges the issue: $d$ is written entirely in 5s and 6s, and no number made of 5s and 6s can be a disguise of a different expansion, since only expansions ending in endless 0s or 9s have doubles.)

The conclusion is inescapable and historic. The decimals form an infinity that is strictly bigger than the infinity of whole numbers. The whole numbers, the evens, the integers, the fractions — all one size, all countable. The decimals: uncountable. Too many to queue.

IV. The tower with no top

Cantor gave the sizes names. The size of the whole numbers is $\aleph_0$ ("aleph-nought") — the smallest infinity. The size of the decimals is called $\mathfrak{c}$, the continuum, and it equals $2^{\aleph_0}$: intuitively, an endless decimal is an infinite sequence of digit choices, and making one independent choice per whole number gives two-to-the-power-of-$\aleph_0$ outcomes. The tower doesn't stop there — Cantor also proved that no set can be paired with the collection of all its subsets, so taking "the set of all subsets" always produces a strictly bigger infinity, forever. There is no biggest infinity.

An obvious question remains, and its fate is stranger than anything so far: is there an infinity strictly between $\aleph_0$ and $\mathfrak{c}$? Cantor believed not — this is the continuum hypothesis — and he spent years failing to prove it. The resolution came in two halves, and it is not what anyone expected. In 1940 Kurt Gödel showed the continuum hypothesis can never be disproved from the standard axioms of set theory [2]; in 1963 Paul Cohen showed it can never be proved from them either [3]. Together: the standard rules of mathematics are simply silent. This is not "we haven't solved it yet" — it is a theorem that, from the accepted axioms, the question has no answer. Whether a between-size infinity "really" exists depends on which extra axioms you are willing to adopt, and mathematicians still argue about it.

V. The numbers with no name

Here is the payoff, and it is worth sitting with. Every number you have ever met has a name — a finite description that pins it down. "Three sevenths." "The square root of 2." "The ratio of a circle's circumference to its diameter." Every such description is a finite string of symbols drawn from a finite alphabet.

But finite strings can be queued: list them by length — all one-symbol strings, then all two-symbol strings, and so on, alphabetically within each length (exactly the catalogue our monkeys typing Shakespeare work through). Each batch is finite, so every string has a definite position. The nameable numbers are therefore at most countable: size $\aleph_0$. The decimals are uncountable. So the numbers we can name — every fraction, $\sqrt{2}$, $\pi$, $e$, every number any formula or computer program will ever single out — form a vanishing speck inside the continuum. Almost every number is one that no phrase, formula or program can ever specify. They are not exotic outliers; they are the overwhelming majority. Mathematics' celebrities — $\pi$, $e$, $\sqrt{2}$ — are a countable red carpet stretched across an uncountable, anonymous crowd.

VI. What 'bigger' really means

We asked what counting means, and the answer — pairing — carried us further than intuition wanted to go. Full hotels have room. The even numbers are no smaller than all the numbers. The fractions queue up politely; the decimals cannot be listed at all, so the continuum is a strictly bigger infinity than $\aleph_0$ — and the tower of infinities climbs forever, with a gap question the standard axioms provably cannot settle.

One honest caveat: "bigger" here means cardinality, the pairing notion of size, which is the faithful way to extend counting. Other useful notions measure differently — along the number line, for instance, the evens have density one-half among the whole numbers even though the two sets pair perfectly. Size, at infinity, depends on what you choose to preserve; Cantor's achievement was showing that once you choose counting, the sizes genuinely differ. Not bad for a "disease". As for the anonymous numbers we just met — they were there all along, an uncountable silent majority, waiting for someone to prove that no one would ever call their names.

---

References:

[1] Georg Cantor, "Über eine elementare Frage der Mannigfaltigkeitslehre," Jahresbericht der Deutschen Mathematiker-Vereinigung 1 (1891): 75–78.

[2] Kurt Gödel, The Consistency of the Continuum Hypothesis (Princeton University Press, 1940).

[3] Paul J. Cohen, "The Independence of the Continuum Hypothesis," Proceedings of the National Academy of Sciences 50 (1963): 1143–1148, and 51 (1964): 105–110.

Note: "Unanswerable" throughout means independent of ZFC, the standard axioms of set theory; stronger axiom systems can and do take sides on the continuum hypothesis. Hilbert's hotel is recorded from his 1924 Göttingen lecture and was popularised by George Gamow's One Two Three… Infinity (1947).