What does Cantor's diagonal argument prove?

It proves that the real numbers between 0 and 1 are uncountable: no list, no matter how cleverly constructed, can contain every real number in that interval. There are simply more real numbers than there are positions on any list.

What does 'uncountable' mean?

A set is countable if you can pair each of its members with a natural number (1, 2, 3, ...) so that nothing is left out. The natural numbers, integers, and even the rationals are all countable. The reals are not: they are too numerous to be placed in any such one-to-one correspondence.

Why can't you just add the missing number to the list?

You can, but then the diagonal argument applies again to the new, longer list and produces yet another missing number. The argument works for any list, however long or cleverly arranged, so there is no way to patch the list into completeness.

Why do you avoid the digits 0 and 9 when flipping?

Some real numbers have two decimal representations: 0.4999... and 0.5000... are the same number. If you flip a digit to 0 or 9 you might accidentally land on the 'other name' for a number already on the list. Avoiding 0 and 9 sidesteps this technicality and keeps the proof clean.

Are the rational numbers also uncountable?

No. The rational numbers are countable: you can systematically list every fraction p/q and assign each one a natural number index, leaving nothing out. Cantor's diagonal argument targets the real numbers, not the rationals.

Cantor's Diagonal Argument: Why the Real Numbers Cannot Be Listed

Suppose someone hands you a list. It is an infinite list, and they claim it contains every real number between 0 and 1. Not a sample, not a selection: every single one, indexed neatly as r1, r2, r3, and so on, stretching forever.

Georg Cantor's response, in 1891, was this: whatever list you hand me, I can read off a number that is not on it. The construction takes about thirty seconds to describe. The consequence took decades for mathematicians to absorb, because it means infinity comes in more than one size.

Counting and Listing

Before the diagonal move, it helps to be precise about what "countable" means. A set is countable if you can assign each element a unique natural number label: a first element, a second, a third, and so on, with nothing left over. The natural numbers themselves are countable by definition. So are the integers (list them as 0, 1, -1, 2, -2, ...) and even the rationals, though listing every fraction requires a clever zigzag pattern.

Cantor's argument shows that the real numbers between 0 and 1 are genuinely different: no labeling exists, no matter how you try. This is not a failure of imagination. It is a proof that the task is impossible.

Assume the List Exists

The argument is a proof by contradiction. Start by granting the opponent everything they want: assume a complete list of every real number in (0, 1) actually exists. Write each number as an infinite decimal expansion.

The list might begin like this:

r1 = 0.14159265...
r2 = 0.73205080...
r3 = 0.00000000...
r4 = 0.27182818...
r5 = 0.91415926...
...

Each entry goes on forever. The list goes on forever. And, by assumption, every real number between 0 and 1 appears somewhere on it.

Now watch what happens when you read down the diagonal.

Reading the Diagonal

Look at the first decimal digit of r1, the second decimal digit of r2, the third of r3, and so on. In the example above, those diagonal digits are: 1, 3, 0, 2, 9, ...

You now build a new number, call it d, one digit at a time. The rule: for each diagonal digit, choose a different digit, but deliberately avoid 0 and 9.

r₁	.	1	4	1	5	9
r₂	.	3	3	3	3	3
r₃	.	5	0	0	0	0
r₄	.	7	1	8	2	8
r₅	.	6	0	2	5	9
new	.	2	4	1	3	8	…

Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.

The diagonal digits are 1, 3, 0, 2, 9. Applying the rule produces 2, 4, 1, 3, 8. So d = 0.24138...

The avoidance of 0 and 9 is a small but necessary guard. Some real numbers have two decimal representations: 0.4999... and 0.5000... name the same point on the number line. Flipping a digit to 0 or 9 could land you on the "other name" for a number already on the list, which would muddy the argument. By staying in the range 1 through 8 for every flipped digit, you guarantee that d has exactly one decimal expansion, and the comparison below is clean.

The New Number Differs from Every Entry

Here is the payoff.

d differs from r1 at the first decimal place

The first digit of d was chosen to differ from the first digit of r1. So d is not equal to r1. They differ at position 1.

d differs from r2 at the second decimal place

The second digit of d was chosen to differ from the second digit of r2. So d is not equal to r2. They differ at position 2.

d differs from rn at the nth decimal place, for every n

By construction, the nth digit of d differs from the nth digit of rn. Since two numbers with a different digit at any position are unequal, d is not equal to rn, for any n you name.

This is the diagonal move: d was designed to clash with every entry on the list, at the one spot where each entry is most exposed, its own diagonal position.

d is a real number between 0 and 1, yet it is not on the list

The number d = 0.24138... is clearly a real number in the interval (0, 1). But we just showed it differs from r1, from r2, from r3, from every entry. If the list were complete, d would have to appear somewhere on it. It does not. So the list is not complete.

The contradiction is sharp: we assumed the list was complete, and we produced a real number not on it. The assumption must be false. No complete list of the real numbers between 0 and 1 can exist.

What This Actually Says

Mathematicians say the natural numbers have cardinality aleph-null (written with the Hebrew letter aleph: the first transfinite cardinal). The real numbers have a strictly larger cardinality, sometimes written as c or as 2 to the power of aleph-null. Cantor's argument is what establishes that these two infinities are not the same size.

This was deeply controversial when Cantor published it. Some colleagues dismissed the result as a curiosity or an error. It is neither. It sits at the foundation of how mathematicians think about sets, cardinality, and the structure of the real number line, and it connects directly to questions about what can and cannot be computed (see also the proof in Goodstein's theorem for another case where something provably true pushes against the limits of formal systems).

Why the Diagonal Works

What makes the argument elegant is its specificity. You are not guessing at a missing number or appealing to vague intuition about how large the reals are. You are reading off exactly which positions on the list each entry controls, and then building a number that evades every entry at precisely that position.

The list itself tells you where to look. Every entry on the list hands you one coordinate, its own diagonal digit, and the construction turns those coordinates into a number the list cannot contain.

The simplicity is deceptive. There is nothing here that requires knowing anything about the entries on the list. It does not matter what numbers are on it, in what order, or how they were chosen. The argument is universal: pick any list of real numbers, and the diagonal construction produces a real number not on that list.

The Zen of It

Cantor's diagonal argument sits in a long tradition of mathematical results that feel like they should not work. You stare at the proof and wait for the trick, the hidden assumption, the place where the logic slips. It is not there. The proof is exactly as simple as it looks.

What it asks you to accept is stranger than the proof itself: that "infinite" is not a single destination. The integers and the reals are both infinite, but they are infinite in categorically different ways. The diagonal argument is the dividing line.

For a deeper sense of how infinite collections can behave strangely, the structure of infinite decimals is a good place to look next, or how limits work when sequences approach a value forever without reaching it. The diagonal argument belongs in that same family: a precise, patient look at what happens at the edge of the infinite, where intuition needs a proof to keep it honest.

Infinity is not one thing. That is the news. The argument that delivers it fits on half a page.