Infinity, Paradoxes, Gödel Incompleteness & the Mathematical Multiverse | Lex Fridman Podcast #488
These notes were generated by AI and may contain inaccuracies.
Joel David Hamkins is a mathematician and philosopher specializing in set theory, the foundation of mathematics, and the nature of infinity. He is the number one highest rated user on MathOverflow, a site like StackOverflow for research mathematicians. Author of books including Proof in the Art of Mathematics and Lectures on the Philosophy of Mathematics. His blog is infinitelymore.xyz. Conversation covers foundations of modern mathematics, infinity, nature of reality, truth, and mathematical paradoxes.
Some infinities are bigger than others, an idea from Cantor at the end of the 19th century that broke and rebuilt mathematics. Reasons for devastation:
- Theological crisis: infinity associated with God; how multiple infinities?
- Mathematical civil war: Kronecker called Cantor a corrupter of youth and blocked his career.
- Paradoxes like Russell's paradox: set of all sets that don't contain themselves, threatening mathematics' consistency.
- Cantor's mental breakdown: spent final years in sanatoriums, obsessed with proving the continuum hypothesis.
Aristotle emphasized potential infinity over actual infinity. Archimedes' method of exhaustion carved regions into triangles to understand area. Mathematicians were potentialists, viewing actual infinity as incoherent. Galileo in The Dialogue of Two New Sciences anticipated Cantor but ended in confusion.
Galileo paradox: perfect squares (0,1,4,9,16,25,...) can be put in one-to-one correspondence with natural numbers (associate each with its square), suggesting same number, yet gaps imply fewer squares. Also, line segments of different lengths, concentric circles, matched point-to-point via fans or rays, seem equinumerous despite size differences.
Cantor-Hume principle: collections are equinumerous if there's a one-to-one correspondence, finite or infinite. Tension with Euclid's principle: whole greater than part. Cantor resolved by showing different infinite sizes.
Cantor proved real numbers uncountable, larger than countable infinity.
Hilbert's Hotel: infinitely many rooms (0,1,2,...), all full. New guest arrives: move everyone from room N to N+1, freeing room 0. Adding one doesn't enlarge. For 20 guests: move to N+20. Violates Euclid's principle.
Hilbert's bus: countably infinite seats (0,1,2,...). Move guests to even rooms (2N), free odds for bus (put bus seat S in 2S+1).
Countable set: equinumerous with natural numbers, fits in Hilbert's Hotel. Union of two countables is countable.
Hilbert's train: countably infinite cars, each with countably infinite seats. Move hotel to evens (2N). For train (car C, seat S): assign room 3^C * 5^S (odd, unique by prime factorization). Union of countably many countables is countable.
Integer lattice (pairs of naturals) like train: zigzag diagonally to enumerate all points, showing countability.
Rational numbers (p/q, q≠0): countable, like pairs (p,q) via 3^p * 5^q.
Real numbers: all points on number line, rationals + irrationals. Include algebraic numbers (roots of integer polynomials, e.g., √2, cube root of 5). Transcendental numbers: not algebraic (e.g., Liouville constant, π, e). Liouville proved transcendentals exist; Cantor showed uncountably many; most reals transcendental.
Proof that every natural number is interesting:
- 0: additive identity.
- 1: multiplicative identity.
- 2: first prime. General principle to prove all are interesting.
Suppose, toward contradiction, that there were some boring numbers. If there was an uninteresting number, then there would have to be a smallest uninteresting number. But that's a contradiction, because the smallest uninteresting number is a super interesting property to have. Therefore, there cannot be any boring numbers. That doesn't say anything about the transcendental numbers, about the real numbers that you just proved from just four natural numbers.
Cantor wants to prove that the infinity of the real numbers is different and strictly larger than the infinity of the natural numbers. Natural numbers are the numbers that start with zero and add one successively: zero, one, two, three, and so on. Real numbers are the numbers that come from the number line, including all the integers and the rationals and the algebraic numbers and the transcendental numbers and all of those numbers altogether.
Since the natural numbers are included in the real numbers, we know that the real numbers are at least as large as the natural numbers. The claim is that it's strictly larger. Suppose that it wasn't strictly larger, so they would have the same size. To have the same size means by definition that there's a one-to-one correspondence between them.
Suppose that the real numbers can be put into one-to-one correspondence with the natural numbers. For every natural number N, we have a real number, R sub N, the Nth real number on the list. Our assumption allows us to think of the real numbers as having been placed on a list: R1, R2, and so on.
Define the number Z: the integer part is going to be a zero, then a decimal place, and then specify the digits of this number Z: D1, D2, D3, and so on. The Nth digit after the decimal point of Z is different from the Nth digit of the Nth number on the list. To specify the Nth digit of Z, go to the Nth number on the list, R sub N, look at its Nth digit after the decimal point, and make sure that the digit in Z is different from it. Make it different in a way that never uses the digits zero or nine.
This forms a kind of diagonal going down and to the right, so this argument is called the diagonal argument because we're looking at the Nth digit of the Nth number. Z is different from R1 because the first digit after the decimal point of Z is different from the first digit of R1. The second digit of Z is different from the second digit of R2, and so on. The Nth digit of Z is different from the Nth digit of R sub N for every N. Therefore, Z is not equal to any of these numbers R sub N.
That's a contradiction because we had assumed that we had every real number on the list, but here is a real number Z that's not on the list. It's a proof by construction. Given a list of numbers, Cantor gives a specific means of constructing a real number that's not on the list.
Some real numbers have more than one decimal representation, for example, the number one can be written as 1.0000 forever or 0.9999 forever. By avoiding zeros and nines, the proof still works because the only case where that phenomenon occurs is when the number is eventually zero or eventually nine. Since Z never has zeros or nines, it has a unique representation and isn't equal to those numbers.
This is one of the initial main results in set theory, profound and amazing, the beginning point of so many later arguments. The diagonalization idea has proved to be an extremely fruitful proof method, and almost every major result in mathematical logic uses diagonalization in an abstract way, including Russell's paradox, the halting problem, and the recursion theorem.
The infinity crisis led to rebuilding mathematics: set theory became the foundation of mathematics, all mathematics could be built from sets, giving math its first truly rigorous foundation. The paradoxes forced mathematicians to develop ZFC and other axiomatic systems, and mathematical logic emerged. Gödel, Turing, and others created entire new fields.
Set theory has two roles: its own subject of mathematics with its own problems, questions, answers, and proof methods, about transfinite recursive constructions or well-founded definitions and constructions. It also serves a foundational role, providing a way to think of a collection of things as one thing. A set is a collection of things, but the set itself is one abstract thing, like a bag of objects.
Axioms are facts that we assume are true, based on which we build the ideas of mathematics. The history of the current set theory axioms, known as the Zermelo-Fraenkel axioms, came out in the early 20th century. In 1904, Zermelo offered a proof that the axiom of choice implies the well-order principle. This was extremely controversial at the time, with no axioms yet. Cantor was not working in an axiomatic framework.
Zermelo was pressed to produce the theory in which his argument could be formalized, leading to Zermelo set theory. The axiom of choice states that for any collection of non-empty sets, it is possible to select exactly one element from each set, even if no explicit rule to make the choices is given. This allows the construction of a new set containing one element from each original set, even in cases where the collection is infinite or where there is no natural way to specify a selection rule.
The axiom of choice is completely obvious: if you have a bunch of sets, there's a way of picking an element from each of them. There's a function that, when applied to any one of those sets, gives an element of that set. It's called the axiom of choice, anthropomorphizing the idea, but it's just asserting the existence of such a function, even if you can't specify a rule or procedure.
ZFC is Zermelo-Fraenkel set theory with the axiom of choice, the standard foundation of modern mathematics. Huge parts of mathematics pay attention to whether the axiom of choice is used and work without it or with weakened forms.
Russell's description: a rich person with an infinite closet has infinitely many pairs of shoes and tells his butler to give him one shoe from each pair. The butler can do this easily by always picking the left shoe or some describable rule. For those cases, you don't need the axiom of choice.
But for an infinite collection of indistinguishable socks, where socks in each pair match and are indiscernible, the butler has no rule for which sock to pick from each pair. That's when you need the axiom of choice to assert there is such a function, even if not defined by a rule.
In mathematical ontology, not every way of choosing has to be defined by a rule. Mathematical reality is rich with objects, including all kinds of functions and ways of choosing. In arguments, assume a choice function exists because there is one.
The philosophical difference: appealing to the axiom of choice admits objects may not be constructive; you can't necessarily say specific things about them. If you have a constructive attitude, thinking mathematical claims are only warranted with explicit procedures, you may deny the axiom of choice.
ZFC axioms include: Axiom of Extensionality, Axiom of Empty Set, Axiom of Pairing, Axiom of Union, Axiom of Power Set, Axiom of Infinity, Axiom of Separation, Axiom of Replacement, Axiom of Regularity, and Axiom of Choice.
Zermelo introduced most of these in 1908 as Zermelo set theory to formalize his proof from the axiom of choice to the well-order principle. Axiom of Extensionality: if two sets have the same members, then they're equal; sets consist of their collection of members, nothing else.
- Axiom of Empty Set: there exists a set with no elements.
- Axiom of Pairing: for any two sets, there's a set that contains exactly those two sets as elements.
- Axiom of Union: for any set, there's a set that contains exactly the elements of the elements of that set.
- Axiom of Power Set: for any set, there's a set whose elements are exactly the subsets of the original set.
- Axiom of Infinity: there exists an infinite set, typically containing the empty set and closed under adding one more element.
Zermelo's well-order theorem was argued about more publicly and vociferously than any previous mathematical theorem. People were suspicious because no one could imagine a well-ordering of the real numbers. Zermelo seemed to prove an obvious untruth from reasonable principles.
Objectors were found implicitly using the axiom of choice in their own arguments. It's natural and easy to use accidentally. In the early 20th century, it was important because of worries about consistency due to antinomies. With Gödel and Cohen's results, the axiom of choice won't be the source of inconsistency; if inconsistent with it, already inconsistent without it.
Consistency means it is impossible to derive a contradiction from the axioms of the theory; a consistent theory is one for which you cannot prove a contradiction.
Cantor proved a more general fact: for any set whatsoever, the power set of that set (set containing all subsets of the original set) is a strictly larger set; they are not equinumerous. There's always at least as many subsets as elements, since for any element you can make the singleton subset.
Suppose X and the power set of X have the same size. Associate to every individual of X a subset. Define a new set D, the subset of X containing all individuals that are not in their associated set.
D is a perfectly good subset, so by equinumerosity, it is attached to some individual, say Diana. Is Diana an element of D? If Diana is in D, then she is in her set, but D is the set of those not in their set, so she shouldn't be. If she isn't in D, then she isn't in her set, so she should be in D. Contradiction. Therefore, the number of subsets is always greater than the number of elements for any set.
Anthropomorphized: for any collection of people, you can form more committees than there are people, even infinitely many. A committee is a list of members: two-person committees, one-person committees, the universal committee, the empty committee.
Suppose not, then associate every committee to a person in a one-to-one way, not necessarily that the person is on the committee named after them.
Committee D consists of all people not on the committee named after them. It has to be named after someone, call that person Daniella. Is Daniella on committee D? If she is, she shouldn't be, because it's the committee of people not on their own committee. If she isn't, she should be. Contradiction.
Consider all possible fruit salads from a collection of fruits (apples, oranges, grapes, etc.), even infinitely many fruits. Prove there are more fruit salads than fruits. Assume a one-to-one correspondence naming each salad after a fruit. Form the diagonal salad: all fruits not in the salad named after them. This is a valid salad (could be empty diet salad, universal salad, or partial). It must be named after some fruit, say durian. Is durian in the durian salad? If yes, it shouldn't be; if no, it should be. Contradiction.
All these arguments (committee, fruit salads) are Cantor's proof that the power set of any set is bigger than the set. Same logic in Russell's paradox: the class of all sets that are not elements of themselves leads to contradiction (it would be an element of itself iff not). Thus, no class of all sets; there are more collections of sets than sets. Speaker calls it Russell's theorem: there's no universal set. Now absorbed into set theory understanding.
Frege worked on logicism: reduce all mathematics to logic. His general comprehension principle: for any property, form the set of objects with that property. Russell wrote Frege a letter showing contradiction: set of all sets not members of themselves can't exist (element of itself iff not). Letter arrived as Frege's work was at the publishers, devastating after years of work.
Frege's appendix: "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. This is the position into which I was put by a letter from Mr. Bertrand Russell as the printing of this volume was nearing completion."
Heartbreaking for Frege's dream of constructing mathematics from logic.
Logicism continued (neologicists today). Goals fulfilled in ZFC set theory as foundation: ZFC principles (including axiom of choice, axiom of infinity) are logical in character, about abstract set formation. Set theory foundations mean mathematics founded on logic.
Profound development; birth of sophisticated mathematical logic.
Post-Russell paradox, Burali-Forti paradox: minefield of paradoxes. Hilbert: "No one shall cast us from the paradise that Cantor has created for us." Wanted trustworthy set theory foundations.
Hilbert's goals:
- Strong theory (set theory) answers all questions: "Wir müssen wissen, wir werden wissen" (We must know, we will know).
- Prove via weak, purely finitary theory that strong theory is consistent (safe).
Formalism: Proofs as finite sequences of symbols following logical rules (syntactic, finitistic objects), divorced from meaning (which may involve infinities).
Finitary: finite strings of symbols; argue about them directly. Example: Peano arithmetic (first-order theory of natural numbers: axioms for 0/1, successor, addition, multiplication, induction). Contentious if truly finitary (strong induction), but formalizes classical number theory (primes, factorization).
Finitary theory proves strong theory consistent. Theorem-enumeration machine spits out all proofs/theorems systematically (computable). Answer questions by waiting for yes/no. Mathematics as rote computation, no creativity.
First incompleteness theorem: No computably axiomatizable theory (with arithmetic) answers all questions; every such theory incomplete.
Second incompleteness theorem: No such theory proves its own consistency (even strong theory can't).
Decisive refutation: no complete theory; constant consistency worries. Mathematics: independence pervasive; rote computation impossible.
Inconsistent theory proves own consistency (like untrustworthy salesman).
Theory (technical term): set of sentences in formal language (axiomatic system); includes axioms and consequences (computably enumerable if axioms computable list, but not decidable).
Pre-Gödel/Tarski, sloppy distinction (e.g., Bourbaki conflated: true = provable). Truth semantic (reality); provability syntactic (proof). Core to mathematical logic.
Truth relates to the nature of mathematical reality, not just physical reality. A statement is true in a specific mathematical structure, such as the real field, a group, or a graph with vertices and edges. Alfred Tarski provided the disquotational theory of truth: the sentence "Snow is white" is true if and only if snow is white. Truth is a property of an assertion; syntactically, the quoted sentence is true iff its content holds. Removing quotation marks (disquotation) defines truth formally in a structure for a formal language with atomic statements about objects and relations, built using logical connectives (and, or, implies, not) and quantifiers.
Truth of complex statements is defined recursively by induction:
- The structure satisfies φ and ψ iff it satisfies φ and satisfies ψ (disquotation shifts 'and' from syntax to condition). This extends to all connectives and quantifiers, yielding a Tarski recursive definition of truth. Truth is structure-relative; e.g., in the standard model of arithmetic (natural numbers with + , ×, 0, 1, <), we check if a statement holds via this definition.
Proof is a sequence of sentences in the formal language following proof system rules (Hilbert-style proof theory). Examples: from A and A implies B, deduce B via modus ponens (implication elimination). Many formal proof systems exist, all sound (preserve truth: true premises imply true conclusion in any structure) and complete (every logical consequence has a proof: if premises true imply conclusion true, then provable).
A third key property: computable decidability—check if a sequence is a proof. Classical systems are sound, complete, and decidable, allowing adjudication of proof claims (contra Fermat's uncheckable margin proof).
Incompleteness theorem: No computable list of axioms (consistent theory) for arithmetic (natural numbers, +, ×, 0, 1, <) proves all true statements. Arithmetic encodes all finite mathematics via coding. Hilbert sought a complete theory proving all and only truths, but Gödel proved it impossible: if consistent, some true statements are unprovable and unrefutable (independent).
This reveals mathematical reality's nature—eye-opening, not traumatic. We cannot axiomatize all truths computably; move forward knowing this limit.
In general, provability problem (does theory prove statement?) is undecidable (Hilbert-Ackermann Entscheidungsproblem, title of Turing's 1936 paper). By Gödel's completeness theorem (not incompleteness), provability ≡ logical consequence, and it's undecidable, equivalent to Halting Problem.
Halting Problem: Given a program (or program + input), does it halt? Undecidable—no computable procedure answers all instances correctly. For single cases, run it: halts → yes; but non-halting requires waiting forever (e.g., run 1000 years, still no proof of non-halting without insight).
Proof by diagonal contradiction (style of Russell, Cantor, Gödel): Assume halting oracle exists. Build Q(P):
- Query oracle: does P halt on P?
- If yes, Q loops infinitely (non-halts).
- If no, Q halts. Thus, Q on Q opposes itself: halts iff non-halts—contradiction. Hence, no such oracle.
Assume computable axiomatization of all true elementary mathematics (arithmetic encodes Turing machines, finite combinatorics). Build theorem enumeration machine: generates all/only theorems.
Solve Halting: for program P on input, wait for theorem "P halts" or "P non-halts" (complete theory enumerates all truths). Contradicts Halting undecidability. Thus, no complete computable theory of arithmetic—proves Gödel's theorem (no need for Gödel sentence).
In Proofs and the Art of Mathematics (from teaching proofwriting class for post-calculus students transitioning to higher math), focus on compelling theorems with elementary proofs showcasing styles, not dull mechanics (e.g., assume hypothesis for implications).
Book dedicated: > "to my students, may all their theorems be true, proved by elegant arguments that flow effortlessly from hypothesis to conclusion while revealing fantastical mathematical beauty."
In a group (circle of friends), each points arbitrarily (multiple, self, none). Can everyone be more pointed-at than pointing? (Twitter analog: more followers than following; no self-follow.)
Favorite proof (money analogy, anthropomorphizing): Assume possible. Give $1 to each pointed-at person. Everyone gains net money (e.g., $10 in, $7 out). Impossible—group cannot profit by internal trades (builds on human intuition about money/resources; mathematically, sum in-degree > sum out-degree impossible in finite directed graph).
Anthropomorphize math objects (as people/agents) for intuition. Proof power: non-obvious becomes obvious over time, guiding to truth.
Infinite case: Fails. With countably infinite people (each 1 dollar), arrange passing so each ends with countably infinite dollars (Hilbert Hotel/Train: Nth car gives to Nth room; each pays 1, receives ∞).
Philosophy of mathematics addresses the existence of mathematical objects, including infinity, similar to questioning the existence of the number five. This is a fundamental question of mathematical ontology. Various positions exist on the existence of abstract objects. Some desire to reduce mathematical existence to physical objects like tables, chairs, and rocks, but this is backward because physical existence lacks a clear account.
We experience the physical world but have no satisfactory account of physical existence. Example: Detailed description of a steam locomotive—engineering, weight, gear linkages, schematics—yet defining its physical existence beyond imagination is impossible without circularity. Physical existence is a profound mystery, increasingly so with physics advances.
Newtonian physics pictured objects as billiard balls or infinitely divisible. Atomic theory upset this; atoms split into electrons, protons, neutrons. Further, these consist of quarks and leptons, existing as wave functions in probability clouds. No clarifying account of an apple's physical existence exists.
Abstract existence is clearer: empty set as predicate never true; singleton of the empty set. It becomes clearer with depth, unlike physical existence.
We anthropomorphize physical objects, mistaking poking them for understanding, ignoring quantum mechanics. Distinction: numerals (representations on page) vs. numbers. Numbers exist as real; speaker holds realism in mathematics, with account via logical properties.
Number four as size of set with four elements, but enters structuralism: Emphasizes function in mathematical structure, not substance or essence. Care about structures up to isomorphism—exact copies with different elements are equivalent mathematically. Substance of individuals irrelevant to properties.
Asking "What is the number four really?" is anti-structuralist. In natural numbers (0, 1, 2, 3, 4, ...), replace four with water bottle; isomorphic, irrelevant for math. Numbers point to underlying structure; objects meaningful via interactions in system.
Frege's logicist program reduced math to logic, using Cantor-Hume principle: Sets equinumerous iff same number of elements. Provides identity criteria (equinumerous sets same number) but not criteria for what is a number—Julius Caesar problem. Structuralists reject essence; replace 17 with Julius Caesar in system, now it's 17; question irrelevant to math.
More concrete statements possible about mathematical object existence than physical. Speaker lives in Platonic realm, understands it better; physical universe mysterious. Realism: Abstract objects have real existence, independent of place/time.
Physical reality experiential (birthday parties, martinis, bicycles), not understood. Mathematical existence better grasped. Physics may progress, but physical existence account unimaginable.
Mathematics has huge progress: Better understanding of infinity now than 100 years ago, continually improving. Fields shift to harder questions. Philosophy has less progress; eternal questions persist, some argue value in asking, not answering.
Mathematical progress continues; in 1000 years, unrecognizable to us, yet communicable to ancients like Archimedes.
Speaker #1 all-time on MathOverflow with >246,000 reputation points since 2009. Great pleasure, learned much. Answers interesting questions across math, initially logic (few others), then logic-adjacent in group theory, analysis. Learns context to answer on axiom of choice, continuum hypothesis; grew as mathematician.
Examples of answered questions:
- Reasonable sounding statements independent of ZFC
- Most misleading alternate definitions in taught mathematics
- Is university analysis of definable numbers?
- Solutions to continuum hypothesis
- Most unintuitive axiom of choice application
- Non-trivial theorems with trivial proofs
- Reductio ad absurdum or contrapositive?
- What is a chess piece mathematically? (Worked on infinite chess)
- Has philosophy clarified mathematics?
- Why two theorems when one implies the other?
- Historical answer on continuum hypothesis
Continuum hypothesis (CH): No infinity between natural numbers and reals. Cantor proved reals' infinity strictly larger than naturals', naturally asked if anything between. Obsessed, struggled lifelong; seemed to break him.
Many real sets (Cantor sets, Vitali sets, closed sets), but all definable/observable ones either countable (equinumerous to naturals) or equinumerous to reals—never strictly between.
CH holds for open sets: Non-trivial open intervals equinumerous to reals via arctangent. Holds for closed sets via Cantor-Bendixson theorem (Cantor invented ordinals for this).
Open set: Every point surrounded by interval (equinumerous to line). Closed set: Complement of open; includes intervals, Cantor set (remove middle thirds iteratively), complements of scattered open intervals. Can have isolated points, convergent sequences, etc.
Cantor set constructed by iteratively removing middle thirds from interval.
Cantor proved with closed sets that no set has intermediate cardinality: every closed set is either countable or equinumerous with the whole real line. Cantor's program for solving the Continuum Hypothesis (CH) involved working up hierarchies of sets. He started with open and closed sets, then Borel sets, which are combinations of open and closed sets forming a vast hierarchy of Borel complexity. The CH has been proved for Borel sets.
Beyond Borel sets, there is a hierarchy of complexity for sets of real numbers. Cantor's idea was to prove CH for increasingly complicated sets based on understanding earlier cases, carried out remarkably over the past 120 years. Higher levels require large cardinal assumptions. The projective hierarchy, sets defined using quantifiers over real numbers, sits atop the Borel hierarchy. With enough large cardinals, projective sets are either countable or equinumerous with the real line.
This fulfills Cantor's vision but cannot fully succeed because the hierarchy does not include all sets of real numbers; some transcend it completely, especially given independence results.
The Continuum Hypothesis is independent of the ZFC axioms of set theory. ZFC originated with Zermelo's 1908 axioms for his well-ordering theorem using the axiom of choice, later expanded with replacement and foundation axioms to Zermelo-Fraenkel. Zermelo's original theory (Z) allowed ur-elements (atoms), non-set objects; modern ZFC (ZFCU or ZFA without atoms) omits them due to structuralism, as structures with atoms are isomorphic to those without, making the theory more elegant.
ZFC expresses main principles of sets and set existence. CH, posed by Cantor in the late 19th century, remained open until 1938. It was Hilbert's number one problem in his 1900 list of 23 problems.
Hilbert's list guided 20th-century mathematics, though he likely saw it as important problems rather than a research blueprint. Hilbert viewed set theory as foundational, quoting "No one will cast us from the paradise that Cantor has created for us." CH is fundamental for mathematics' unity: before set theory, fields like algebra, analysis, topology had separate axioms, yet proofs borrowed across (e.g., fundamental theorem of algebra uses topology). Set theory provides a uniform foundation resolving this.
Alternative foundations now exist (category theory, type theory, univalent foundations), but set theory excels in meta-mathematical analysis despite limitations like computer proofs.
Hilbert's 10th problem sought an algorithm for Diophantine equations (polynomials in several variables over integers). Solved negatively: undecidable, like the halting problem—no computable procedure exists.
Cantor posed CH late 19th century; Hilbert highlighted it 1900; open until 1938. Kurt Gödel proved half: if ZFC is consistent, then ZFC + CH is consistent via the constructible universe (L), where axiom of choice and CH hold. Beautiful argument constructs an alternative mathematical reality.
Gödel showed CH cannot be refuted (if ZF consistent, then ZFC + CH consistent), but not that CH is true.
In 1963, Paul Cohen's forcing proved the other half: if a model of ZFC exists, then a model where CH fails (forcing extension). Forcing builds alternative realities, allowing travel/expansion/alteration between mathematical universes.
Thousands of independence results: practically every non-trivial infinite combinatorics statement is independent of ZFC. Universe view (monist): ZFC weak; seek stronger theory for the true set-theoretic reality with definite answers.
Independence: cannot prove or disprove within ZFC.
Set theorists celebrate independents as "carving nature at its joints," revealing dichotomies—worlds where true vs. false.
Incompleteness theorem: any theory has unprovable truths; Gödel's second implies consistency-strength hierarchy—towers of theories where each proves prior consistency unprovable in previous.
Large cardinals instantiate this: unending hierarchy of big infinities with increasing strength, fulfilling Gödel's prediction (not self-referential but existential).
Yet CH independent of all known large cardinals; hierarchy never settles it.
Multiverse view (pluralist): no unique reality; decades of forcing produce alternative universes differing on fundamentals (e.g., CH true/false like a light switch in closely related worlds). Pluralist truth: no singular meaning, but choice among universes.
Universe vs. multiverse views agree on theorems; differ philosophically on direction.
Newton/Leibniz calculus used suspect infinitesimals (mocked by Berkeley as "ghosts of departed quantities"); rigorous only in 1950s via non-standard analysis (Robinson). Yet they proved fundamental theorems with poor foundations—showing foundations not prerequisite for insights.
Philosophical perspective guides questions: universe view seeks one true universe (e.g., Woodin's ultimate L; Hamkins' advisor). Pluralist view explores interactions (e.g., set-theoretic potentialism—universes potentialist despite containing infinities.
Set theoretic universes are potentialist, allowing for more sets by forcing or extending upward. Research explores the nature of this realm of set theoretic universes. With Benedikt Lowe, proved theorems on the modal logic of forcing and set theoretic potentialism under end extensions. With Gunter Fuchs and PhD student Jonas Reitz, developed set theoretic geology, studying the metaphor of forcing backwards. Jonas wanted to undo forcing, going from the forcing extension back to the ground model. Initially skeptical, but pursued it, defining bedrock models and ground models to reverse engineer forcing origins.
This pluralist-inspired work fits the universe view, discovering the set theoretic mantle. Historically, this geology program from pluralism was adopted by universe view researchers.
Proofs in a forcing extension can imply truths in the ground model. To prove something in the current universe, construct a forcing extension, use its features to deduce ground model truths, then discard the extension.
Analogy to early complex numbers: solving real algebraic equations symbolically, passing through square roots of negatives (nonsense), with imaginaries canceling to yield real solutions like 3 + √17, verifiable in reals. Similarly, forcing takes you to an imaginary world, argues there, and returns consequences to the ground model.
Surreal numbers, introduced by John Conway, unify all number systems: extends naturals, integers, rationals, reals, ordinals, and infinitesimals. A proper class containing all ordinals, generated from nothing by a single rule in transfinite stages.
At each stage, divide existing numbers into left set L and right set R (everything in L < everything in R), create new surreal born in the gap between L and R.
- Start with empty L and empty R (vacuous truth), birth 0 (surreal genesis, Big Bang of numbers).
- With 0: L={0}, R=∅ births 1; L=∅, R={0} births -1.
- Next: birth -2, -1/2, 1/2, 2 in gaps.
- Finite stages birth dyadic rationals (denominators powers of 2).
- Day ω (first infinite): all real numbers (filling rational gaps), ω (first > all finites), -ω (< all finites), ε (infinitesimal: 0 < ε < all positive rationals).
- Continues transinfinitely: ω+1, ω+2, etc.
Arithmetic (addition, multiplication) defined recursively, forming an ordered field: commutative, distributive, reciprocals for non-zero, subtraction, division. Also real closed field: square roots, every odd-degree polynomial has a root (like reals, due to opposite infinity behaviors).
Non-standard model of reals with infinitesimals for non-standard calculus (Robinson's theory). Fundamentally discontinuous: no least upper bound property for non-trivial subsets, no convergent sequences, limits-based calculus fails. Infinitesimal methods work instead.
Conway's greatest disappointment: surreal numbers didn't become a fundamental system for math/science despite unifying power, non-set analysis, calculus, ordinals. Thousands study it; experts like Philip Ehrlich note Conway's game-like treatment may have undermined seriousness. Hamkins writes essays on Substack Infinitely More, finds it profound.
Conway's Game of Life (cellular automata) explores computably undecidable questions: whether a cell ever becomes alive is undecidable, equivalent to Halting Problem. Semi-decidable: if it happens, finite simulation shows it; non-halting requires undecidability proof. Visualizations show mini-civilizations: some die quickly, predictable/boring, others richly complex.
Rice's Theorem: no thorough understanding of program behavior from code alone; learn by running it.
Random programs: for Turing machines (one-way infinite tape, 0s/1s, halt state), halting problem has a black hole (Alexey Myasnikov): decidable for almost all instances (asymptotic density 1). Procedure decides easily for programs in a large collection (proportion →100% as states grow).
Proof: trivial cases pile to jackpot.
- ~13.5% (1/e²) never halt: no instructions transition to halt state.
- Gigantic reason: head starts leftmost cell, start state. Instructions: half move left immediately (head falls off tape, stops). Others right to new state; random walk (Pólya recurrence theorem: 1D random walk returns to origin with probability 1). On return, half fall off left. Thus, probability 1: head falls off before repeating state (non-halting).
Shows how to solve the halting problem by considering machine crashes. If the computation stops because the machine crashed, it doesn't count as halting on some accounts. If crashing is defined as halting, adjust the formalism accordingly. In any setup, you can answer the question for the machine's behavior when the head falls off.
Statistically, in the limit, you solve the halting problem computably. It solves almost all instances probabilistically. It's impossible to fully solve the halting problem correctly in all cases.
Versions interesting from complexity theory perspective. P vs NP problem: NP-complete problems are infeasible, take exponential time ordinarily, not known to be polynomial time solvable (open question). For most NP-complete problems, prove polynomial time approximation solves almost all instances feasibly.
Examples: knapsack problem, packing problems, satisfaction problems. Depending on formalism, prove feasible algorithms solve almost every instance. Proven many instances; widespread for almost all NP-complete problems. These are important for industrial applications.
P vs NP: relation between computation time and problem complexity. Will it be solved? Chance P = NP?
Could be independent (interesting for logicians), but relative to a theory—every statement independent over extremely weak theory. P in a problem means computable decision procedure runs in time bounded by some polynomial (coefficients enormous, degree incredibly high). Asymptotic property: relevant as input size goes to infinity.
For small inputs (human lifetime, civilization span), polynomial time feasibility doesn't apply. Temper claims: if P = NP, immense wealth from feasible algorithms for NP problems—but asymptotic, not practical for real inputs. We already have the algorithm (terrible, involves massive coding). Approximation algorithms solve real engineering problems pragmatically.
SAT solvers work amazingly well despite proofs no polynomial time SAT solver if P ≠ NP.
Candidates: Euler, Gauss, Newton, Ramanujan, Hilbert, Gödel, Turing.
Incredibly difficult; doesn't rank by greatness. Forced pick: Archimedes—incredible achievements transcending his era.
Prefers learning from anyone providing insight, not just greats. Sometimes greats first by luck. Progress in math: understand better now, so past achievements seem replicable. Disparate mathematicians prove similar results simultaneously.
Simultaneous discoveries common in math, physics, science: ideas in the air, not fully articulated—nature of knowledge growth.
Doesn't understand where ideas come from. Style: loves simple, clear, easy-to-understand arguments proving surprising results (new or not less important). Skeptical of complicated arguments (might be wrong, can't understand every step at once).
Avoids enormous projects with huge parts, different technologies. Large projects now use Lean programming language for validation, reducing skepticism.
Works off beaten path. Curiosity draws to simplicity; fortunate to contribute in this style.
Process (recommended to students): playful curiosity—play with idea/topic, change little things, basic case to complicated, press sides, apply to favorite example, see what happens. Leads to insights, methods, progress. Fool around until path to interesting thing, then prove.
Uses thought experiments/anthropomorphization: imagine ZFC model as place to live, travel by forcing to distant lands (metaphor). Visualize tensions as people fighting, game-theoretic players. Reveals strategies: enemy picks to make continuous, counter accordingly.
Andrew Wiles: 7 years grinding Fermat's Last Theorem (amazing). Different style: works collaboratively (~100 co-authors). Anybody's idea → collaborate, joint paper.
Couldn't do Wiles' isolation (MathOverflow gives ideas, papers—e.g., question → answer → idea → three-way paper). Math as social activity: put ideas forth, responses help learn mutually—productive.
Solo math terrifyingly lonely, especially sticking to problem that broke others: rollercoaster of breakthroughs/disappointments, walls, no brainstorming.
Grigori Perelman: declined Fields Medal, Millennium Prize. Quote: "I'm not interested in money or fame. The prize is completely irrelevant to me. If the proof is correct, then no other recognition is needed."
Math full of different people; doesn't matter—want their good ideas. Brilliant, solved famous hard problem (Poincaré conjecture implied). Views on prizes unclear.
Reminder: greats do it for love, not prizes/money (though useful if comes). Contribute to MathOverflow for curiosity, not wealth/power.
Objective criteria for greatest mathematician: MathOverflow score. Tenure/promotion on MathOverflow score. Asked daughter's boyfriend: chess rating, MathOverflow score.
Infinite chess: from MathOverflow question by Noam Elkies (cited in arXiv paper). Ordinary chess: 8x8 board. Infinite: integer board, infinite four directions, chessboard pattern, possibly infinitely many pieces.
No standard starting position: present complicated position with pieces, analyze.
Mate in N: infinite chess has positions white wins (checkmate infinitely many moves) but not mate in any finite N—white win, black controls duration (doomed; black forces 1000/million moves).
Position in first infinite chess paper: black to play; if not move rook, white checkmates quickly. Game value omega: white wins, black counts down from omega (giant step to finite, then subtract 1—picks initial number for duration).
Rules: ordinary pieces on infinite board (no edge/boundary). Moves same: knights, rooks (ranks/files), bishops (diagonals, any distance if clear). White pawns up, black down; capture diagonal.
Differences: no threefold repetition (proxy for infinite play). Infinite play = draw; win only by finite checkmate. No pawn promotion (no edge).
Collaboration: co-author Corey Evans (US national master, philosophy/law professor, son's elementary chess coach). Met at CUNY. Invaluable: proofs finicky, chess reasoning needed. Created positions (after generations corrected by Corey).
In developing infinite chess positions, the speaker knew the ordinals needed for the position and struggled to create them. They would show positions to collaborator Corey, who pointed out flaws like a hanging pawn breaking the argument or a bishop leaking out of the cage. This back-and-forth was extremely helpful, leading to correct arguments.
Follow-up Paper and Improvements
A follow-up three-way paper with Corey, the speaker, and PhD student Norman Perlmutter improved the bound, producing chess positions with higher ordinal values. The initial position had value omega, then omega-squared and omega-cubed in the first paper. The collaboration achieved omega to the 4th. Paper title: The Position in Infinite Chess with Game Value Omega to the 4th. This was the state-of-the-art at the time, but it has since been dramatically improved. Now, every countable ordinal arises as the game value of a position in infinite chess.
The speaker distinguishes current AI from future possibilities. Current LLMs have been unhelpful for mathematical reasoning, providing garbage answers that are incorrect. Interacting feels frustrating, like arguing with someone who insists on errors despite corrections—something they would avoid with a person.
They are skeptical of current systems' reliability for mathematical reasoning. Some prominent mathematicians report helpful uses, which surprises the speaker given their opposite experience. They use AI successfully for programming and image generation but not math arguments. Perhaps their interaction method needs improvement, or the mathematicians' successes involve heavy interaction where ideas come from the humans.
Concerns with LLM Approach
LLMs aim to produce arguments that sound like proofs, not ones that are proofs, creating a dangerous source of error. Analogy from undergrad at Caltech: Learning LaTeX produced beautifully typeset homework that looked like book math (assumed correct), masking bonehead mistakes and leading to poor grades. LLMs similarly produce plausible-looking arguments, fooling the unskeptical.
Tying to formal verification like Lean is different and promising, but casual chat use risks errors from text mimicry, not genuine understanding. Methods rely on word patterns in arguments, not underlying concepts.
Lex Fridman's Counterpoints
There's a skill in prompting LLMs with full context from one's work. Like programming, where colleagues share skepticism but providing structured info yields inspiration via broad connections across fields. Benefits: handholding, camaraderie, knowing vast knowledge to spark ideas—not direct answers. Requires extreme patience despite frustrations like obvious misunderstandings. Programming has abundant training data, showing promising collaboration potential, not yet genius insights.
Speaker agrees, noting math training data likely includes MathOverflow, making it like talking to oneself.
Transfinite ordinals, invented by Georg Cantor for counting beyond infinity. Start with natural numbers: 0, 1, 2, .... Then omega, omega + 1, omega + 2, ..., omega + omega (first after all omega + n), omega + omega + 1, etc. Continues to omega times 3, omega times 4, limiting to omega squared—first compound limit ordinal (limit of limit ordinals like omega times n).
Then omega squared + 1, etc. Process never ends. Simple, elegant idea foundations transfinite recursive constructions: Cantor-Bendixson theorem, V hierarchy, Gödel's constructible universe, Zermelo's well-ordering proof via axiom of choice. Infinity is not the end.
Speaker straddles math and philosophy: math PhD/degrees, but work engages philosophical issues. Appointments: math then philosophy at CUNY Graduate Center (NY); philosophy main at Oxford, now at Notre Dame (also concurrent math prof, supervising PhD students in both). No need to choose—ample overlap.
Anecdote: Daughter surprised at Oxford philosophy professorship, seeing father as mathematician, mother (wife Barbara, also Notre Dame philosopher) as philosopher.
Most beautiful philosophical idea: distinction between truth and proof. Truth concerns objective mathematical reality (Platonic realm); proof is human interaction/understanding of it. Gap filled with mysteries across math, physics, psychology, sociology, politics—discovery process vs. reality itself.
Well, I for one, am grateful for how marvelous of a philosopher, mathematician, and human being you are. It's truly an honor to speak with you today.
Well, thank you so much. It's such a pleasure to be here, and thank you for inviting me.
Keep Lex Fridman in your library
Save the videos and channels worth coming back to, and find them again in one place.
