Thank you for visiting this site. This article covers “Cantor’s Diagonal Argument.”
Infinity is infinity — nothing more, nothing less. Or so it seems. In the 19th century, German mathematician Georg Cantor proved that infinities have different sizes. And the proof, once understood, is so elegant you can’t help but marvel at it.
Is All Infinity the Same Size?
First, the natural numbers (1, 2, 3, 4 …) are infinite. The even numbers (2, 4, 6, 8 …) are also infinite.
Intuitively, the natural numbers seem more numerous than the even numbers — but these two sets are actually “the same size of infinity.” For every natural number n we can pair an even number 2n: the correspondence 1↔2, 2↔4, 3↔6, 4↔8 … assigns exactly one even number to every natural number, with no gaps or duplicates.
Now what about the “real numbers” — all numbers including decimals, such as 0.1415926… ? The reals are also infinite. Are they the same size of infinity as the natural numbers?
Cantor proved with the diagonal argument that the real numbers are “strictly more” than the natural numbers.
How the Diagonal Argument Works
The proof uses contradiction. We assume “the real numbers between 0 and 1 can all be paired one-to-one with the natural numbers” and then derive a contradiction.
Suppose we could list every real number between 0 and 1:
- Real #1: 0.51209347…
- Real #2: 0.33817260…
- Real #3: 0.71038492…
- Real #4: 0.49027351…
- Real #5: 0.82615094…
- …
Now focus on the “diagonal digits”: the 1st digit of the 1st real, the 2nd digit of the 2nd real, the 3rd digit of the 3rd real, and so on. Reading them off gives 5, 3, 0, 2, 5… (the bold digits above).
Next, construct a new decimal by changing each diagonal digit — for example, add 1 to each (and turn 9 into 0). The result is 6, 4, 1, 3, 6…, giving the new real number 0.64136…
This new real number is not on the list anywhere.
- It differs from real #1 in its 1st digit (5→6)
- It differs from real #2 in its 2nd digit (3→4)
- It differs from real #3 in its 3rd digit (0→1)
- It differs from real #n in its nth digit
We assumed the list contained all real numbers — yet we just constructed one that isn’t on the list. That is a contradiction.
Therefore, the real numbers between 0 and 1 cannot be numbered by the natural numbers, and the reals are strictly “more” than the natural numbers.
The Hierarchy of Infinity
Cantor’s discovery was revolutionary. Infinity is not a single thing; there are different sizes of infinity.
Infinities that can be counted (like the natural numbers) are called “countably infinite (aleph-null),” while infinities that cannot be counted (like the reals) are called “uncountably infinite.”
More astonishingly, the hierarchy never ends. Beyond the infinity of real numbers lies an even larger infinity, and beyond that a still larger one — the levels of infinity go on infinitely.
The Reaction at the Time
Cantor published the diagonal argument in 1891, and it was met with fierce criticism from the mathematical establishment.
The influential mathematician Leopold Kronecker called Cantor a “corrupter of youth” and attacked him relentlessly. Kronecker held that “God made the integers; all else is the work of man,” and the idea that some infinities are larger than others was simply unacceptable to him.
Yet Cantor’s proof was logically airtight, and over time it was accepted by the mathematical community. Today the diagonal argument is widely regarded as one of the most beautiful proofs in all of mathematics.
The diagonal argument is used in other fields too
The value of the technique is not confined to proving the uncountability of the reals. Arguments of the same shape produced several of the twentieth century’s most important theorems.
Where it was carried over to
| Theorem | Published | How the diagonal argument is used |
|---|---|---|
| Russell’s paradox | 1901 | constructs, diagonally, the set of sets not containing themselves |
| Gödel’s incompleteness theorems | 1931 | constructs, diagonally, “this proposition is unprovable” |
| Turing’s halting problem | 1936 | constructs, diagonally, a program returning the opposite of the verdict |
| The time hierarchy theorem | 1965 | shows that more available time means more solvable problems |
What they share is the procedure of assuming everything has been listed and then constructing something the list does not contain.
For Gödel, it is a true proposition absent from the list of provable propositions. For Turing, it is a program absent from the list of programs whose halting can be decided.
The moment the list is made, something outside it can be constructed. The pattern Cantor found for infinite sets became the standard instrument for demonstrating the limits of a system.
The continuum hypothesis, left over
The diagonal argument showed that there are more reals than naturals. Is there a size in between?
Cantor conjectured that there is no intermediate size, and called this the continuum hypothesis. He spent his life attempting a proof without success.
The matter was settled in the middle of the twentieth century. Gödel in 1940 and Paul Cohen in 1963 showed, respectively:
- The continuum hypothesis cannot be proved from the current axioms of set theory
- It cannot be refuted from those axioms either
So the conclusion is that it can be decided neither true nor false. Cantor’s failure was not a matter of ability; the problem admits of no settlement in the first place.
How Cantor himself was treated
How a man who made a discovery of this importance was treated in his own lifetime is worth setting down.
From the 1870s through the 1890s, while Georg Cantor was publishing the hierarchy of infinities, the mathematical world’s reaction was cold.
The fiercest opposition came from Leopold Kronecker, a leading figure at the University of Berlin. Known for the line “God made the integers; all else is the work of man”, he sought to shut out of mathematics anything not constructible by a finite procedure.
Kronecker is said to have obstructed the publication of Cantor’s papers and blocked his appointment at Berlin. Cantor spent his entire career at the provincial University of Halle.
- 1874: publishes the first proof of uncountability. It is almost entirely ignored
- 1884: falls into his first severe depression; repeated hospital admissions follow
- 1891: publishes the diagonal argument, in the form still used today
- 1918: dies in the sanatorium where he was being treated
Whether academic criticism was the sole cause of the depression is not known; the anguish of failing to settle the continuum hypothesis is said to have compounded it.
Until the verdict reversed
The tide turned after the turn of the century. At the 1900 International Congress of Mathematicians, the first of Hilbert’s twenty-three problems was the continuum hypothesis. Cantor’s question stood at the head of the problems mathematics recognised as most important.
Hilbert went further in a 1926 lecture, defending set theory as a foundation for mathematics with the words “no one shall expel us from the paradise that Cantor has created for us”.
Set theory now underlies almost every field of mathematics. A theory treated as heresy in its author’s lifetime is now taught as a premise.
The lag before a new idea is accepted, and the price its author pays in the meantime — Cantor’s life shows both in a fairly harsh form.
The conclusion that infinities come in sizes is strange however often one reads it, and what impresses me every time is the sheer neatness of the diagonal argument’s execution.
Related paradoxes of mathematical infinity
Related paradoxes about the counter-intuitive behaviour of infinite sets.
Summary
This article covered “Cantor’s Diagonal Argument.”
The discovery that infinities have different sizes is one of the most revolutionary achievements in the history of mathematics. The proof itself — nothing more than changing the diagonal digits — is both disarmingly simple and utterly ironclad.
To return to the full list of paradoxes, follow the link below.
Thank you for reading. We hope to see you in the next article.
Also popular with readers
📚 Series: The World's Paradoxes (19/81)
