Claim◆Audio · 43:34 — 47:25
Some infinities are larger than others, and Cantor's diagonal argument proves that the set of real numbers is strictly larger than the set of natural numbers.
Cantor's diagonal argument proves the real numbers are uncountably infinite — strictly larger than the countable infinity of the natural numbers — by constructing a real number that differs from every entry in any putative enumeration. ✦ AI generated
Joel David Hamkins · Lex Fridman · 2025-12-31 · original ↗
plays this moment only · 43:34 — 47:25
Elicited by
“Can you explain the idea of infinity that some infinities are larger than others, and why was this so transformative to mathematics?”
Cantor wants to prove that the infinity of the real numbers is different and strictly larger than the infinity of the natural numbers. [...] Suppose that the real numbers can be put into one-to-one correspondence with the natural numbers. So therefore, for every natural number n, we have a real number, let's call it R sub n. R sub n is the nth real number on the list. [...] I'm going to define the number z, and it's going to be the integer part is going to be a 0, and then I'm going to put a decimal place, and then I'm going to start specifying the digits of this number Z. D1, D2, D3, and so on. And what I'm going to make sure is that the nth digit after the decimal point of Z is different from the nth digit of the nth number on the list. [...] But now it follows that Z is not on the list because Z is different from R1 because, well, the first digit after the decimal point of Z is different from the first digit of R1 after the decimal point. That's exactly how we built it. And the 2nd digit of Z is different from the 2nd digit of R2 and so on. The nth digit of Z is different from the nth digit of R sub n for every n. So therefore, Z is not equal to any of these numbers R sub n.
verbatim transcript · starts at 43:34
- ·Cantor proved real infinities are strictly larger than natural infinities
- ·Natural numbers are countably infinite (1, 2, 3, …)
- ·Real numbers are uncountably infinite — a bigger infinity
- ·Assume real numbers can be matched 1-to-1 with natural numbers
- ·List them: R₁, R₂, R₃, … for each natural number n
- ·Construct a new number Z by changing each diagonal digit
- ·Z's nth digit differs from the nth digit of Rₙ
- ·Z differs from every R₁, R₂, R₃, … at position n
- ·Contradiction: the list cannot contain all real numbers
Around this claim
Context · 3
The historical tension between the Cantor-Hume principle (sets are equinumerous when in one-to-one correspondence) and Euclid's principle (the whole is always greater than the part) was not fully resolved until Cantor.Joel David Hamkins · Lex Fridman · conf 85%The tension between the Cantor-Hume principle (one-to-one correspondence determines size) and Euclid's principle (the whole is greater than the part) was not fully resolved until Cantor, who showed that infinite sets can violate Euclid's principle and that there are different sizes of infinity.Joel David Hamkins · Lex Fridman · conf 80%A set is countable if it fits into Hilbert's Hotel, and countably many countable sets put together still form only a countable infinity—a strong violation of Euclid's principle.Joel David Hamkins · Lex Fridman · conf 60%
Extends · 2
The diagonalization idea—abstracted from Cantor's proof that the power set of any set is strictly larger than the set itself—is the core of Russell's paradox, the halting problem, the recursion theorem, and almost every major result in mathematical logic.Joel David Hamkins · Lex Fridman · conf 85%Cantor's power set theorem — that for any set, its power set is strictly larger — is the general form of the argument that there are infinitely many sizes of infinity, and it can be understood through the intuitive metaphor that there are more committees than people.Joel David Hamkins · Lex Fridman · conf 85%