A hotel with infinitely many rooms, all full, can always fit more guests, even infinitely many busloads. But there is a kind of infinity no hotel can hold. Move the guests, then build a number that escapes every list.
Rooms are numbered 1, 2, 3, and so on forever, and every room has a guest. Nobody may share a room, and nobody is left outside. You can only show the first sixteen rooms, but the rule you announce applies to every room at once.
Every move sends each guest to a room with a definite number, so anyone can work out where to go without waiting for anyone else. The zigzag is exactly how you list every fraction p/q, which is why there are no more fractions than whole numbers.
Two sets are the same size if their members can be paired off one to one, with nothing left over. Any set you can arrange in a list (first, second, third, …) is "countable" and the same size as the counting numbers.
| Set | A list that catches every member | Size |
|---|---|---|
| Counting numbers | 1, 2, 3, 4, … | countable, ℵ₀ |
| Even numbers | 2, 4, 6, 8, … (room n → room 2n) | countable, ℵ₀ |
| All integers | 0, 1, −1, 2, −2, 3, … | countable, ℵ₀ |
| Fractions (rationals) | zigzag through the grid of p/q, skipping repeats: 1/1, 2/1, 1/2, 1/3, 3/1, … | countable, ℵ₀ |
| Real numbers | impossible: the diagonal below escapes any list you try | uncountable, 2ℵ₀ |
Suppose someone hands you a numbered list that, they claim, contains every infinite string of digits. Go down the diagonal: change the 1st digit of row 1, the 2nd digit of row 2, and so on. The result differs from every row in at least one place, so it was never on the list.
Click any digit in the list to change it; the new string updates to dodge it. Then try "Add the new string to the top": the list shifts down, the diagonal runs again, and out comes another string the list missed.
In the hotel, every rule is a one-to-one pairing between guests and room numbers. "1 new guest" uses n → n + 1. "A bus" uses n → 2n for current guests and the odd rooms 2k − 1 for passengers. For infinitely many buses, the zigzag walks the grid of (bus, seat) along its diagonals; the prime-power plan sends current guests to 2n and bus b's passengers to the b-th odd prime raised to the seat number.
In the diagonal grid, row k is the k-th string on the list. Binary digits are flipped. Decimal digits become 5, or 4 if they were already 5, which avoids the 0.0999… = 0.1000… double-spelling problem.
For finite sets, a part is always smaller than the whole. For infinite sets that fails: the even numbers are half of the counting numbers, yet pair off with them perfectly. Galileo noticed this with square numbers in 1638 and concluded infinite sets can't be compared. Cantor showed they can, and that they don't all match.
His 1874 paper proved the real numbers can't be listed; the diagonal argument of 1891 made it a one-line idea and showed there is no largest infinity at all. Whether any size sits between the countable and the reals (the continuum hypothesis) turned out to be unprovable either way from the standard axioms (Gödel 1940, Cohen 1963).
Cantor's trick turned into one of the most useful ideas in logic and computer science. Wherever you can list all the things of one kind, the diagonal builds something outside the list, and that marks out what computers and proofs can never do.
In 1936 Alan Turing proved no program can decide, for every program and input, whether it will eventually stop. List all programs; a "contrarian" program that does the opposite of what the checker predicts for program k on input k differs from every program on the list. Every program analyser lives with this limit.
In the demo: row k, digit k, flipped.Fred Cohen showed in 1987 that deciding whether any given program is a virus is undecidable, by the same diagonal reasoning. Rice's theorem extends it to any non-trivial question about what a program does. Real scanners use signatures and heuristics, and accept missing some threats or flagging some safe files.
In the demo: whatever list of verdicts you write, the diagonal dodges it.In 1931 Kurt Gödel coded every formula as a single number using products of prime powers, then built a statement that in effect says "I am not provable". Any consistent system strong enough for arithmetic has true statements it cannot prove.
In the demo: the prime-power plan packs many sequences into one numbering.Every program is a finite string of symbols, so programs can be listed, and the numbers some program can print digit by digit are countable. The reals are not. So almost every real number has no program that computes it, and computers only ever work with a thin, countable slice of the number line.
In the demo: fill the list with every computable number; the diagonal is still missing.The zigzag gives a formula that turns any pair of whole numbers into one whole number and back, known as the Cantor pairing function. Programmers use it and its cousins to key a table by two numbers at once, such as grid coordinates, and logicians use it to encode pairs, lists and programs as single numbers.
In the demo: bus b, seat k → one room number.There are 2n files of n bits but fewer than 2n shorter files, so no lossless compressor can shrink every file; some must stay the same size or grow. It is the same counting-by-pairing idea Cantor used, applied to finite sets, and why zipping a zip file doesn't help.
In the demo: sizes are compared by pairing members off.