[@lexfridman] Infinity, Paradoxes, Gödel Incompleteness & the Mathematical Multiverse | Lex Fridman Podcast #488

Link: https://youtu.be/14OPT6CcsH4

Duration: 232 min

Short Summary

Joel David Hamkins, a mathematician and philosopher at Notre Dame who holds all-time #1 ranking on MathOverflow, joins to explore the mathematics of infinity—from Cantor's groundbreaking discovery of different-sized infinities through Gödel's incompleteness theorems to Turing's undecidable Halting Problem. The episode covers ZFC set theory, the independence of the Continuum Hypothesis, surreal numbers, infinite chess with countable ordinal game values, and Hamkins' critical assessment of AI's limitations for mathematical reasoning.

Key Quotes

1. "The hotel is full. And then you could still squeeze in one more, and that breaks the traditional notion of mathematics and breaks people's brains when they try to think about infinity, I suppose. This is a property of infinity." (00:00:11)
2. "It seems to me that, we don't really have any understanding of what the physical world is as opposed to the abstract world, and it's the abstract world where existence is much more clear." (00:00:57)
3. "Mathematics has huge progress. We simply understand the mathematical ideas much, much better, you're continually improving our understanding and there's growth in knowledge." (00:01:42)

Detailed Summary

Episode Overview

This episode features Joel David Hamkins, a mathematician and philosopher specializing in set theory, the foundations of mathematics, and infinity at Notre Dame. Hamkins holds all degrees in mathematics but has concurrent appointments in both philosophy and mathematics, and ranks #1 all-time on MathOverflow with over 246,000 reputation points, with Hugh Woodin as his graduate supervisor. The interview traces the historical development of infinity from Cantor's groundbreaking discoveries through the foundational crisis in mathematics to Gödel's incompleteness theorems and Turing's solution to the Entscheidungsproblem.

Historical Background: Cantor and Infinity

Georg Cantor discovered in the late 19th century that some infinities are larger than others, a finding that fundamentally rebuilt mathematics. Cantor was deeply religious, and this discovery caused a theological crisis because infinity had traditionally been associated with God.

• Cantor faced intense opposition from Kronecker, who called him a "corrupter of youth" and attempted to block his career
• Cantor experienced mental breakdowns and spent his final years in sanatoriums, obsessed with proving the continuum hypothesis
• Russell's paradox (the set of all sets that don't contain themselves) emerged from Cantor's work and threatened to make mathematics inconsistent
• Frege's logicism project aimed to reduce all of mathematics to logical notions using the general comprehension principle
• Frege wrote in his appendix after Russell's discovery: "Hardly anything more unwelcome can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished"

Countable Infinity and Hilbert's Hotel

The episode explains countable infinity using Hilbert's Hotel thought experiment, demonstrating how infinite sets behave counterintuitively compared to finite sets. The hotel thought experiment reveals how traditional assumptions about "full" collections break down when applied to infinite collections.

• A hotel with infinitely many rooms numbered 0, 1, 2, 3... can accommodate new guests even when completely full by moving all occupants up one room (Room N → Room N+1), freeing Room 0
• For 20 new guests, the manager moves all occupants up 20 rooms, freeing the first 20 rooms
• For infinitely many new guests (the "infinite Hilbert's Bus"), the solution doubles all room numbers (Room N → 2N), occupying all even rooms and freeing all odd rooms
• A set is countable if it is equinumerous with the natural numbers—equivalent to being able to fit into Hilbert's Hotel
• The union of two countably infinite sets remains countably infinite

The Hilbert's Train: Infinity of Infinities

The episode extends the hotel analogy with Hilbert's Train, which has infinitely many cars each containing infinitely many seats, representing an infinity of infinities. This thought experiment demonstrates how countable operations on infinite collections can still yield countable results.

• Train passengers are assigned odd rooms using the formula 3^C × 5^S, where C is the car number and S is the seat number
• The prime factorization theorem ensures these values are always odd and unique
• The union of countably many countable sets remains countable, proven by enumerating elements along diagonals of an integer lattice grid using a zigzag path

Cantor's Diagonal Argument and Uncountable Infinity

Cantor proved that the set of all real numbers is uncountable—strictly larger than the natural numbers—using his famous diagonal argument. This discovery established that not all infinities are equal, with profound implications for mathematics.

• Cantor demonstrated that rational numbers (densely ordered, with fractions between any two) are only countably infinite because each rational consists of two integers
• Real numbers include both rational and irrational numbers, with transcendental numbers (like pi and e) being non-algebraic
• Cantor proved there are uncountably many transcendental numbers; most real numbers are transcendental
• The diagonal argument assumes real numbers can be listed in correspondence with natural numbers, then constructs number Z whose Nth digit differs from the Nth digit of the Nth listed number
• A complication arose from the fact that 1 has two decimal representations (1.0000... and 0.999...), which was resolved by avoiding digits 0 and 9 in the construction
• Cantor proved that for any set, the power set (collection of all subsets) is strictly larger than the original set

The Axiom of Choice and Zermelo's Theorem

In 1904, Zermelo proved that the axiom of choice implies the well-order principle, sparking intense controversy that lasted for decades. The axiom of choice states that for any collection of non-empty sets, one element can be selected from each set, even without an explicit selection rule.

• Historians note that no mathematical theorem in history was argued about so publicly and vociferously as Zermelo's well-order theorem
• Mathematicians who publicly objected to the axiom of choice were often found to be implicitly using it in their own arguments
• Russell illustrated the axiom using a thought experiment: a butler can easily pick one shoe from each pair (distinguishable by left/right) but cannot apply a rule to pick one sock from indistinguishable pairs
• ZFC consists of nine axioms: Extensionality, Empty Set, Pairing, Union, Power Set, Infinity, Separation, Replacement, Regularity, and Choice
• Hilbert famously defended set theory: "No one shall cast us from the paradise that Cantor has created for us"

Gödel's Incompleteness Theorems

Gödel proved that no computably axiomatizable theory including sufficient arithmetic can answer all mathematical questions; every such theory will be incomplete. These theorems represent a decisive refutation of Hilbert's program.

• The second incompleteness theorem states that no such theory can prove its own consistency
• Mathematical reality involves two features: even our best theories will always have unanswerable questions due to independence, and we cannot have truly convincing proofs that our theories are free from contradiction
• A self-consistency proof is not trustworthy because even an inconsistent theory would prove its own consistency
• Gödel's incompleteness theorems defeated both goals of Hilbert's program completely
• Hilbert declared in his retirement address: "Wir müssen wissen, wir werden wissen" (We must know, we will know)

Turing, the Halting Problem, and Computability

Turing addressed the provability decision problem (Hilbert-Ackermann Entscheidungsproblem) in his 1936 paper and proved that the Halting Problem is computably undecidable. The Halting Problem asks whether there exists a computable procedure that correctly answers whether any given program will halt on all inputs.

• The Halting Problem proof uses diagonalization: program Q is designed so that when given any program P, Q halts if and only if P does not halt on P
• Asking what Q does on input Q creates a contradiction: Q halts on Q if and only if Q does not halt on Q
• The speaker considers this halting-problem-based proof of Gödel's theorem the simplest available, requiring no Gödel sentence
• For the Halting Problem, "yes" answers are trivially obtained by running programs, but "no" answers require deep insight into program behavior
• The question of whether a cell will ever become alive in Conway's Game of Life is computably undecidable and equivalent to the Halting Problem

The Halting Problem Black Hole

Alexey Myasnikov asked whether the halting problem has a "black hole"—a decision problem difficult in worst case but easy outside a tiny region. A theorem was proved establishing a black hole for the halting problem with surprising quantitative results.

• Approximately 13.5% of programs never halt because they lack any halt instruction
• The asymptotic density of programs for which the halting problem can be decided goes to 100%
• The proof strategy was to pile up "stupid reasons" for non-halting (like the head falling off the tape when moving left from the leftmost cell) until exceeding 50%
• Pólya's Recurrence Theorem showing one-dimensional random walks return to start was used, causing half to fall off the tape
• Before Gödel, mathematicians were "totally sloppy" about distinguishing truth from proof; the distinction between truth (semantic) and proof (syntactic) was not clearly understood before Gödel and Tarski

The Continuum Hypothesis and Its Independence

Cantor spent his entire life trying to prove or disprove the Continuum Hypothesis (CH), which asserts no infinity exists between the natural numbers and the real numbers. Hilbert listed CH as Problem #1 among his 23 problems at his famous 1900 address.

• In 1938, Gödel proved that if ZF is consistent, then so is ZFC plus CH, using the constructible universe (Gödel's L), showing CH cannot be refuted but not that it is true
• In 1963, Paul Cohen invented forcing and proved that if there's a model of set theory, there's also a model where CH is false
• Forcing builds alternative set-theoretic universes where CH can be "turned on and off like a light switch"
• Thousands of independence results exist: practically every non-trivial statement about infinite cardinalities is very likely to be independent of ZFC
• The Cantor's Bendixson theorem established that every closed set of real numbers is either countable or equinumerous with the entire real line, never strictly in between

Universe View vs. Multiverse View

The universe view holds there is one true set-theoretic reality with definite answers, while the multiverse view holds there are multiple realities with differing truths. This philosophical disagreement has profound implications for how mathematicians understand mathematical truth.

• The multiverse view suggests the fundamental nature of set-theoretic truth has a plural character rather than a singular meaning
• Hugh Woodin is pursuing the universe view with his theory of ultimate L, striving to find the nature of the one true set-theoretic universe
• Hamkins worked with Gunter Fuchs and Jonas Riets on set theoretic geology, which studies how to undo forcing by finding the bedrock model from which a set-theoretic universe originated
• Set theoretic geology originated from the pluralist perspective but is now being used by universe view researchers to discover the one true universe's mantle

Philosophy of Mathematics

Hamkins identifies as a mathematical realist who believes abstract objects have real existence in a Platonic realm. Structuralism is presented as an anti-essentialist position emphasizing that mathematical objects matter for how they function in structures, not their intrinsic nature.

• Hamkins argues that we understand mathematical and abstract existence better than the nature of physical reality, which remains a profound mystery
• Structuralists argue structures are equivalent up to isomorphism
• The episode revisits Frege's Julius Caesar problem: whether the Cantor-Hume principle can distinguish numbers from non-numbers, with structuralists controversially arguing Caesar could play the role of 17 in an isomorphic number system
• Mathematics has made huge progress over the past century while philosophy has eternal questions that have persisted for thousands of years
• Hamkins identifies transfinite ordinals as the most beautiful idea in mathematics and the distinction between truth and proof as the most beautiful idea in philosophy

Surreal Numbers

John Conway introduced the surreal number system, which unifies all other number systems: natural numbers, integers, rational numbers, real numbers, ordinals, and infinitesimals. Surreal numbers are generated from nothing by a single rule applied in transfinite stages.

• Divide existing numbers into a left set and right set where all left elements are less than all right elements, then create a new number fitting in that gap
• Zero is the first surreal number created (the "surreal genesis"), followed by one, minus one, then at the next stage: two, minus two, 1/2, and minus 1/2
• On day omega (the first infinite stage), all real numbers are born because they fill gaps between previously born dyadic rationals
• Also born on day omega are ordinal omega, minus omega, and epsilon (the first infinitesimal greater than zero)
• Surreal numbers are not a set but a proper class because they contain all ordinal numbers
• Conway's greatest disappointment was that surreal numbers never achieved the unifying status he had hoped for across mathematics and science

Infinite Chess

Infinite chess is played on a board extending infinitely in all four directions; games are not played from standard starting positions but from complicated positions with many pieces already on the board. In infinite chess, games are draws by infinite play, and a player can only win by achieving checkmate at a finite stage.

• The speaker's interest originated from a MathOverflow question by Noam Elkies
• He collaborated with Corey Evans, a US national master chess player and philosophy professor of law, who provided corrections based on chess rules
• The first paper established positions with values omega, omega-squared, and omega-cubed
• A follow-up with Norman Perlmutter produced a position with game value omega to the 4th
• It is now known that every countable ordinal arises as the game value of a position in infinite chess
• Pawns cannot promote in infinite chess because there is no edge to the board; the threefold repetition rule is eliminated

Mathematical Style, Collaboration, and Motivation

The speaker prefers simple, clear, easy-to-understand arguments that prove surprising results, viewing complicated arguments with skepticism. Mathematical ideas are often "in the air" among mathematicians, with disparate mathematicians independently proving similar results at approximately the same time.

• The speaker has approximately 100 collaborators and co-authors, contrasting with Andrew Wiles who spent seven years grinding at Fermat's Last Theorem in isolation
• Grisha Perelman declined both the Fields Medal and Millennium Prize for solving the Poincaré conjecture, stating "If the proof is correct, then no other recognition is needed"
• The speaker argues the fundamental motivation for great mathematicians is love of the art itself, not prizes

AI in Mathematics

Hamkins finds current AI systems provide zero helpfulness for mathematical reasoning, describing typical interactions as giving garbage answers that are not mathematically correct. He raises concerns about AI producing mathematical arguments that superficially mimic mathematical reasoning without genuine mathematical understanding.

• Current LLMs are designed to produce arguments that sound like proofs rather than arguments that are actually valid proofs, which is a fundamentally different and dangerous motivation
• This makes AI a dangerous source of error for non-experts who may not recognize the flaws
• The speaker recommends using AI for mathematical arguments only when tied to formal proof verification systems like Lean rather than relying on chat-based LLMs
• He acknowledges that LLMs can provide value through unexpected cross-field connections and inspiration
• Effective use of LLMs requires providing comprehensive, structured information from one's body of work to make the system a better collaborator

About Joel David Hamkins

Joel David Hamkins holds all degrees in mathematics but has become a philosopher over the years because his mathematical work engaged with philosophical issues. He has held academic positions at the Graduate Center in New York, Oxford University, and currently at Notre Dame.

• His wife Barbara is also a philosopher at Notre Dame
• Transfinite ordinals form the foundation for the Cantor-Bendixson theorem, the V hierarchy, Gödel's constructible universe, and Zermelo's proof of the well-order principle using the axiom of choice
• The progression of transfinite ordinals includes omega, omega+1, omega+2, up to omega squared (the limit of omega times n for all n), with counting never ending

Transcript: Download plain text