The Sizes of Infinity: why some infinities are bigger than others

Jul 10, 2026 · #mathematics #logic #infinity

Infinity is not a single thing. In 1874 Georg Cantor proved that some infinities are strictly larger than others: the whole numbers can be lined up and counted, but the decimals between 0 and 1 cannot. The same one-line trick that shows this also shows that almost every number is uncomputable, and that no system of logic can ever be complete.

Cover: a supposedly complete list of decimals, with the diagonal digits highlighted and a new number, 0.555…, built to differ from every row — Hand me a "complete" list of every decimal, and I can always build the one number your list forgot, by walking down the diagonal and changing each digit.

Ask a child’s question: how many numbers are there? The answer comes instantly: “infinitely many.” Now a nastier one: are there more fractions than whole numbers? More decimals than whole numbers? Your intuition shouts “yes, obviously” both times, and it is wrong once and right once. In 1874 a mathematician named Georg Cantor proved something his contemporaries found so scandalous that it helped wreck his career: infinity comes in different sizes. Some infinities are strictly bigger than others. And the proof fits in a single picture.

How do you compare two infinities?

You cannot count an infinite set: you never reach the end. Cantor’s unlocking idea is simple: to say two sets are the same size, you do not need to count them, you only need to pair them up one-to-one, with nothing left over on either side. If every element on the left can be married to exactly one element on the right and vice versa, the two sets have the same “size” (the technical word is cardinality). That’s the whole tool.

Forget the jargon and keep one image: the shepherd with no numbers. A shepherd who cannot count can still know his flock is complete. Each morning, one sheep out, one pebble aside: one sheep, one pebble. Each evening, one sheep in, one pebble away. If no pebble is left and no sheep is still outside, the count is right, without ever naming a number. That is pairing. Not counting: matching.

This little move has an immediate, disorienting consequence. Take the whole numbers 1, 2, 3, 4… and the even numbers 2, 4, 6, 8… There are “obviously” half as many evens (we threw away every other one). And yet you can marry them perfectly: 1↔2, 2↔4, 3↔6, 4↔8… every whole number gets its own even partner, nobody is left single. So there are exactly as many even numbers as whole numbers. With infinity, “half” can be just as big as the whole. Welcome.

Hilbert’s Hotel: the infinity that always has room

To tame this kind of infinity, the mathematician David Hilbert invented an image that has become famous. Picture a hotel with an infinite number of rooms, numbered 1, 2, 3, 4… and tonight it is full: every room taken. A traveller arrives. “Sorry, full”? No! The clerk simply asks each guest to shift up one room: room 1 moves to 2, room 2 to 3, and so on. Room 1 falls empty, the newcomer checks in. The hotel was full, and it made room without turning anyone away.

The magic of countable infinity: you can always open room at the front by pushing everyone up one. A whole infinite busload of newcomers fits too (put the old guests in the even rooms, the new ones in the odd rooms). Even infinitely many infinite buses still fit. This is the infinity of the whole numbers, call it countable: anything you can put in a single queue and number 1, 2, 3…

And here is where it turns genuinely strange. The fractions (1/2, 3/4, 22/7…) look infinitely more numerous than the whole numbers: there are already infinitely many just between 0 and 1. Yet they fit in the hotel too. Cantor lays them out in a grid (numerator down the rows, denominator across the columns) and sweeps through them diagonally, in a zig-zag. Done that way, every fraction eventually gets an order number. So the fractions are countable as well. The “bigger” infinity we imagined was not bigger at all. The trick is the zig-zag: sweep by diagonals instead of trying to finish an endless first row, and you reach every fraction in a finite number of steps.

The thunderclap: Cantor’s diagonal

By now you might bet that every infinity is countable, that deep down there is only one kind of infinity. This is where Cantor strikes. Take the “real” numbers between 0 and 1: all the decimals with an endless string of digits (0.333…, 0.141592…, 0.500000…). Cantor proves they do not fit in the hotel: it is impossible to put them in a queue. The proof is diabolically elegant: the diagonal argument.

The reasoning is by contradiction. Suppose you have succeeded: a complete list, numbered 1, 2, 3…, that contains every real number between 0 and 1. Cantor then builds, right in front of you, a number that cannot be on it. He walks down the diagonal of your list and constructs his number one decimal at a time, with a single rule: “for the n-th decimal, I pick a digit different from the n-th decimal of the n-th number on the list.”

The rule here: every diagonal digit becomes a 5. The number built, 0.55555…, differs from row 1 in the 1st decimal, from row 2 in the 2nd, from row 3 in the 3rd… It differs from every row in at least one place, so it cannot equal any of them. Your "complete" list was not complete after all, and this works for any list you propose.

Take the hit. This manufactured number differs from every row of your list (at least at the decimal that carries its number). So it is not on the list. So your list (which we assumed was complete) is not. And the argument depends on no particular list: any attempt to queue up the reals will always leave at least one number outside. The conclusion is unavoidable: the reals are not countable. There are strictly more of them than there are whole numbers. It is a bigger infinity. Don’t memorise the notation, keep two heaps and one image. Heap one: everything you can line up (whole numbers, fractions), the “listable” infinity, the hotel. Heap two: the reals, a continuum so dense it overflows every possible queue. The image: heap one is sand you can shelve grain by grain; heap two is water: you don’t shelve it grain by grain, it fills everything. And there is more water than sand.

A tower with no top

Cantor does not stop there. He proves a general result (his “theorem”): starting from any set, the set of all its subsets (every group you can carve out of it) is always strictly bigger. Apply that on repeat: from the reals you get a still-bigger infinity; from that one, bigger again… There is no largest infinity. You climb a tower of infinities with no top.

Each floor is "the set of all subsets" of the one beneath, and it is always strictly larger. The tower rises forever: there is no "largest infinity" to crown them all.

The twist that reaches computers

Here is the payoff that turns a curiosity into something with teeth. Computer programs (every finite string of instructions you can write) are countable (each program is a finite text, so you can queue them up, just like the fractions). But the real numbers are not countable. So there are infinitely more numbers than there are programs able to compute them. The blunt, true consequence: almost every real number is uncomputable, unnameable: no algorithm, no formula, no finite sentence will ever pin it down. Such numbers exist, yet stay forever beyond any description, one by one.

And it is exactly the same move as three of the deepest results in logic. Gödel’s incompleteness (1931) builds a true statement no formal system can prove (“this statement is unprovable”) by the same self-referential diagonal. Turing’s halting problem (1936) shows no program can decide, for all programs, whether they stop, again by diagonalising against the list of all programs. And Russell’s paradox (1901) kills the idea of a “set of all sets” with the very same twist: consider the catalogue of all catalogues that do not list themselves: does it list itself? Cantor, Russell, Gödel, Turing: one diagonal, four earthquakes. The pattern is always the same: take any list that claims to contain everything, then explicitly construct the thing it left out.

Where this stands in 2026

The neat “tower of infinities” is not a settled museum piece: it is live, and lately messier than the textbooks suggest. In June 2025, Quanta Magazine reported that two newly constructed large cardinals refused to slot into the tidy hierarchy of infinite sizes: instead of stacking cleanly, they “exploded” and spawned a new class of infinities, hinting that far more chaos lurks in the architecture of infinity than anyone expected (Quanta · “Is Mathematics Mostly Chaos or Mostly Order?”). The clean picture drawn above is a useful model, not carved truth.

Infinity is not just abstract, either: it makes real machines sweat. In October 2024 the collaborative GIMPS project established that 2^136,279,841 − 1 is prime: 41,024,320 decimal digits, the 52nd known “Mersenne prime,” more than 16 million digits past the previous record. It was found by Luke Durant on a “cloud supercomputer” of thousands of GPUs spread across 17 countries (GIMPS · the M136279841 announcement). Euclid proved 2,300 years ago that the primes are infinite; this record hunt is humanity climbing, one rung at a time, a ladder we already know has no end.

And some think we should climb down. In April 2026, Quanta covered a Columbia gathering where physicists, logicians and philosophers pitted real infinity against the ultrafinitists (who hold that sufficiently large numbers do not truly “exist”) while the physicist Sean Carroll asked whether the universe is genuinely infinite “or merely quite large” (Quanta · “What Can We Gain by Losing Infinity?”). If the fabric of reality is finite, then Cantor’s tower is a purely mental cathedral: magnificent, and with no physical floor to stand on.