Joel David Hamkins Challenges Cantor's Monist Set Theory on Foundations of Infinity

Joel David Hamkins在无穷基础问题上挑战康托尔的一元集合论 连续统假设并非一个具有唯一定论、有待解决的问题，而是一个证明了集合论多元宇宙存在的数学开关。 该对话梳理了无穷的历史演变与哲学悖论，涵盖从 Georg Cantor 的革命性发现、Bertrand Russell 带来的基础性挑战，直至现代 ZFC 集合论的发展历程。对话深入探讨了 Kurt Gödel 的不完备性定理、Alan Turing 的停机问题，以及数学真理与句法证明之间的深刻鸿沟。此外，Hamkins 详细阐释了连续统假设，并说明了他提出的“集合论多元宇宙”观点，该观点将数学独立性结果以及 John Conway 的超现实数等系统，视为通向不同且相互作用的数学现实之路径。 19世纪格奥尔格·康托尔（Georg Cantor）发现“某些无穷大于其他无穷”，颠覆了无穷与神学专属绑定的传统观念，并证明无穷集合彻底打破了欧几里得“整体大于部分”的经典公理。 (2:17) 希尔伯特旅馆等思想实验直观展示了可数无穷的特性，证明向可数无穷集合中加入有限或可数无穷个新元素，均不会改变其基础基数。 (19:38) 康托尔通过开创性的反证法——对角线论证（Diagonal Argument），严格确立了实数集是不可数的，且其大小严格大于自然数集。 (27:51) 策梅洛（Ernst Zermelo）在1904年证明选择公理蕴含良序原理，由此引发学界对非构造性数学对象的巨大争议，并直接推动了现代ZFC公理化集合论的建立。 (43:51) 罗素悖论证明不存在包含所有集合的“万全集”，用精炼的自指矛盾彻底击溃了弗雷格（Gottlob Frege）试图将数学完全归结为逻辑的逻辑主义宏图。 (57:26)

Mathematician and philosopher Joel David Hamkins argues that foundational paradoxes and undecidability results do not signal a crisis in mathematics, but rather clarify the boundary between formal provability and truth, pointing toward a pluralistic mathematical multiverse. Actual Infinity and Cantor's Diagonalization (19:38) Historical mathematics maintained an Aristotelian orthodoxy prioritizing potential infinity over completed, actual infinities. Galileo anticipated modern tensions by identifying equinumerous paradoxes between natural numbers and geometric segments, which were resolved through the Cantor-Hume principle. Georg Cantor later established transfinite arithmetic, using his diagonal argument to demonstrate that real numbers are strictly more numerous than natural numbers. Cantor generalized this result to prove that every set's power set is strictly larger than the set itself, demonstrating that multiple sizes of infinity exist. Axiomatization, Russell's Paradox, and Foundational Limits (40:13) To systematize set theory and avoid paradoxes like Russell's paradox—which demonstrated that Gottlob Frege's general comprehension principle yields a contradiction, proving no universal set exists—mathematicians instituted the Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC). Russell's analogy of an infinite closet of indistinguishable socks illustrated the controversy surrounding the Axiom of Choice: whether a choice function requires an explicit selection rule or can exist as an arbitrary mathematical object. Formal systems establish strict baselines, but logicians such as Alfred Tarski clarified that defining semantic truth requires separating formal syntax from model-specific semantics. Incompleteness, Turing Decidability, and Independence (76:18) David Hilbert sought a complete, computably axiomatizable theory capable of deciding all arithmetic propositions and proving its own consistency using finitistic methods. Kurt Gödel refuted this program by demonstrating that any computably axiomatizable, consistent system containing arithmetic is incomplete and incapable of proving its own consistency. Alan Turing established equivalent limits through the undecidability of the Halting Problem via diagonal inversion. Rather than viewing incompleteness as a crisis, Hamkins treats it as an informative revelation about the limits of computation and formal theories. Set-Theoretic Multiverse Versus the Universe View (148:18) Following proofs by Gödel and Paul Cohen showing the independence of the continuum hypothesis and the Axiom of Choice from ZFC, set theorists discovered thousands of independent combinatorial propositions. Set theorists navigate between alternative mathematical models using the technique of forcing. This persistence of independence leads Hamkins to reject the monist 'universe view'—advocated by figures like Hugh Woodin, who seek a single, definitive true universe of sets—in favor of a 'multiverse view' recognizing multiple distinct, equally valid mathematical realities across an unending consistency-strength hierarchy. Heuristics, AI Reasoning, and Truth Versus Proof (215:28) Hamkins prefers intuitive, simple arguments and playful anthropomorphic metaphors over excessively complex formal machinery when analyzing problems like infinite chess or cellular automata. Addressing recent developments in artificial intelligence, Hamkins expresses deep skepticism regarding the capacity of current Large Language Models to conduct authentic mathematical reasoning. He argues that LLMs are engineered to mimic the linguistic appearance of proofs—analogous to visually appealing LaTeX formatting—rather than verifying actual logical soundness, maintaining that a strict conceptual boundary remains between proof mechanisms and objective truth. The exploration of transfinite set theory, undecidable problems, and independence highlights an enduring divide between objective mathematical truth and human proof systems, leaving open whether foundational mathematics will ultimately coalesce around an extended axiomatic standard or permanently embrace the pluralism of the multiverse.

数学家兼哲学家乔尔·大卫·哈姆金斯（Joel David Hamkins）指出，现代数学基础已从寻求单一确定性体系转向包容多元性，哥德尔不完备定理与海量独立性命题并非学科危机，而是揭示了数学实在由多个自洽体系构成的“数学多宇宙”（Multiverse）。他强调，必须严格区分客观存在的“真理”与形式验证的“证明”，这种认识构成了现代逻辑与数学哲学的基石。 无穷的结构化与公理化集合论的建立 (33:56) 回顾数学史，亚里士多德曾确立仅承认“潜无穷”而排斥“实无穷”的传统，阿基米德等早期学者均将无穷视作永无止境的逼近过程；直至伽利略指出自然数与其平方数一一对应等反直觉现象，无穷集合的等势性才初现端倪。格奥尔格·康托尔（Georg Cantor）通过对角线论证法证明实数集合严格大于自然数集合，并证明任何集合的幂集基数均严格大于原集合，打破了无穷只有单一尺度的传统直觉。这一突破引发了“无穷危机”，促使数学家通过集合概念将复杂对象封装为单一实体，并发展出严格的公理系统。 为解决弗雷格逻辑主义中因“无限制概括原则”而暴露的罗素悖论（即不存在包含所有集合的绝对全集），策梅洛（Ernst Zermelo）与弗兰克尔（Adolf Fraenkel）建立了ZFC公理体系，确立了外延公理、空集公理、并集公理、幂集公理与无穷公理等基础规则。针对选择公理（Axiom of Choice），伯特兰·罗素（Bertrand Russell）曾以“在无穷双不可区分的袜子中挑选一只”作比，说明选择公理涉及无法用客观构造规则定义的任意选择。哈姆金斯强调，选择公理的成立反映了数学本体论中独立对象的丰富性，现代集合论已将罗素悖论内化为“不存在全集”的形式定理，奠定了现代数学的结构根基。 希尔伯特纲领的破灭与可计算性边界 (76:18) 20世纪初，大卫·希尔伯特（David Hilbert）为抵御集合论悖论提出了“希尔伯特纲领”，主张借助形式主义将数学推理转化为符号演算，并试图利用较弱的有穷算术理论证明强无穷理论的无矛盾性与完备性。然而，库尔特·哥德尔（Kurt Gödel）的不完备定理打破了这一设想：任何包含基础算术的计算可公理化形式系统，只要自洽就必然是不完备的，且绝无法证明自身的自洽性。哈姆金斯形象地将形式系统宣称自身自洽比作“二手车推销员自夸值得信赖”，强调自洽系统证明自身可靠毫无逻辑价值，因为矛盾系统同样能证明自身正确。 与哥德尔定理并行的另一里程碑是阿兰·图灵（Alan Turing）对判定问题（Entscheidungsproblem）的解决，证明停机问题（Halting Problem）在算法上完全不可判定。若存在能够完全判定所有算术真理的完备公理系统，便可通过枚举定理直接解决停机问题，这反向构成了一条无需构造复杂哥德尔句子的不完备定理简明证明路径。面对传统学界将不完备性视作创伤的观点，哈姆金斯持明确的积极态度，认为这并非危机，而是深刻澄清了人类面对数学真理时的真实处境，有助于摆脱全知幻觉并推进数学认知。 独立性结果与数学多宇宙的崛起 (148:18) 康托尔提出的连续统假设（CH）主张自然数基数与实数基数之间不存在中间无穷大，位列希尔伯特23个数学难题之首。尽管在博雷尔阶层及引入大基数公理的投影阶层上部分命题得到推进，但哥德尔与保罗·寇驰（Paul Cohen）最终证明，连续统假设在标准ZFC公理系统下是完全独立的——即在现有公理下既不能证明也不能证伪。寇驰发明的“力迫法”（Forcing）成为在不同数学模型间穿梭的通用工具，数学家可借此向现有模型添加新集合以构建满足或不满足连续统假设的拓展宇宙，类似历史上数学家借助虚数解决实数方程后再回归现实世界。 哈姆金斯指出，无穷组合学中几乎所有深层命题均独立于ZFC，这意味着独立性不是罕见特例而是普遍常态。基于此，他明确反对以其导师休·伍丁（Hugh Woodin）为代表的“单宇宙观”（即坚信存在唯一的终极真实集合论宇宙），转而坚定倡导“数学多宇宙观”（Multiverse View）。在多宇宙框架下，不存在凌驾一切的单一真理宇宙，各个满足ZFC公理的模型作为平权且独立的数学实体共同存在，真理的取值随着具体宇宙的公理与模型结构而发生改变。 计算复杂性与人工智能的证明假象 (215:28) 在可计算性理论与复杂性科学中，不可判定性广泛渗透于具体数学系统中。例如康威生命游戏中特定细胞是否会被激活的问题等价于停机问题，莱斯定理（Rice's Theorem）进一步指出任何程序的非平凡语义性质均无法单纯靠检查源代码判定。尽管在NP完全问题中，多项式时间近似算法与SAT求解器能在现实场景中解决绝大部分实例，甚至有约13.5%（收敛于$1/e^2$）的图灵机因完全缺乏停机指令而显式不休眠，但最坏情况下的理论黑洞依旧不可逾越。 哈姆金斯结合自己在研究中追求简明直观论证的风格，对当前大语言模型（LLM）在严谨数学推理中的应用表达了强烈怀疑。他认为，当前文本生成模型的核心目标是生成“听起来像证明”的符号序列，而非构造在逻辑上严密成立的真正证明。他将这种表面合理性称为“LaTeX假象”，指出模型输出缺乏对深层概念与客观数学现实的对应纽带，极易产生顽固且隐蔽的逻辑错误。他主张，唯有结合如Lean这类严密的形式化证明验证工具，人工智能才可能真正参与到可靠的数学推导中。 哈姆金斯总结认为，数学逻辑中最迷人且深奥的概念在于“真理”（客观事实的实在状态）与“证明”（人类形式化的验证机制）之间的本体论鸿沟。哥德尔与图灵的工作明确了人类符号化证明的硬边界，而独立性结果与多宇宙观则极大丰富了数学实在的维度；承认证明无法穷尽真理不仅不是理性探索的失败，反而是人类准确把握数学现实多样性的必要开端。

[24:43] Joel David Hamkins: Suppose, toward contradiction, that there were some boring numbers.... But 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. So therefore, there cannot be any boring numbers. [33:56] Joel David Hamkins: The axiom of choice principle is completely obvious that we want this to be true, that it is true. I mean, a lot of people take it as a law of logic. If you have a bunch of sets, then there's a way of picking an element from each of them. [40:13] Joel David Hamkins: Why should everything that exists in mathematical reality follow a rule or a procedure of that sort? [57:26] Gottlob Frege: 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. [63:07] David Hilbert: Wir müssen wissen, wir werden wissen [88:04] Joel David Hamkins: I mean, my view is that this isn't traumatic at all. This is rather completely eye-opening in terms of our understanding of the nature of mathematical reality. [99:05] Joel David Hamkins: may all their theorems be true, proved by elegant arguments that flow effortlessly from hypothesis to conclusion while revealing fantastical mathematical beauty. [118:35] Joel David Hamkins: I live entirely in the Platonic realm, and I don't really understand the physical universe at all. [152:00] Joel David Hamkins: The fact that given any model of set theory, there's a forcing extension where the continuum hypothesis is true, and another one where it's false. You can sort of turn it on and off like a light switch. [172:00] Joel David Hamkins: The surreal numbers... Not the numbers themselves, but the reception of the surreal numbers... He had ambition that the surreal numbers would become a fundamental number system used throughout mathematics and science... And he was disappointed that it never really achieved that unifying status.

[0:00] - The following is a conversation with Joel David Hamkins, a [0:03] mathematician and philosopher specializing in set theory, [0:07] the foundation of mathematics and the nature of [0:10] infinity. He is the number one highest [0:14] rated user on MathOverflow, which I think is a legendary [0:17] accomplishment. MathOverflow, by the way, is like StackOverflow [0:21] but for research mathematicians. He is [0:25] also the author of several books, including Proof [0:29] in the Art of Mathematics and Lectures on the [0:32] Philosophy of Mathematics. And he has a great blog, [0:37] infinitelymore.xyz. This is a super technical and [0:44] super fun conversation about the foundation of modern mathematics [0:48] and some mind-bending ideas about infinity, [0:52] nature of reality, truth, and the mathematical [0:55] paradoxes that challenged some of the greatest minds of the 20th century. [1:02] I have been hiding from the world a bit, reading, thinking, writing, soul-searching, [1:10] as we all do every once in a while. But mostly, just deeply focused [1:14] on work and preparing mentally for some challenging travel I [1:18] plan to take on in the new year. Through all of it, a recurring thought comes to me, [1:25] how damn lucky I am to be alive and to get to [1:29] experience so much love from folks across the [1:32] world. I want to take this moment to say thank you [1:37] from the bottom of my heart for everything, for your [1:40] support, for the many amazing conversations I've had [1:44] with people across the world. I got a little bit of hate [1:50] and a whole lot of love, and I wouldn't have it [1:54] any other way. I'm grateful for all of it. [1:58] This is the Lex Fridman Podcast. To support it, please check out our [2:01] sponsors in the description, where you can also [2:05] find ways to contact me, ask questions, give feedback, and so on. And now, dear [2:13] friends, here's Joel David Hamkins. [2:17] Some infinities are bigger than others. This idea from [2:21] Cantor at the end of the 19th century, I think it's fair to [2:25] say, broke mathematics before rebuilding it. And [2:29] I also read that this was a devastating and transformative discovery for [2:32] several reasons. So one, it created a theological [2:36] crisis. Because infinity is associated with God, how could there be multiple [2:40] infinities? And also, Cantor was deeply religious [2:43] himself. Second, there's a kind of mathematical civil [2:47] war. The leading German mathematician Kronecker called Cantor a corrupter of youth [2:54] and tried to block his career. Third, many [2:58] fascinating paradoxes emerged from this, like Russell's [3:02] paradox, about the set of all sets that don't contain themselves, [3:06] and those threatened to make all of mathematics [3:09] inconsistent. And finally, on the psychological side and the personal [3:13] side, Cantor's own breakdown. He literally went mad, [3:16] spending his final years in and out of sanatoriums, obsessed with [3:20] proving the continuum hypothesis. So, laying that all out on the [3:24] table, can you explain the idea of infinity, that some infinities are [3:31] larger than others, and why was this so transformative to mathematics? [3:35] - Well, that's a really great question. I would want to start [3:39] talking about infinity and telling the story much [3:43] earlier than Cantor, actually, because, I mean, you can go all the way [3:47] back to Ancient Greek times when Aristotle [3:51] emphasized the potential aspect of infinity as opposed [3:55] to the impossibility, according to him, of achieving an actual [3:59] infinity. And Archimedes' method of exhaustion where [4:02] he is trying to understand the area of a region [4:06] by carving it into more and more triangles, say, and [4:10] sort of exhausting the area and thereby understanding the total area in terms [4:14] of the sum of the areas of the pieces that he put into it. [4:18] And it proceeded on this kind of potential understanding of infinity for hundreds of years, [4:22] thousands of years. Almost all mathematicians were [4:26] almost all mathematicians were potentialists only and [4:30] thought that it was incoherent to speak of an actual [4:33] infinity at all. Galileo is an extremely prominent exception to this, though he [4:41] argued against this sort of potentialist orthodoxy [4:45] in The Dialogue of Two New Sciences. Really lovely [4:48] account there that he gave. And that the... In many ways, Galileo was anticipating [4:56] Cantor's developments, except he couldn't quite push it all the way [5:00] through and ended up throwing up his hands in confusion [5:06] in a sense. I mean, the Galileo paradox is the idea or the [5:10] observation that if you think about the natural numbers, [5:14] I would start with zero but I think maybe he would start with one. The numbers one, [5:18] two, three, four, and so on, and you think about which of those [5:22] numbers are perfect squares. So zero squared is [5:25] zero and one squared is one and two squared is four, three [5:29] squared is nine, 16, 25, and so on. And Galileo [5:33] observed that, that the perfect squares can be [5:37] put into a one-to-one correspondence with all of the [5:41] numbers. I mean, we just did it. I associated every number [5:44] with its square. And so it seems [5:48] like on the basis of this one-to-one correspondence that [5:52] there should be exactly the same number of [5:56] squares, perfect squares as there are numbers, and [5:59] yet there's all the gaps in between the perfect squares, [6:03] right? And, and this suggests that there should be fewer perfect squares, more [6:10] numbers than squares because the numbers include all the squares plus a lot more in [6:14] between them, right? And Galileo was quite troubled by this observation because [6:21] he took it to cause a kind of incoherence in the [6:24] comparison of infinite quantities, right? And another example [6:28] is, if you take two line segments of different lengths, [6:33] and you can imagine drawing a kind of foliation, [6:37] a fan of lines that connect them. So the endpoints are [6:41] matched from the shorter to the longer segment, and the midpoints are matched and [6:45] so on. So spreading out the lines as you go. And so every [6:48] point on the shorter line would be associated with [6:52] a, a unique distinct point on the longer line in a [6:55] one-to-one way. And so it seems like the two [6:59] line segments have the same number of points on them because of that, even [7:03] though the longer one is longer. And so it [7:07] makes, again, a kind of confusion over our ideas about infinity. And [7:11] also with two circles, if you just place them [7:13] concentrically and draw the rays from the center, [7:17] then every point on the smaller circle is associated [7:21] with a corresponding point on the larger circle, you know, in a [7:25] one-to-one way. And, and again, that seems to show that the [7:28] smaller circle has the same number of points on it as the larger one, precisely [7:32] precisely because they can be put into this one-to-one correspondence. [7:36] Of course, the contemporary attitude about this situation is that those two [7:40] infinities are exactly the same, and that Galileo was right in those [7:44] observations about the equinumerosity. We would talk about it now [7:47] by appealing to what I call the Cantor-Hume principle, or some people [7:51] just call it Hume's principle, which is the idea that if you have two [7:55] collections, whether they're finite or infinite, then we want to [7:59] say that those two collections have the same size. They're [8:03] equinumerous if and only if there's a one-to-one [8:06] correspondence between those collections. Galileo was [8:10] observing that line segments of different lengths are equinumerous, [8:14] and the perfect squares are equinumerous with all of the [8:18] natural numbers, and any two circles are equinumerous, and so [8:22] on. The tension between the Cantor-Hume [8:25] principle and what could be called Euclid's principle, which is that the [8:30] whole is always greater than the part, is a principle that Euclid [8:34] appealed to in the Elements many times when he's calculating [8:38] area and so on. It's a basic idea [8:42] that if something is just a part of another thing, then the [8:45] whole is greater than the part. So what Galileo [8:50] was troubled by was this tension between [8:54] what we call the Cantor-Hume principle and Euclid's [8:57] principle. It wasn't fully resolved, I [9:01] think, until Cantor. He's the one who really explained [9:05] so clearly about these different sizes of infinity and so on [9:09] in a way that was so compelling. He [9:13] exhibited two different infinite sets and proved that [9:17] they're not equinumerous; they can't be put into one-to-one [9:20] correspondence. It's traditional to talk about the [9:23] uncountability of the real numbers. Cantor's big result was that the [9:27] set of all real numbers is an uncountable set. Maybe if we're [9:31] going to talk about countable sets, then I would suggest that we talk [9:35] about Hilbert's Hotel, which really makes that idea perfectly clear. [9:39] - Yeah, let's talk about Hilbert's Hotel. [9:41] - Hilbert's Hotel is a hotel with infinitely many rooms. Each [9:45] room is a full floor suite. So there's floor zero... I always [9:49] start with zero because for me, the natural numbers start with zero, although that's [9:54] maybe a point of contention for some mathematicians. The other [9:57] mathematicians are wrong. [9:58] - Like I mentioned, I'm a programmer, so starting at zero is a wonderful place to start. [10:01] - Exactly. So there's floor zero, floor one, floor two, or room zero, [10:05] one, two, three, and so on, just like the natural numbers. So Hilbert's Hotel has a [10:09] room for every natural number, [10:13] and it's completely full. There's a person occupying room N for [10:17] every N. But meanwhile, a new guest comes up to the [10:20] desk and wants a room. "Can I have a room, please?" The manager says, [10:24] "Hang on a second, just give me a moment." [10:27] You see, when the other guests had checked in, they had to sign an [10:31] agreement with the hotel that maybe [10:35] there would be some changing of the rooms during this stay. [10:39] So the manager sent a message up to all the current [10:43] occupants and told every person, "Hey, can you [10:47] move up one room, please?" So the person in room five would move to [10:51] room six, and the person in room six would move to room seven and so on. And everyone [10:55] moved at the same time. And of course, we never want to be placing two different [10:58] guests in the same room, and we want everyone to have their own private room [11:02] and... But when you move everyone up one room, then the bottom [11:06] room, room zero, becomes available, of course. And so he can put the new guest in [11:10] that room. So even when you have infinitely many [11:13] things, then the new guest can be accommodated. And that's a way of [11:17] showing how the particular infinity of the occupants of [11:21] Hilbert's Hotel, it violates Euclid's principle. I [11:25] mean, it exactly illustrates this idea because [11:28] adding one more element to a set didn't make it larger, because we [11:32] can still have a one-to-one correspondence between the total new [11:36] guests and the old guests by the room number, right? [11:40] - So, to just say one more time, the hotel is full. [11:45] - The hotel is full. [11:46] - And then you could still squeeze in one more, and that breaks [11:50] the traditional notion of mathematics and breaks [11:54] people's brains when they try to think about infinity, I suppose. This is [11:58] a property of infinity. [11:59] - It's a property of infinity that sometimes when you add an [12:03] element to a set, it doesn't get larger. That's what this [12:07] example shows. But one can go on with Hilbert's [12:11] Hotel, for example. I mean, maybe the next day, you know, [12:15] 20 people show up all at once. We can easily do the same trick again, just move [12:19] everybody up 20 rooms. And then we would have 20 [12:23] empty rooms at the bottom, and those new 20 guests could go [12:26] in. But on the following weekend, a giant bus pulled up, Hilbert's [12:33] bus. And Hilbert's bus has, of course, [12:37] infinitely many seats. There's Seat Zero, Seat One, Seat Two, Seat Three, and so [12:41] on. And so one wants to... You know, all the people on the bus want [12:45] to check into the hotel, but the hotel is completely full. So what is the manager going to [12:49] do? And when I talk about Hilbert's Hotel, [12:53] when I teach Hilbert's Hotel in class, I always demand that the [12:56] students provide, you know, the explanation of- of how to do it. [13:00] So maybe I'll ask you. [13:02] Can you tell me, yeah, what is your idea about how to fit them all in the hotel, everyone [13:06] on the bus, and also the current occupants? [13:08] - You separate the hotel into even and odd rooms, and you squeeze in the new [13:15] Hilbert bus people into the odd rooms and the previous occupants [13:19] go into the even rooms. [13:20] - That's exactly right. That's a very easy way to do it. If you [13:23] just tell all the current guests to double their room number, so in [13:27] Room N, you move to Room 2 times N. So they're all going to get their own [13:31] private room, the new room, and it will always be an even number 'cause 2 times N is always an even [13:35] number. And so all the odd rooms become empty that way. And now we can [13:39] put the bus occupants into the odd-numbered rooms. [13:42] - And by doing so, you have now shoved an infinity into another infinity. [13:47] - That's right. So what it really shows... I mean, another way of thinking [13:51] about it is that, well, we can define that a set is [13:54] countable if it is equinumerous with a set of natural [13:58] numbers. And a kind of easy way to understand what that's [14:02] saying in terms of Hilbert's Hotel is that [14:04] a set is countable if it fits into Hilbert's Hotel, 'cause Hilbert's Hotel [14:08] basically is the set of natural numbers in terms of the room numbers. So to be [14:12] equinumerous with a set of natural numbers is just the same thing as to fit into Hilbert's [14:16] Hotel. And so what we've shown is that [14:20] if you have two countably infinite sets, then their [14:24] union is also countably infinite. If you put them together and form a new set [14:28] with all of the elements of either of them, then that union set is still [14:33] only countably infinite. It didn't get bigger. [14:36] And that's a remarkable property for a notion [14:40] of infinity to have, I suppose. But if you thought that there was only [14:43] one kind of infinity, then it wouldn't be surprising at all, because if you take [14:48] two infinite sets and put them together, then it's still infinite. And so if there were only one kind of [14:51] infinity, then it shouldn't be surprising... [14:53] that the union of two countable sets is countable. So there's another way [14:57] to push this a bit harder, and that is when Hilbert's train [15:02] arrives, and Hilbert's train has infinitely many train cars... [15:08] ...and each train car has infinitely many seats. [15:13] And so we have an infinity of infinities of the train [15:16] passengers together with the current occupants of the [15:20] hotel, and everybody on the train wants to check in to Hilbert's Hotel. [15:26] So the manager can, again, of course, send a message up to all the [15:30] rooms telling every person to double [15:33] their room number again. And so that will occupy all the [15:37] even-numbered rooms again, and but free up again the [15:41] odd-numbered rooms. So somehow, we want to put the train passengers [15:45] into the odd-numbered rooms. And so while [15:49] every train passenger is on some car, let's say Car C and Seat S, [15:55] so somehow, we have to take these two coordinates, you know, C, [15:59] S, the car number and the seat number, and produce from [16:03] it an odd number in a one-to-one way, you [16:06] know? And that's actually not very difficult. In [16:10] fact, one can just use, say... An easy way to do it is to just use the number [16:18] 3 to the C times 5 to the S. 3 to the C, 3 to the car number, so 3 x 3 x [16:25] 3, you know, the number of the car. You multiply 3 by itself, the [16:29] number of the train car, and then you multiply 5 by itself [16:33] the seat number of times, and then you multiply those two numbers together. So [16:37] 3 to the C times 5 to the S. That's [16:41] always an odd number, 'cause the prime factorization has only 3s and [16:45] 5s in it. There's no 2 there. So therefore, it's [16:48] definitely an odd number, and it's always different because [16:53] of the uniqueness of prime factorization. So every number [16:57] can be factored uniquely into primes. So if you have a number of that form, [17:00] then you can just factor it, and that tells you the exponent on 3 and the [17:04] exponent on 5. And so you know exactly which person it was, which car [17:08] they came from, and which seat they came from. [17:10] - And prime factorization is every single number can be [17:15] decomposed into the atoms of mathematics, which is the prime [17:19] numbers. You can multiply them together to achieve that number. [17:23] And that's prime factorization. You're showing 3 and 5 are both prime numbers, [17:28] odd. So through this magical formula, you can deal with this [17:35] train, infinite number of cars, with each car having infinite number of seats. [17:41] - Exactly right. We've proved that if you have countably many [17:45] countable sets, then the union of those [17:48] sets, putting all those sets together into one giant set, [17:52] is still countable. You know, because the train cars are each countable, plus the current [17:55] hotel. It's sort of like another train car, if you want to think about it that way. The current [17:59] occupants of the hotel could, you know, have the same number as [18:03] any of the train cars. So putting countably many [18:07] countable sets together to make one big union set is [18:11] still countable. It's quite remarkable, I think. I mean when [18:15] I first learned this many, many years ago, I was completely shocked by it and [18:19] transfixed by it. It was quite amazing to me that this notion [18:23] of countable infinity could be closed under this process of [18:26] infinitely many infinities adding up still to the very same [18:30] infinity, which is a strong instance, a [18:34] strong violation of Euclid's principle once again, right? So, the new [18:38] set that we built is... has many more elements than the old [18:42] set in the sense that there are additional elements, but it doesn't have many [18:46] more elements in terms of its size because it's still just a countable [18:50] infinity and it fits into Hilbert's Hotel. [18:53] - Have you been able to sort of internalize a good intuition about [18:58] countable infinity? Because that is a pretty weird thing. You can have a countably [19:04] infinite set of countably infinite sets, and you can shove it [19:08] all in and it still is a countable infinite set. [19:11] - Yeah, that's exactly right. I mean, I guess, [19:15] of course, when you work with these notions, the argument of [19:19] of Hilbert's Hotel becomes kind of clear. There are many other ways to [19:23] talk about it too. For example, let's think about, say, [19:27] the integer lattice, the grid of points that you [19:31] get by taking pairs of natural numbers, say, so the upper [19:35] right quadrant of the integer lattice, yeah? [19:38] So there's the, you know, row zero, row one, row two and so on, column zero, column one, column two and so on, [19:42] and each row and column has a countable infinity of points on it, right? [19:50] So those dots, if you think about them as dots, [19:54] are really the same as the train cars if you think about each column [19:58] of... in that integer lattice, it's a countable infinity. It's like one [20:02] train car and then there's the next train car next to it, and then the next column [20:05] next to that, the next train car. [20:08] And so, but if we think about it in this grid manner, then I can imagine [20:12] a kind of winding path winding through these grid [20:16] points, like up and down the diagonals. [20:19] Winding back and forth. So I start at the corner point and then I go down, [20:23] up and to the left, and then down and to the right, up and to the left, down and to the right, and so on, [20:28] in such a way that I'm going to hit every grid point on this path. [20:34] So, this gives me a way of assigning room numbers to the points. [20:38] Because every grid point is going to be the [20:42] Nth point on that path for some N. And that [20:46] that gives a correspondence between the grid points and the natural numbers [20:49] themselves. So it's a kind of different picture. Before, we used this 3 [20:53] to the C, 5 times 5 to the S, which is a kind of, you [20:57] know, overly arithmetic way to think about it. But there's a kind [21:01] of direct way to understand that it's still a [21:05] countable infinity when you have countably many countable sets, because you can just [21:09] start putting them on this list. And as long as you give each of the infinite collections a [21:13] chance to add one more person to the list, then [21:17] you're going to accommodate everyone in any of the sets in one list. [21:20] - Yeah, it's a really nice visual way to think about it. You just zigzag your way across the grid [21:25] to make sure everybody's included. That gives you an algorithm for including [21:29] everybody. So, can you speak to the uncountable infinities? [21:33] - Yeah, absolutely. [21:33] - What are the integers and the real numbers- [21:35] - Correct [21:36] - and what is the line that Cantor was able to find? [21:38] - Maybe there's one more step I want to insert before doing that. [21:43] Which is the rational numbers. So we did pairs of natural numbers. [21:50] Right? That's the train car, basically. But maybe it's a little [21:54] bit informative to think about the rational, the fractions, the set of [21:57] fractions, or rational numbers, [22:00] because a lot of people maybe have an expectation that maybe this is a bigger [22:04] infinity because the rational numbers are densely ordered. [22:08] Between any two fractions, you can find another fraction, right? [22:12] The average of two fractions is another fraction. And so, sometimes people, [22:18] it seems to be a different character than the [22:22] integers, which are discretely ordered, right? From any integer, there's a next one and a [22:26] previous one, and so on. But that's not true in the rational [22:29] numbers. And yet, the rational numbers are [22:33] also still only a countable infinity. And the way to see that is actually [22:40] it's just exactly the same as Hilbert's train again, because every fraction [22:43] consists of two integers: the numerator and the [22:47] denominator. And so if I tell you two natural [22:51] numbers, then you know what fraction I'm talking about. I mean, plus the [22:55] sign issue, I mean if it's positive or negative. But if you just think about the [22:58] positive fractions, then, you know, you have the numbers of the form [23:02] P over Q, where Q is not zero. So you can still do [23:06] 3 to the P times 5 to the Q. The same idea works. [23:11] with the rational numbers. So this is still a countable [23:14] set. And you might think, "Well, every set [23:18] is going to be countable because there's only one infinity." I mean, if that's a kind of [23:22] perspective maybe that you're adopting, but it's not [23:26] true, and that's the profound achievement that Cantor made is proving that the set of [23:30] real numbers is not a countable infinity. It's a strictly larger [23:33] infinity, and therefore there's more than one [23:37] concept of infinity, more than one size of infinity. [23:40] - So let's talk about the real numbers. What are the real numbers? Why do they break infinity? [23:44] The countable infinity. Looking it up on Perplexity, real numbers [23:49] include all the numbers that can be represented on the number line, encompassing both [23:53] rational and irrational numbers. We've spoken about the rational numbers, and the [23:57] rational numbers, by the way, are by definition, the numbers that can be represented [24:01] as a fraction of two integers. [24:05] - That's right. So with the real numbers, we have the algebraic numbers. We [24:09] have, of course, all the rational numbers. The integers and the rationals are all part of the [24:13] real number system. But then also, we have the algebraic numbers like the square root of [24:16] 2 or the cube root of 5 and so on. Numbers that solve an [24:20] algebraic equation over the integers, those are known as algebraic [24:24] numbers. It was an open question for a long time whether that was [24:27] all of the real numbers or whether there would [24:31] exist numbers that are the transcendental numbers. The [24:35] transcendental numbers are real numbers that are not algebraic. [24:38] - And we won't even go to the surreal numbers about which you have a wonderful blog post. [24:42] We'll talk about that a little bit later. [24:43] - Oh, great. So it was Liouville who first proved that [24:47] there are transcendental numbers, and he exhibited a very specific number [24:51] that's now known as the Liouville constant, which is a transcendental [24:55] number. Cantor also famously proved that there are many, [24:59] many transcendental numbers. In fact, it follows from his [25:03] argument on the uncountability of the real numbers that there are [25:07] uncountably many transcendental numbers. So most real numbers are transcendental. [25:12] - And again, going to Perplexity, "Transcendental numbers are 'real' or 'complex' [25:15] numbers; they are not the root of any nonzero polynomial with [25:19] integer or rational coefficients. This means they cannot [25:23] be expressed as solutions to algebraic equations with integer coefficients, [25:27] setting them apart from algebraic numbers." [25:31] - So some of the famous transcendental numbers would include the number pi, [25:35] you know, the 3.14159265 and so on. [25:41] So that's a transcendental number. Also, Euler's constant, the [25:44] e, like e to the x, the exponential function. [25:47] - So you could say that some of the sexiest numbers in mathematics are all transcendental numbers? [25:51] - Absolutely. That's true. Yeah, yeah. Although, you know, I don't know, square root of two is [25:55] pretty [25:56] - Square root. All right. So it depends. Let's not... Beauty can be found in [26:00] in all the different kinds of sets, but yeah. [26:02] - That's right. And if you have a kind of simplicity attitude, then zero and one are looking pretty good too, [26:06] so... And they're definitely not [26:07] - Sorry to take that tangent, but what is your favorite number? Do you have one? [26:10] - Oh, gosh. You know- [26:12] - Is it zero? [26:13] - Did you know there's a proof that every number is [26:17] interesting? You can prove it, because... [26:22] - Yeah? What's that proof look like? [26:23] - Yeah, okay. [26:23] - How do you even begin? [26:24] - I'm gonna prove to you- [26:25] - Okay [26:26] - ...that every natural number is interesting. [26:28] - Okay. [26:29] - Yeah. I mean, zero's interesting because it's the additive identity, right? [26:32] That's pretty interesting. And one is the multiplicative identity, so when you [26:36] multiply it by any other number, you just get that number back, right? And [26:40] two is, you know, the first prime number. That's super interesting, right? And- [26:46] Okay. So one can go on this way and give specific reasons, but I wanna [26:50] prove as a general principle that every number is interesting. And this is [26:54] the proof. Suppose, toward contradiction, that there were some boring numbers. [27:02] Okay? [27:03] - Oh, okay. [27:04] - But if there was an uninteresting number- [27:06] - Yes [27:07] - ...then there would have to be a smallest uninteresting number. [27:11] - Mm-hmm. Yes. [27:13] - But that's a contradiction, because the smallest uninteresting number is a super [27:17] interesting property to have. So therefore- [27:23] - Ah, that's good. [27:24] - ...there cannot be any boring numbers. [27:26] - I'm gonna have to try to find a hole in that proof- because there's a lot of [27:30] baked in in the word interesting, but yeah, that's a beautiful. [27:33] - Right. [27:34] - That doesn't say anything about the transcendental numbers, about the real numbers that you [27:38] just proved from just- [27:39] - That's right [27:39] - ...four natural numbers. [27:40] - Yeah. Okay, should we get back to Cantor's argument, or- [27:42] - Sure. [27:43] You've masterfully avoided the question. Well, you basically said, "I love all [27:46] numbers." [27:47] - Yeah, basically. [27:48] - Is that what you said? [27:49] - Yeah. That was my intention. [27:49] - Back to Cantor's argument. Let's go. [27:51] - Okay, so Cantor wants to prove that [27:55] the infinity of the real numbers is different and [27:59] strictly larger than the infinity of the natural numbers. So the natural [28:03] numbers are the numbers that start with zero and add one [28:06] successively, so zero, one, two, three, and so on. And the real numbers, as [28:10] we said, are the numbers that come from the number [28:14] line, including all the integers and the rationals and the algebraic numbers and [28:18] the transcendental numbers and all of those numbers altogether. Now, [28:21] obviously, since the natural numbers are included in the real numbers, [28:25] we know that the real numbers are at least as large as [28:29] the natural numbers. And so the claim that we want to prove is that [28:34] it's strictly larger. So suppose that it wasn't strictly larger. So [28:40] then they would have the same size. But to have the same size, remember, [28:44] means by definition that there's a one-to-one [28:48] correspondence between them. So we suppose that the real [28:52] numbers can be put into one-to-one correspondence with the natural numbers. [28:57] So therefore, for every natural number N, we have a real number, let's call it R sub N. [29:01] R sub N is the Nth real number on the [29:05] list. Basically, our assumption allows us to think of the real numbers as [29:09] having been placed on a list, R1, R2, and so on. [29:13] Okay, and now I'm going to define the number Z, and it's going to [29:16] be... The integer part is going to be a zero, and then I'm going to [29:20] put a decimal place, and then I'm going to start specifying the digits of this number [29:24] Z. D1, D2, D3, and so on. And what [29:28] I'm going to make sure is that the Nth digit after the [29:32] decimal point of Z is different from the Nth digit of the Nth number on the list. [29:40] Okay? So, to specify the Nth digit of Z, I [29:44] go to the Nth number on the list, R sub N, and I look at its Nth [29:47] digit after the decimal point. And whatever that digit [29:51] is, I make sure that my digit is different from it. Okay? [29:57] And then I want to do something a little bit more, and that is [30:01] I'm going to make it different in a way that I'm never using the [30:05] digits zero or nine. I'm just always using the other digits and not zero [30:10] and it would form a kind of diagonal going down and to the right, and that, [30:41] for that reason, this argument is called the diagonal argument because we're looking at the [30:44] Nth digit of the Nth number, and those exist on a kind of diagonal going [30:48] down. And we've made our number Z [30:52] so that the Nth digit of Z is different from the Nth digit of the Nth number. [30:58] But now it follows that Z is not on the list because [31:04] Z is different from R1 because, well, [31:08] the first digit after the decimal point of Z is different from the first [31:12] digit of R1 after the decimal point. That's exactly how we built [31:15] it. And the second digit of Z is different from the second digit [31:19] of R2 and so on. The Nth digit of Z is different [31:23] from the Nth digit of R sub N for every N. So [31:26] therefore, Z is not equal to any of these numbers R sub N. And [31:32] but that's a contradiction because we had assumed that we had every real number [31:36] on the list, but yet here is a real number Z that's not on the [31:39] list, okay? And so that's the main contradiction. [31:43] - And so it's a kind of proof by construction. [31:45] - Exactly. So given a list of numbers, Cantor's [31:48] proving... It's interesting that you say that actually, because there's a kind of philosophical [31:52] controversy that occurs in connection with [31:56] this observation about whether Cantor's construction is constructive or not. [32:00] Given a list of numbers, Cantor gives us a specific [32:03] means of constructing a real number that's not on the list, is a [32:07] way of thinking about it. There's this one aspect, which I alluded to earlier, but [32:14] some real numbers have more than one decimal [32:16] representation, and it causes this slight problem [32:21] in the argument. For example, the number one, you can write it as 1.0000 [32:27] forever, but you can also write it as 0.999 forever. Those are two [32:34] different decimal representations of exactly the same number. [32:38] - You beautifully got rid of the zeros and the nines. Therefore, we don't need to even consider that, [32:42] and the proof still works. [32:44] - Exactly, because the only kind of case where that phenomenon occurs is [32:48] when the number is eventually zero or eventually nine. And so since our [32:52] number Z never had any zeros or nines in it, it wasn't one of those [32:55] numbers. And so actually, in those cases, we didn't need to do anything special to [32:59] diagonalize. Just the mere fact that our number has a unique representation [33:03] already means that it's not equal to those numbers. So maybe it [33:07] was controversial in Cantor's day more than 100 years ago, but I think it's [33:11] most commonly looked at today as, you know, one of the [33:15] initial main results in set theory, and it's [33:19] profound and amazing and insightful and the beginning [33:22] point of so many later arguments. And this diagonalization [33:26] idea has proved to be an extremely fruitful proof method, [33:31] and almost every major result in mathematical logic [33:35] is using in an abstract way the idea of [33:39] diagonalization. It was really the start of so [33:42] many other observations that were made, including [33:46] Russell's paradox and the halting problem and the recursion [33:50] theorem, and so many other principles are using diagonalization at their core. So... [33:56] - Can we just step back a little bit? [33:58] - Sure. [33:58] - This infinity crisis led to a kind of rebuilding of mathematics. So it'd be [34:06] nice if you lay out the things it resulted in. So one is [34:10] set theory became the foundation of mathematics. All mathematics could now [34:14] be built from sets, giving math its first truly rigorous [34:16] foundation. The axiomatization [34:21] of mathematics, the paradoxes forced mathematicians to develop ZFC and other [34:25] axiomatic systems, and mathematical logic emerged. Gödel, Turing, and [34:31] others created entire new fields. So can you explain what set theory is and, [34:38] how does it serve as a foundation of modern mathematics and maybe even the [34:41] foundation of truth? [34:43] - That's a great question. Set theory really has two [34:47] roles that it's serving. There's kind [34:51] of two ways that set theory emerges. On the one hand, set theory [34:56] is its own subject of mathematics, with its [35:00] own problems and questions and answers and proof [35:04] methods. And so really, from this point of view, set theory is [35:07] about the transfinite recursive constructions or well-founded definitions and [35:14] constructions. And those ideas have been enormously [35:18] fruitful and set theorists have looked into them and [35:22] developed so many ideas coming out of that. But set [35:26] theory has also happened to serve in this other [35:29] foundational role. It's very common to hear things said about [35:33] set theory that really aren't taking account of this distinction between [35:37] the two roles that it's serving. It's its own subject, but it's also serving as a [35:41] foundation of mathematics. So in its foundational role, set [35:45] theory provides a way to think of a collection of things as one thing. [35:49] That's the central idea of set theory. A set is a [35:52] collection of things, but you think of the set [35:56] itself as one abstract thing. So when you form the [36:00] set of real numbers, then that is a set. It's one thing. It's a [36:03] set, and it has elements inside of it. So it's sort of [36:07] like a bag of objects. A set is kind of like a bag of objects. And so we have a [36:11] lot of different axioms that describe the nature of this [36:15] idea of thinking of a collection of things as one thing itself, one abstract thing. [36:20] - And axioms are, I guess, facts that we assume are true, based on which we then [36:27] build the ideas of mathematics. So there's a bunch of facts, axioms about sets [36:34] that we can put together, and if they're sufficiently...... [36:37] powerful, we can then build on top of that a lot of really interesting mathematics. [36:42] - Yeah, I think that's right. So, I mean, the history of the current set [36:46] theory axioms, known as the Zermelo-Fraenkel axioms, came out in the [36:50] early 20th century with Zermelo's idea. I mean, the history is quite [36:54] fascinating because Zermelo in 1904 offered a proof [37:00] that what's called the axiom of choice implies the [37:04] well-order principle. So he described his proof, and that was [37:08] extremely controversial at the time. And there was no [37:12] theory, there weren't any axioms there. Cantor was not working in an axiomatic [37:16] framework. He didn't have a list of axioms in the way that we have for set theory [37:20] now, and Zermelo didn't either. And his [37:24] ideas were challenged so much with regard to the well-order theorem— [37:29] —that he was pressed to produce the theory [37:33] in which his argument could be formalized, and that was the origin of [37:37] what's known as Zermelo set theory. [37:39] - And going to perplexity, the axiom of choice is a fundamental principle in set [37:43] theory which states that for any collection of non-empty sets, it is [37:46] possible to select exactly one element from each set, even [37:50] if no explicit rule to make the choices given. This axiom [37:54] allows the construction of a new set containing one element from each [37:58] original set, even in cases where the collection is infinite [38:02] or where there is no natural way to specify a selection [38:05] rule. So this was controversial and this [38:09] was described before there's even a language for axiomatic systems. [38:14] - That's right. So on the one hand, I mean, the axiom of choice principle is [38:20] completely obvious that we want this to be true, that it is [38:24] true. I mean, a lot of people take it as a law of logic. If you have [38:28] a bunch of sets, then there's a way of picking an element from each of them. [38:31] picking an element from each of them. There's a [38:35] function. If I have a bunch of sets, then there's a function that, [38:39] when you apply it to any one of those sets, gives you an element of that set. [38:43] It's- it's a completely natural principle. I mean, [38:47] it's called the axiom of choice, which is a way of sort of anthropomorphizing the [38:50] mathematical idea. It's not like the function is choosing [38:54] something. I mean, it's just that if you were to make such choices, [38:58] there would be a function that consisted of the choices that you made. [39:02] And the difficulty is that when you- when you can't specify a [39:05] rule or a procedure by which you're making choices, then it's difficult to say [39:09] choices, then it's difficult to say what the function is that you're asserting exists. [39:13] function is that you're asserting exists. You know, you- you [39:17] want to have the view that, well, there is a way of choosing. I don't have an [39:21] easy way to say what the function is, but there definitely is one. [39:25] Yeah, this is the way of thinking about the axiom of choice. [39:28] - So we're going to say the- the- the three letters of ZFC may be a lot on this [39:31] conversation. You already mentioned- [39:33] - Right [39:33] - ...Zermelo-Fraenkel set theory, that's the Z and the F and the C in that is this... [39:37] and the C in that is this... Comes from this axiom of choice. [39:41] - That's right. [39:42] - So ZFC sounds like a super technical thing, but it is the [39:46] set of axioms that's the foundation of modern mathematics. [39:49] - Yeah, absolutely. So one should be aware also that there's huge parts of [39:53] mathematics that don't... That pay attention to whether the axiom of [39:57] choice is being used and they don't want to use the axiom of choice, so they work out [40:01] the consequences that's- that are possible without the axiom of choice or with weakened [40:05] forms of- of Zermelo-Fraenkel set theory and so on. And that's quite [40:09] a- there's quite a vibrant amount of work in that area. I mean, but going back to the [40:13] axiom of choice for a bit, it's maybe interesting to- to give Russell's description [40:21] of how to think about the axiom of choice. So Russell describes, [40:24] this rich person who has a- an infinite closet. And in that closet, he has [40:33] infinitely many pairs of shoes and he tells his butler to [40:40] "Please go and give me one shoe from each pair." [40:43] And- and the butler can do this easily because he can... For any pair of shoes, he [40:47] can just always pick the left shoe. I mean, there's a way [40:51] of picking that we can describe. We always take the left one or [40:55] always take the right one, or take the left one if it's a red shoe and the right one if [40:59] it's a brown shoe or, you know. We can invent rules that would [41:03] result in these kind of choice functions, so we can describe [41:07] explicit choice functions. And for those cases, you don't need the axiom of choice [41:11] you don't need the Axiom of Choice to know that there's a choice function. [41:15] When you can describe a specific way of choosing, then you don't need to [41:18] appeal to the axiom to know that there's a choice [41:21] But the problematic case occurs when you think about the infinite collection [41:25] when you think about the infinite collection of socks that the [41:29] person has in their closet. And if we assume that socks are [41:33] sort of indistinguishable within each pair, you know, they match each other, [41:37] indiscernible, then the- the butler wouldn't have any kind of rule for [41:43] which sock in each pair to pick. And so it's not so clear that he has a way of- [41:52] of producing one sock from each pair [41:55] because... Right? So that's what's at stake, is the question of whether [41:59] you can specify a rule by which the choice function, you know, a rule that it obeys [42:06] that defines the choice function, or whether there's sort of this arbitrary [42:10] choosing aspect to it. That's when you need the axiom of choice to [42:14] know that there is such a function. But of course, as a matter of [42:18] mathematical ontology, we might find attractive the idea that, well, [42:22] look, I mean, I don't- not every way of [42:25] choosing the socks has to be defined by rule. Why should everything that [42:29] exists in mathematical reality follow a rule or a [42:33] procedure of that sort? If I have the [42:37] idea that my mathematical ontology is rich with objects, [42:40] then I think that, that there are all kinds of functions and [42:44] ways of choosing. Those are all part of the mathematical reality that I [42:48] wanna be talking about.... and so I don't have any problem [42:52] asserting the Axiom of Choice. Yes, there is a way of choosing, [42:55] But I can't t- necessarily tell you what it is. [42:59] But in a mathematical argument, I can assume that I fix the choice [43:03] function because I know that there is one. So it's a... The [43:06] philosophical difference between working when you have the Axiom of Choice [43:10] and when you don't is the question of this constructive nature of the [43:14] argument. So if you make an argument and you appeal to the Axiom of Choice, [43:18] then maybe you're admitting that the objects that [43:21] you're producing in the proof are not gonna be constructive. [43:25] You're not gonna be able to necessarily say specific things about them. [43:30] But if you're just claiming to make an existence claim, that's totally fine. Whereas if you have [43:34] a constructive attitude about ma- the nature of mathematics, and you [43:38] think that mathematical claims maybe are only warranted when you can [43:42] provide an explicit procedure for producing the mathematical objects that you're dealing [43:45] with then you're probably gonna wanna deny the axiom of choice and maybe much more. [43:51] - Can we maybe speak to the axioms that [43:55] underlie ZFC? So cone of perplexity, ZFC, or Zermelo-Fraenkel [43:59] set theory with the Axiom of Choice, as we mentioned, is the standard foundation for most [44:03] modern mathematics. It consists of the following main axioms: Axiom [44:07] of Extensionality, Axiom of Empty Set, Axiom of Pairing, Axiom [44:11] of Union, Axiom of Power Set, Axiom of Infinity, Axiom of [44:15] Separation, Axiom of Replacement, Axiom of Regularity, [44:19] and Axiom of Choice. Some of these are quite basic, but it would be nice [44:25] to kinda give people a sense- [44:28] ...of what it means to be an axiom. Like, what kind of basic [44:33] facts we can lay on the table on which we can build some beautiful mathematics. [44:37] - Yeah, so the history of it is really quite fascinating. So, Zermelo introduced [44:41] most of these axioms, I mean, as part of what's now called Zermelo set [44:45] theory, to formalize his proof from the Axiom of [44:49] Choice to the Well-Order Principle, which was an extremely controversial result. [44:53] So in 1904, he gave the proof without the theory, and then he was challenged to [44:57] provide the theory. And so in 1908, he produced [45:01] the Zermelo set theory and gave the proof that [45:05] in that theory, you can prove that every set admits a well ordering. [45:09] And so the axioms on the list, these things like extensionality, express [45:13] the most fundamental principles of the [45:16] understanding of sets that he wanted to be talking about. So for example, [45:20] extensionality says if two sets have the same members, then they're equal. So [45:26] it's this idea that the sets consist of the [45:30] collection of their members, and that's it. There's nothing else that's going on in [45:34] the set. So it's just if two sets have the same members, then they are the same [45:37] set. So it's maybe the most primitive axiom in some respect. [45:44] - Well, there's also, just to give a flavor, there exists a set [45:48] with no elements, called the empty set. For any two sets, there's a [45:52] set that contains exactly those two sets as [45:55] elements. For any set, there's a set that contains exactly the elements of the [45:59] elements of that set, so the union set. And then there's the power [46:03] set. For any set, there's a set whose elements are exactly the [46:07] subsets of the original set, the power set. In the axiom of [46:10] infinity, there exists an infinite set, typically a set [46:14] that contains the empty set and is closed under the operation of adding one more [46:18] element. Back to our hotel example. [46:22] - That's right. [46:23] - And there's more, but this is kind of fascinating. [46:26] Just put yourself in the mindset of people at [46:30] the beginning of this, of trying to formalize set theory. [46:34] It's fascinating that humans can do that. [46:37] - I read some historical accounts by historians about [46:40] that time period, specifically about Zermelo's axioms and his [46:44] proof of the well-order theorem. And the historians were saying never before in the [46:52] history of mathematics has a mathematical theorem been argued [46:56] about so publicly and so vociferously as that theorem of [47:01] Zermelo's. And it's fascinating also because the axiom of choice was [47:08] widely regarded as a kind of, you know, basic principle at first, [47:12] but then when, but people were very suspicious of the well-order theorem because no one could [47:15] imagine a well ordering, say, of the real numbers. And so [47:19] this was a case when Zermelo seemed to be, from principles [47:23] that seemed quite reasonable, proving this obvious untruth. [47:28] And so people were, mathematicians were objecting. But then [47:32] Zermelo and others actually looked into the [47:35] mathematical papers and so on of some of the people who had been [47:39] objecting so vociferously, and found, in many [47:43] cases, that they were implicitly using the axiom of choice in their [47:46] own arguments, even though they would argue publicly against [47:50] it. Because it's so natural to use it because [47:54] it's such an obvious principle in a way. I mean, it's [47:57] easy to just use it by accident if you're not critical enough [48:01] and you don't even realize that you're using the axiom of choice. That's true now, even. [48:05] People like to pay attention to when the axiom of choice is used or not used in [48:09] mathematical arguments, up until this day. It used to be more [48:12] important. In the early 20th century it was very important because people didn't know if it [48:16] was a consistent theory or not, and there were these antinomies arising. [48:20] and so there was a worry about consistency of the axioms. [48:24] but then, of course, eventually, with the result of, of [48:28] Godel and Cohen and so on, they... this consistency question specifically about the [48:32] axiom of choice sort of falls away. We know that the axiom of choice itself [48:36] choice itself will never be the source of inconsistency in set [48:40] theory. If there's inconsistency with the axiom of choice, then it's, it's already [48:44] inconsistent without the axiom of choice. So it's not the cause of [48:47] inconsistency. And so in that... from that point of view, the need to pay [48:51] attention to whether you're using it or not from a consistency point of view is somehow less [48:55] important. But still there's this [48:59] reason to pay attention to it on the grounds of these constructivist [49:02] ideas that I had mentioned earlier. [49:05] - And we should say, in set theory, consistency means that it is impossible to [49:09] derive a contradiction from the axioms of the theory. [49:12] It means that there are no contradictions. That's a... [49:15] - That's right [49:15] - A consistent axiomatic system is that there are no contradictions. [49:19] - A consistent theory is one for which you cannot prove a contradiction from that [49:22] theory. [49:23] - Maybe a quick pause, a quick break, a quick bathroom break. [49:28] You mentioned to me offline we were talking about Russell's paradox and that [49:32] there's a- a nice, another kind of anthropomorphizable proof of [49:37] uncountability. I was wondering if you can lay that out. [49:41] - Oh yeah, sure. Absolutely. [49:42] - Both Russell's paradox and the proof. [49:44] - Right. So we talked about Cantor's proof [49:49] that the real numbers, the set of real numbers is an uncountable infinity, [49:53] it's a strictly larger infinity than the natural numbers. But Cantor [49:57] actually proved a- a much more general fact, [50:00] namely that for any set whatsoever, the power [50:05] set of that set is a strictly larger set. So the power set [50:09] is the set containing all the subsets of the original set. So if you have a set [50:14] and you look at the collection of all of its subsets, then Cantor proved [50:18] that this is- this is a bigger set. They're not [50:22] equinumerous. Of course, there's always at least as many subsets as elements [50:25] because for any element you can make, the- the singleton subset [50:29] that has only that guy as a member, right? So [50:33] there's always at least as many subsets as elements. But the question is [50:37] whether they, whether it's strictly more or not. And so [50:41] Cantor reasoned like this. It's very simple. It's a kind of [50:45] distilling the abstract diagonalization idea [50:48] without being encumbered by the complexity of the real numbers. So, we have a set X, [50:56] and we're looking at all of its subsets. That's the power set of X. [51:00] Suppose that X and the power set of X have the same [51:03] size. Suppose, towards contradiction, they have the same size. [51:07] So that means we can associate to every individual of X a subset. [51:14] And so now let me define a new set. Another set, I'm going to [51:18] define it. Let's call it D. And D is the subset [51:22] of X that contains all the individuals that are not in their set. Every individual [51:30] was associated with a subset of X, and I'm looking at the individuals that [51:34] are not in their set. [51:37] Maybe nobody's like that. Maybe there's no element of X that's like that, [51:41] or maybe they're all like that, or maybe some of them are and some of them aren't. [51:43] It doesn't really matter for the argument. I defined a subset [51:47] D consisting of the individuals that are not in the set that's [51:51] attached to them, but that's a perfectly good subset. And so [51:55] because of the equinumerosity, it would have to be attached to a particular individual, [51:58] you know? And- ...but that... let's call that person, it should [52:06] be a name starting with D, so Diana. [52:10] And now we ask, is Diana an element of D or not? [52:15] But if Diana is an element of D, then she is in her [52:18] set. So she shouldn't be because the [52:23] set D was the set of individuals that are not in their set. [52:28] So if Diana is in D, then she shouldn't be. But if she isn't in [52:31] D, then she wouldn't be in her set. And so she should be in D. [52:35] That's a contradiction. So therefore, the number [52:39] of subsets is always greater than the number of elements for any set. [52:45] And the anthropomorphizing idea is the following. [52:49] I'd like to talk about it this way. For any collection [52:53] of people, you can form more committees from them [52:57] than there are people, even if you have infinetely many people. [53:03] Suppose you have an infinite set of people. And what's a [53:06] committee? Well, a committee is just a list of who's on the committee, basically. [53:10] The members of the committee. So there's all the two-person committees [53:14] and there's all the one-person committees, and there's the universal, [53:17] the worst committee, the one that everyone is on. Okay. The best committee [53:22] is the empty committee. With no members and never meets and so on. Or is the empty [53:27] committee meeting all the time? I'm not sure. [53:29] - Yeah. That's... wow, that's a profound question. [53:32] And does a committee with just one member meet also as a- [53:35] - Yeah, maybe it's always in session. I don't know. [53:38] So the claim is that there are more committees than people. [53:44] Okay. Suppose not. Well, then we could make an association between the [53:48] people and the committees. So we would have every committee [53:52] could be named after a person in a one-to-one way. [53:56] And I'm not saying that the person is on the committee that's named after them, [54:00] or not on it, whatever. Maybe sometimes that happens, sometimes it doesn't. I don't know. [54:04] It doesn't matter. But let's form what I call committee D, which consists of all the [54:10] people that are not on the committee that's named after them. [54:16] Okay. Maybe that's everyone, maybe it's no one, maybe it's half the people. It doesn't [54:20] matter. That's a committee. It's a set of people. And so it has to be named after [54:26] someone. Let's call that person Daniella. So now we ask, is [54:33] Daniella on the committee that's named after her? [54:37] Well, if she is, then she shouldn't be because it was the [54:41] committee of people who aren't on their own committee. [54:45] And if she isn't, then she should be. So again, it's a [54:48] contradiction. So when I was teaching at Oxford, one of my students came up with the [54:55] following different anthropomorphization of Cantor's [54:59] argument. Let's consider all possible fruit [55:03] salads. We have a given collection of fruits. [55:07] You know, apples and oranges and grapes, whatever. And a fruit salad consists of [55:11] some collection of those fruits. So there's the banana, pear, grape salad and [55:15] so on. There are a lot of different kinds of salad. Every set of fruits [55:19] makes a salad, a fruit salad. Okay. And we want to [55:23] prove that for any collection of fruits, even if there are infinitely [55:27] many different kinds of fruit, for any collection [55:31] of fruits, there are more possible fruit salads than there are fruits. [55:38] So if not, then you can put a one-to-one correspondence between the [55:41] fruits and the fruit salads, so you could name every fruit [55:45] salad after a fruit. That fruit might not be in [55:49] that salad, it doesn't matter. We're just... it's a naming, a one-to-one correspondence. [55:53] And then, of course, we form the diagonal salad, which consists [55:58] of all the fruits that are not in the salad that's named after them. [56:04] And that's a perfectly good salad. It might be [56:08] the kind of diet salad, if it was the empty salad, or it might be the universal [56:11] salad [56:12] which had all fruits in it, if all the fruits were in it. Or it might have just some and [56:16] not all. So that diagonal salad would have to be named after [56:20] some fruit. So let's suppose it's named after durian, [56:23] meaning that it was associated with durian in the one-to-one correspondence. And then [56:27] we ask, well, is durian in the salad that it's named after? And if it is, then it [56:35] shouldn't be. And if it isn't, then it should be. And so it's again the same [56:39] contradiction. So all of those arguments are just the same as [56:42] Cantor's proof that the power set of any set is [56:46] bigger than the set. And this is exactly the same logic [56:49] that comes up in Russell's paradox, because Russell is arguing [56:53] that the class of all sets can't be a set, [56:59] because if it were, then we could form the [57:03] the set of all sets that are not elements of themselves. [57:09] So basically, what Russell is proving is that there are more [57:12] collections of sets than elements. Because we can form the [57:18] diagonal class, you know, the class of all sets that are not [57:22] elements of themselves. If that were a set, then it would be an [57:26] element of itself if and only if it was not an element of itself. It's [57:30] exactly the same logic in all four of those arguments. Yeah. [57:34] So there can't be a class of all sets, because if there were, then there would have to be a class of all [57:38] sets that aren't elements of themselves. But that set [57:42] would be an element of itself if and only if it's not an element of itself, which is a [57:46] contradiction. So this is the essence of the Russell paradox. I don't call it the [57:51] Russell paradox. Actually, when I teach it, I call it Russell's theorem. There's no [57:55] universal set. And it's not really [57:58] confusing anymore. At the time, it was very confusing, but now we've absorbed this [58:05] nature of set theory into our fundamental understanding of how sets [58:09] are, and it's not confusing anymore. I mean, the history is fascinating though about [58:13] the Russell paradox, because before that [58:17] time, Frege was working on his monumental work [58:21] undertaking, implementing the philosophy of logicism, which is [58:25] the attempt to reduce all of mathematics to logic. [58:30] So Frege wanted to give an account of all of mathematics in [58:33] terms of logical notions, and he [58:37] was writing this monumental work and had formulated his basic [58:41] principles. And those principles happened to [58:45] imply that for any property whatsoever, you could form the set of objects with that [58:51] property. This is known as the general comprehension principle. And [58:59] he was appealing to the principles that support that axiom, [59:03] throughout his work. I mean, it wasn't just an [59:07] incidental thing. He was really using this principle. And Russell wrote him a letter [59:13] when he observed the work in progress, that there was [59:17] this problem, because if you accept the principle that for any property whatsoever, you can make [59:21] a set of objects with that property, then you could form the set of [59:25] all sets that are not members of themselves. That's just an [59:29] instance of the general comprehension principle. And [59:36] the set of all sets that aren't elements of themselves can't be a set, because if it [59:40] were, then it would be an element of itself if and only if it's not a member of [59:43] itself, and that's a contradiction. [59:46] And so Russell wrote this letter to Frege, and it was just at the moment [59:50] when Frege was finishing his work. It was already at the publishers [59:54] and, you know, in press basically. But it's [59:57] completely devastating. I mean, it must have been such a [60:01] horrible situation for Frege to be placed in [60:04] because he's finished this monumental work, you know, [60:10] years of his life dedicated to this, and Russell finds this [60:15] basically one-line proof of a contradiction in the fundamental principles of [60:20] the thesis that completely destroys the whole system. And [60:27] Frege had put in the appendix of his work a [60:31] response to Russell's letter in which he explained what happened, and he wrote [60:35] very gracefully, "Hardly anything more unwelcome can befall a [60:38] scientific writer than to have one of the foundations of his edifice shaken after the [60:42] work is finished. This is the position into which I was put by a letter from [60:46] Mr. Bertrand Russell as the printing of this volume was nearing [60:49] completion." And then he goes on to explain the matter, it concerns his basic law [60:53] five, and so on, and... [60:54] - It's heartbreaking. I mean, there's nothing more traumatic to [60:58] a person who dreams of constructing mathematics all from logic. [61:02] to get a very clean, simple contradiction. I mean, that's just... [61:08] - You devote your life to this work, and then it's shown to be contradictory, and [61:13] that must have been heartbreaking. [61:16] - What do you think about the Frege project, the philosophy of logic, [61:20] the dream of the power of logic- [61:22] - Right [61:22] - ... to construct a mathematical universe? [61:24] - So, of course, the project of logicism did not die with [61:28] Frege, and it was continued, and, you know, there's a whole [61:31] movement, the neologicists and so on, in contemporary times [61:35] even. But my view of the matter is that, really, we [61:39] should view the main goals of logicism are basically completely fulfilled [61:45] in the rise of set-theoretic foundationalism. I mean, [61:49] When you view ZFC as the foundation of mathematics, and in my view, the principles of [61:56] ZFC are fundamentally illogical in character including the axiom of [62:00] choice, as I mentioned, as a principle of logic. This is a [62:04] highly disputed point of view, though, cause a lot of people take even the axiom of [62:08] infinity as inherently mathematical and [62:12] not logical and so on. But I think if you adopt the view [62:17] that the principles of ZFC have to do with the principles of [62:20] abstract, you know, set formation, which is fundamentally [62:24] logical in character, then it's complete success for [62:28] logicism. So the fact that set theory is able to serve as a foundation [62:32] means that mathematics can be founded on logic. [62:35] - I think this is a good moment to talk about Gödel's incompleteness [62:39] theorems. So, can you explain them and what do they teach [62:43] us about the nature of mathematical truth? [62:47] - Absolutely. It's one of the most profound developments in mathematical [62:51] logic. I mean, the incompleteness theorems is when [62:54] mathematical logic, in my view, first became sophisticated. [62:59] It's a kind of birth of the subject of mathematical [63:03] logic. But to understand the theorems, you really have to start a little [63:07] bit earlier with Hilbert's program. [63:10] because at that time, you know, with the Russell Paradox and so on, there were these various contradictions [63:14] popping up in various parts of set theory and the Burali-Forti [63:18] paradox and so on. And, and Hilbert was famously supportive of set theory. I mean, [63:25] there's this quote of him saying, "No one [63:29] shall cast us from the paradise that Cantor has created for [63:33] us." And what I take him to mean by that is he was [63:37] so captured by the idea of using set theory as a foundation [63:40] of mathematics and it was so powerful and convenient and unifying in a [63:44] way that was extremely important. And he wasn't, he didn't wanna give that [63:48] up, despite the danger of these [63:53] paradoxes, these contradictions, basically, is how some people viewed them. And so, [63:58] - this minefield of paradoxes. Yeah. [64:00] - Right. A minefield. That's a really good way of describing the situation. And [64:03] so Hilbert said, "Well, look, we have to fix this [64:07] problem, you know. We wanna use the set theory foundations, but we want to [64:11] do it in a way that is trustworthy and reliable. We can't [64:15] allow that the foundations of mathematics are in [64:18] question. You know, this is a kind of attitude, I think, that underlies Hilbert [64:24] and the Hilbert program. And so he proposed, "Look, [64:28] we're going to have this strong theory, this set theory that we want to be proving [64:32] our theorems in but I [64:36] I mean, on the one hand, we want it to be as strong as possible. We would [64:40] like it to answer all the questions." There's another [64:44] famous quote of Hilbert in his retirement address where, [64:48] he proclaims, "Wir müssen wissen, wir [64:51] werden wissen." So, "We must know, we will know," in [64:55] which he's very optimistic about the ability of [64:59] mathematics to answer all of the questions of mathematics that [65:05] we have posed. We have all these problems we want to solve and he is saying, [65:09] "We're going to do it. We're going to solve all these problems." So we want to propose this strong theory [65:13] and one has the sense that he had in mind set [65:16] theory in which all the questions are going to be [65:19] answered. Okay? But secondly, we want to combine that with, in a very [65:27] weak arithmetic, purely finitistic theory, we want to prove [65:32] that the reasoning process of the strong theory is [65:36] safe. Okay? So in order to make sense of that point of view, you [65:39] basically have to invent the philosophy of formalism, where we can look at what is a [65:46] proof, what is the nature of mathematical [65:49] reasoning. And on Hilbert's way of thinking about [65:53] this, a proof is basically itself a finitistic kind of object. It's a sequence [66:00] of... If you think about the nature of what a proof is, it's a sequence of [66:04] assertions which can be viewed as sort of sequences of symbols [66:08] that conform with certain rules of logical reasoning. [66:12] And this is a formalist way of understanding the nature of [66:16] proof. So we think about a proof in a kind of syntactic, formal [66:19] way. Even though the contents of those statements might be [66:23] referring to infinite uncountable objects, [66:27] the statements themselves are not infinite uncountable objects. The statements themselves are [66:31] just finite sequences of symbols. [66:33] - So when you think of proof as, maybe it's fair to say, almost like a [66:36] outside of math. It's like, tools operating on math. And then for [66:40] Hilbert, he thought proof is inside the axiomatic system. Something like this. [66:45] - Yeah, that's helpful. [66:46] - That's wild. [66:48] - The main thing about formalism is that you [66:52] think of the process of doing mathematics. You divorce it [66:56] from the meaning of the mathematical assertions, right? So the [67:00] meaning of the mathematical assertions that you make in this infinitary theory [67:04] has to do with these huge uncountable infinities and so on possibly. [67:08] And that's a very sort of uncertain realm maybe and the source of the paradoxes [67:15] and so on in some people's minds. But the reasoning [67:19] process itself consists of writing down sequences of symbols [67:23] on your page and, you know, undertaking or, [67:27] an argument with them which is following these finitary rules. And so, [67:33] if we divorce the meaning of the symbols from just the process of [67:37] manipulating the symbols, it's a way of looking at the nature of mathematics [67:40] as a kind of formal game in which- [67:43] the meaning may be totally absent. I don't think it's necessarily [67:47] part of the formalist view that there is no meaning behind, but rather it's [67:51] emphasizing that we can divorce the meaning of [67:55] the sentences from the process of manipulating those sentences. [67:59] And then Hilbert wanted to prove in this purely finitary [68:02] theory that if we follow the rules of that game, we're [68:06] never going to get a contradiction. [68:09] So those were the two aims of the Hilbert program, is to [68:13] found the strong infinitary theory, probably set [68:16] theory, which is going to answer all the questions. And then [68:20] secondly, prove in the finitary theory that the strong theory is [68:28] safe. In other words, consistent, yeah? [68:31] - What does the word "finitary" in finitary theory mean? [68:34] - Yeah. Well, this is, of course, philosophically contentious, and people [68:38] have different ideas about what exactly it should mean. So there's hundreds [68:42] of papers on exactly that question. But I like to take it just kind of [68:45] informally. I mean, it means that we're talking about finite sequences of [68:49] symbols, and we're going to have a theory, you know, finite [68:52] strings of symbols. A finitary theory would be [68:56] one whose subject matter is about those kinds of things so that we [69:00] can conceivably argue about the nature [69:04] of these finite strings. A proof is just a finite sequence of statements, [69:08] so that every statement is either one of the axioms or follows [69:12] by the laws of logic from the earlier statements in some specified [69:15] manner, like using modus ponens or some other law of logic like that. [69:21] And such that the last line on the list is, you know, the theorem [69:25] that you're proving. So that's what a proof is in this kind of way of thinking. [69:29] To take a specific example, I mean, I always conceive of the, perhaps the [69:33] most natural finitary theory that one would be called upon to [69:37] exhibit would be Peano arithmetic, the theory of Peano arithmetic, which- [69:41] which is a first order theory of the nature of [69:44] arithmetic. But okay, so some people say, "Well, Peano [69:48] arithmetic has these strong first order induction axioms, and there's much, [69:52] much weaker versions of arithmetic, like I-sigma-naught or I-sigma-1 and [69:56] so on, which are even more finitary than Peano [69:59] arithmetic." So different philosophical positions take different [70:03] attitudes about what is, what does it take to be finitary? How finitary do you [70:07] have to be to be truly finitary? [70:10] - So according to Perplexity, Peano arithmetic is a foundational system for [70:13] formalizing the properties and operations of natural numbers using a set of [70:17] axioms called the Peano axioms. Peano arithmetic provides a [70:21] formal language and axioms for arithmetic operations, such as [70:25] addition and multiplication over the natural numbers. The axioms define the [70:29] existence of a first natural number, usually zero or [70:32] one, the concept of a successor function, which generates [70:36] the next natural number, rules for addition and multiplication built from these [70:40] concepts, the principle of induction allowing proofs around all [70:44] natural numbers, and it goes on. So it's a very particular kind of arithmetic [70:48] that is finitary. [70:51] - You know, in my... I view it as finitary, but this is a contentious view. Not everyone agrees with [70:55] that. That's what I was trying to hint at. [70:58] - Okay. I got it. All right. [70:58] - Peano arithmetic is one of the hugely successful theories [71:04] of the natural numbers and elementary number theory. [71:07] Essentially, all of classical number theory, so [71:11] whatever kind of theorems you want to be proving about the prime numbers or [71:15] factorization or any kind of finitary reasoning about [71:19] finite combinatorial objects, all of it can be formalized in [71:22] Peano arithmetic. I mean, that's the basic situation. Of [71:26] course, one has to qualify those statements in light of the Gödel incompleteness [71:30] theorem, but for the most part, the classical number theoretic analysis of [71:37] the finite numbers is almost entirely developable inside Peano arithmetic. [71:45] So if we go back to the Hilbert program, so Hilbert has these two goals: [71:50] produce the strong theory which is going to answer all the questions, and then [71:54] prove by purely finitary means [71:57] that that theory will never lead into contradiction. And one [72:01] can think about, well, the incompleteness theorem should be viewed as a [72:05] decisive refutation of the Hilbert program. It defeats [72:09] both of those goals decisively, completely. But before explaining [72:15] that, maybe one should think about, you know, what if Hilbert had been right? What would [72:19] be the nature of mathematics in the world that Hilbert is telling us to search for? [72:24] - And if I may, going to Perplexity's definition of Hilbert's [72:28] program, it was David Hilbert's early 20th century project to give all [72:32] of classical mathematics a completely secure finitary [72:36] foundation. In essence, the goal was to formalize all of [72:40] mathematics in precise axiomatic systems and then [72:44] prove using only very elementary finitary reasoning [72:48] about symbols that these systems are free of contradiction. [72:51] - Right. Exactly right. Let's imagine what it would be like if he had been [72:55] right. So we would have this finitary theory, [72:59] and it would prove that the strong theory was free of contradiction. [73:04] So we could start enumerating proofs from the strong theory. Right now, we can [73:11] write a computer program that would systematically generate all possible proofs [73:17] from a given theory. And so we could have, like, this theorem [73:27] enumeration machine that would just spit out theorems all day long in such [73:31] a manner that every single theorem would eventually be produced by this device. [73:37] And so if you had a mathematical question of any kind, you could answer it by just [73:45] waiting for either the answer to come out yes [73:48] or from the machine or the answer to come out no. So [73:52] the nature of mathematical investigation in Hilbert's world [73:55] is one of just turning the crank of the theorem enumeration [73:59] machine, devoid of creative thinking or [74:03] imagination, it's just getting the answer from this by rote. [74:07] procedure. So Hilbert, in effect, is telling us, I mean, with his program, that the [74:15] fundamental nature of mathematics is rote computation. I mean, the way I [74:19] think about the Hilbert program seems extremely attractive in the [74:23] historical context of being worried about the antinomies, [74:26] the inconsistencies, and so how can we kind of block them? [74:31] It seems natural, first of all, to have a strong theory that's going to answer [74:35] all the questions, because the idea of logical independence and [74:39] pervasiveness that we now know exists just wasn't, you know, there was [74:46] no known. They didn't know anything like that happening ever. [74:50] And so it's natural to think that it wouldn't happen, and also [74:54] that they would be able to guard against this inconsistency. So it seems like the [74:58] goals of the Hilbert program are quite natural in that historical context. [75:03] But, you know, when you think a little more about what the nature of it would be like, [75:07] it shows you this kind of rote procedure. And now you're saying, well, that [75:11] doesn't seem so unlikely maybe, I mean, in the light of the [75:15] increasing computer power and so on, it's actually maybe turning into [75:19] our everyday experience, where the machines are calculating more and more for [75:23] us in a way that could be alarming. Okay. But, okay, so to talk about the [75:30] alternative to the Hilbert point of view, I mean, if he's [75:33] wrong, then what is the nature of mathematical reality? Well, it would mean [75:37] that we couldn't ever maybe, for the first goal, we [75:41] couldn't ever write down a theory that answered all the [75:44] questions. So we would always be in [75:48] a situation where our best theory, even the infinitary theories, [75:55] would have questions that they stumble with and are unable to answer. [75:59] Independence would occur. But then also, because of [76:03] the failure of the second goal, we would also have to be [76:07] constantly worrying about whether our theories were consistent or not, and we wouldn't [76:11] have any truly convincing means of [76:14] saying that they were free from contradiction. And [76:18] the fact of Gödel's Incompleteness Theorem shows that that is exactly the nature of [76:26] mathematical reality, actually. Those are the two incompleteness theorems. [76:30] So the first incompleteness theorem says you cannot write [76:33] down a computably axiomatizable theory that answers all the [76:37] questions. Every such theory will be incomplete, [76:40] assuming it includes a certain amount of arithmetic. And [76:44] secondly, no such theory can ever prove its own consistency. So not only is [76:48] it the case that the finitary theory can't prove the consistency of the [76:51] strong infinitary theory, but even the infinitary theory can't prove [76:55] its own consistency, right? That's the second incompleteness [76:59] theorem. And so it's, in that sense, a decisive takedown of the Hilbert [77:05] program, which is really quite remarkable, the [77:09] extent to which his theorem just really answered that [77:13] whole puzzle. It's quite amazing. [77:17] I mean, there's another aspect, kind of easy to think about. [77:21] I mean, if you're wondering about theories that prove their [77:25] own consistency, then, I mean, would you trust a theory [77:29] that proves of itself that it's consistent? I [77:33] mean, that's like... it's like the used car salesman [77:37] telling you, "Oh, I'm trustworthy." I mean, it's not a reason [77:41] to trust the used car salesman, is it? Just because he says that. [77:45] So similarly, if you have a theory that proves its own consistency, well, even an [77:49] inconsistent theory would prove its own consistency. And so it doesn't [77:53] seem to be a logical reason to believe in the consistency, if you have a [77:57] theory that proves itself consistent. [77:59] - Just for clarification, you used the word theory. [78:03] Is it, in this context, synonymous with axiomatic system? [78:07] - Right. So in mathematical logic, "theory" is a technical term. [78:11] And it means any set of sentences in a formal language. And so [78:15] if you say axiomatic system, it's basically synonymous to my [78:19] usage with theory. So a theory means, you know, the [78:22] consequences of a set of axioms or... People are sometimes unclear on whether they just mean [78:26] the axioms or the consequences of the axioms, but... [78:29] - So theory includes both the axioms and the consequences of the [78:32] axioms, and you use it interchangeably and the context is supposed to [78:36] help you figure out which of the two you're talking about? The axioms [78:40] or the consequences? Or maybe to you, they're basically the same? [78:44] - Yeah, well, they're so closely connected, although all the features aren't the same. [78:47] So if you have a computable list of axioms for a theory, then you [78:55] can start enumerating the consequences of the [78:59] axioms, but you won't be able to computably decide [79:02] whether a given statement is a consequence or not. You can enumerate the [79:06] consequences, so you can semi-decide the [79:10] consequences, but you won't be able to decide yes or no whether a given statement [79:14] is a consequence or not. [79:17] So it's the distinction between a problem being computably decidable and a [79:21] problem being computably enumerable, which, [79:24] was made clear following the work of Turing and others [79:28] that came from that. I mean, so that's one difference between the list of [79:32] axioms of the theory and the theory itself. The axioms could [79:36] be... You can decide, maybe computably, whether something is an axiom or not, but [79:40] that doesn't mean that you can decide computably whether or not something is a theorem [79:44] or not. Usually, you only get to decide the positive [79:47] instances. If something is a theorem, you will eventually come to recognize that, but if something isn't [79:51] a theorem, maybe at no point will you be able to say, "No, that's not a theorem." [79:56] - And that's of course connected to the halting problem. [79:58] ...and all of these contradictions and paradoxes are [80:02] all nicely, beautifully interconnected. [80:06] So can we just linger on Gödel's incompleteness theorem? [80:09] You mentioned the two components there. [80:12] You know, there's so many questions to ask, like what is the difference between [80:15] provability and truth? What is true and what [80:19] is provable? Maybe that's a good line to draw. [80:21] - Yeah, this is a really core distinction that [80:27] it's fascinating to me to go back and read [80:32] even the early 20th century people before Gödel and Tarski, [80:38] and they were totally sloppy about this distinction [80:41] between truth and proof. It wasn't clear at all [80:45] until Gödel, basically. Although even as late as [80:49] Bourbaki has the kind of confusion in this [80:52] foundational work. So, this standard graduate-level [80:56] textbook used in France in the presentation of logic, they are conflating truth and [81:03] proof. To be true for them means to be provable. So, in [81:07] the early days, maybe it wasn't clear enough that the concept of truth [81:11] needed a mathematical investigation or [81:15] analysis. Maybe it was already taken to be fully clear. [81:19] But because of the incompleteness theorem, we realized that actually there's quite [81:23] subtle things happening, right? And so, why don't we talk about [81:26] this distinction a bit? To me, it's absolutely core and fundamental [81:30] to our understanding of mathematical logic now. [81:34] This distinction between truth and proof. So, truth is [81:41] on the semantic side of the syntax-semantics dichotomy. [81:44] Truth has to do with the nature of reality. I [81:48] mean, okay, when I talk about reality, I'm not talking about physical reality. [81:52] I'm talking about mathematical reality. So, we have a concept of something being [81:56] true in a structure, a statement being true in a mathematical structure. [82:00] Like maybe you have the real field or something, and you want to know, does it satisfy this [82:04] statement or that statement? Or you have a group of some kind, or maybe [82:08] you have a graph. This is a particular kind of mathematical structure [82:12] that has a bunch of vertices and edges, and you want to know [82:16] does this graph satisfy that statement? And [82:19] Tarski gave this absolutely wonderful account of the [82:23] nature of truth in what's now known as the disquotational [82:27] theory of truth. And what Tarski says is the sentence, "Snow is white," [82:35] is true if and only if snow is white. And what he means by that is, look, to say [82:46] truth is a property of an assertion, so we can think of the assertion as it [82:51] syntactically. So, the sentence is true [82:57] if and only if the content of the sentence is the case. You [83:00] know? So, the sentence, "Snow is white," you know, in quotations is true, that [83:08] just means that snow is white. And [83:12] that's why it's called the disquotational theory because we remove the quotation marks. [83:16] from the assertion, right? And you can use this idea of [83:20] disquotation to give a formal definition of truth in a [83:24] mathematical structure of a statement in a formal language. So, for example, if I [83:28] have a formal language that allows me to make atomic statements [83:31] about the objects and relations of the [83:35] structure, and I can build up a formal language with, you know, [83:38] with the logical connectives of "and" and "or" and [83:41] "implies" and "not" and so on, and maybe I have quantifiers, right? Then, [83:46] for example, to say that the structure satisfies phi [83:50] and psi, that that single statement, phi [83:53] and psi, I'm thinking of that as one statement, just means that it satisfies phi [84:00] and it satisfies psi. And if you notice what happened there, [84:06] I... At first, the 'and' was part of the sentence inside the [84:10] sentence, but then in the second part, I was using the word [84:14] 'and' to refer to the conjunction of the two conditions. So- [84:17] - Yeah, it has the disquotation. [84:18] - Yeah, it has the disquotation. [84:20] And so this idea can be done for all the logical connectors and quantifiers and [84:24] everything. You're applying Tarski's idea of disquotation, [84:28] and it allows you to define by induction the truth of any [84:32] assertion in a formal language inside any mathematical structure. And [84:36] so to say that a sentence is true, first of all, it's ambiguous [84:40] unless you tell me which structure you're talking about it being true in. [84:45] And so maybe we have in mind the standard model of arithmetic [84:49] or something with the natural numbers and the arithmetic structure, and I want to know is a given statement [84:53] true in that structure. Then we have a formal definition of what that means [84:56] according to the Tarski recursive definition of truth. Okay, that's [85:04] truth. Proof, on the other hand, is, you know, in [85:08] this Hilbert way of thinking, we can develop proof theory. What is [85:12] a proof for a mathematician, for a mathematical logician? A [85:15] proof is a certain sequence or arrangement of sentences in the formal language that [85:22] accord with the logical rules of a proof [85:26] system. So there are certain modes of reasoning that are [85:29] allowed. So if you know A and you know A implies B in [85:33] the proof, then at a later step you're allowed to [85:37] write B as a consequence. So if you know A [85:41] and you know A implies B, those are both two statements that are known, then [85:45] you can deduce B as a consequence according to the rule of modus [85:49] ponens. This is the rule of modus ponens. And, you know, there are a lot of other [85:53] rules. Some people would call this implication elimination. There are [85:57] different kinds of proof systems. There are a lot of different formal [86:01] proof systems that exist that are studied by the proof theorists, and all of them have [86:05] the property that they're sound, which means [86:09] that if the premises of the argument are all [86:13] true in a structure and you have a proof to get a [86:16] conclusion, then the conclusion is also true in that structure. So [86:20] that's what it means to be sound. Proofs preserve truth. They're truth- [86:26] preserving arguments. Okay? But also the proof systems are [86:33] also generally complete. They're both sound and complete, and complete [86:37] means that whenever a statement is a consequence, a logical consequence of some [86:44] other statements, which means that whenever the assumptions are true, then [86:48] then the consequence is also true in the structure. [86:52] So whenever you have a logical consequence, then there is a proof of [86:55] it. Okay? And the proof systems generally [86:59] have both of those properties; they're sound and complete. There's a third property a lot of logicians [87:03] talk about [87:04] sound and complete, sound and complete this, sound and complete that. But actually, there's a hidden [87:08] third adjective that they should always be talking about in any such case, which is [87:13] that you should be able to recognize whether or [87:17] whether or not something is a proof or not. So there's a computable aspect [87:22] to the proof systems. We want to be able to recognize whether something is a proof. [87:25] It should be computably decidable whether a given sequence of statements is a proof [87:29] or not. So we don't want a proof system in which [87:33] someone claims to have a proof, but we can't check that fact, whether [87:37] it's a proof or not. We want to be able to correctly adjudicate [87:43] all claims to having a proof. [87:46] - Yeah. A mathematician comes to mind that said he has a proof, but the margins are [87:50] too small [87:51] - That's right. [87:51] - to continue. [87:52] - Exactly. So [87:53] - So that doesn't count as a proof. [87:55] - Yeah. So generally, all the classical proof systems that are used are sound [87:59] and complete and also computably decidable in the sense that we can decide whether [88:02] something is a proof or not. [88:04] - So what is, again, the tension between truth and proof? [88:08] Which is more powerful, and how do the two interplay [88:12] with the contradictions that we've been discussing? [88:15] - Right. So the incompleteness theorem is the question whether we [88:19] could, say, write down a theory [88:22] for arithmetic. Say, for the standard model of arithmetic where we have the natural [88:26] numbers and plus and times and zero, one, and less than, and so on. [88:30] In that formal language, we can express an enormous number of [88:34] statements about the nature not only of arithmetic, but actually by [88:38] various coding methods, we can express essentially all of finite [88:41] mathematics in that structure. So the question would be, can [88:45] we write down a computable list of axioms that will answer [88:49] all those questions by proof? In other words, we want to [88:53] have a complete theory, a theory of arithmetic that proves all and only the true [89:00] statements. That would be the goal. Hilbert would love that. I mean, that would [89:04] be supportive of Hilbert's program to have such a complete [89:07] theory of arithmetic, and Godel proved that this is [89:11] impossible. You cannot write down a computable list of axioms that is complete [89:15] in that sense. There will always be statements... If the theory is [89:19] consistent, there will always be statements that you cannot prove and you cannot [89:23] refute. So they are independent of that theory. [89:26] - How traumatic is that, that there are statements that are independent from the theory? [89:30] - I mean, my view is that this isn't traumatic at all. This is rather [89:38] completely eye-opening in terms of our [89:42] understanding of the nature of mathematical reality. I mean, we're not... [89:49] We understand this profound fact about our [89:53] situation with regard to mathematical truth. [89:57] The incompleteness theorem tells us, look, we just can't write down a list of [90:01] axioms that is going to be consistent and it's going to answer all the questions. [90:05] It's impossible. And so I don't think of it as trauma. [90:09] I just think, look, this is the nature of mathematical reality and it's good that [90:12] we know it, and so now we need to move on from that. And, you know, [90:16] do what we can in light of that. [90:19] - Is it fair to say that in general it means if I give you a [90:22] statement, you can't know if your axiomatic system would be able to prove it? [90:31] - That's right. In general, you cannot. The provability problem, [90:35] we can formulate it as a decision problem. Given a theory and given a [90:38] statement, is that statement a consequence of that theory? Yeah. [90:42] This is one of the most famous decision problems. In fact, the very first one, [90:46] because it's equivalent to the Hilbert-Ackermann [90:49] Entscheidungsproblem, which is also appearing in the title of [90:53] Turing's 1936 paper that was so important for computability theory. So, it's a [91:01] formulation of the Entscheidungsproblem. Does a given theory [91:05] have a given statement as a logical consequence? Which, because [91:09] of Gödel's completeness theorem, not his incompleteness theorem, but his earlier [91:13] completeness theorem, Gödel had proved that the proof systems that they [91:17] studied did have this completeness property that I mentioned. So provability [91:21] is the same as logical consequence. And this is an undecidable decision [91:25] problem. Turing proved and we now know it's equivalent to the Halting Problem. [91:30] - Can you describe the Halting Problem? Because it's a thing that shows up in a [91:34] very useful and, again, traumatic way through a lot of computer [91:38] science, through a lot of mathematics. [91:39] - Yeah. The Halting Problem is expressing a fundamental [91:43] property of computational processes. So, [91:47] given a program, or maybe we think of it as a program together with its input, [91:51] but let me just call it a program. So given a program, we could run that [91:54] program, but I want to pose it as a decision [91:58] problem. Will this program ever complete its [92:01] task? Will it ever halt? And the Halting Problem is the question, given [92:05] a program, will it halt? Yes or no? And, of course, for [92:13] any one instance, the answer's either yes or no. That's not what we're talking [92:16] about. We're talking about whether there's a computable procedure to answer [92:20] all instances of this question. So, it's a decision problem is [92:24] given as a scheme of instances for all possible programs that you could ask [92:28] about. What I want to know is, is there a computable procedure that will answer [92:32] those questions? [92:34] And it turns out the answer's no. The Halting Problem is computably [92:37] undecidable. There is no computable procedure that will correctly [92:41] answer all instances of whether a given program will halt. And of course, we can [92:48] get half the answers in the sense that [92:52] you give me a program and you say, "Will this halt?" And I could take that [92:56] program and I could run it. [92:59] And I could keep running it, and maybe in a week, it would [93:02] halt. And at that time, I could say, "Yes, it [93:05] halted." So I can get the yes answers correctly for halting, all the yes answers. [93:13] But the problem is [93:17] if it didn't halt yet, like maybe I waited, you know, a thousand years [93:21] and it still hasn't halted, [93:23] I don't seem entitled to say, "No, it's not going to halt." Yet, because [93:27] maybe in a thousand and one years, it'll halt. And so at no point can I [93:31] seem to say, "No." In order to say, "No, it won't ever halt," it [93:35] seems like I would have to really understand how the program [93:39] worked and what it was doing. [93:41] So giving the "yes" answers was sort of trivial. You didn't have to understand it. You just needed [93:45] to run it, which is a kind of rote task. But to give the "no" answers, [93:49] you need to have a kind of deep insight into the nature of the program and what it's [93:53] doing in such a way that you would understand it and be able to see, "Oh, no, I can [93:58] see this program is never gonna halt." Because, you know, it's a much more [94:02] difficult task to say, "No, it won't halt," than it is to say, "Yes, [94:06] it halted because I ran it and it halted." And it turns [94:10] out to be impossible to have a computable procedure that gives [94:14] the "no" answers, you know? And the argument is not very difficult. Should we do it? [94:18] - Yes, let's do it. [94:19] - Okay. Suppose toward contradiction. I mean, all these proofs are by [94:23] contradiction, and this argument is going to be a diagonal argument in the same [94:27] style as the Russell argument and the Cantor argument and [94:30] Gödel's argument that we haven't talked about yet. So many diagonal [94:34] arguments come in. So [94:37] suppose towards contradiction that we had a procedure for determining whether a given program [94:41] halted on a given input. Now, let me describe. I'm gonna use that procedure [94:48] as a subroutine in the following process. And [94:52] my process, let's call it Q, process Q, and it takes as input [94:57] a program P, okay? And the first thing it does is it asks that subroutine, [95:04] "Hey, would P halt if I ran it on [95:08] P itself?" Okay, that's the diagonal part because we're applying P to P, right? [95:14] Okay, so I'm describing program Q, and program Q takes as input [95:18] P, which is itself a program. And the first thing it does is it asks [95:22] the halting subroutine program, "Would P halt on [95:25] P?" And if the answer comes back from the subroutine, [95:29] "Yeah, that would halt," then what I do in program Q [95:34] is I immediately jump into an infinite loop. So I don't [95:37] halt. If P halts on P, I don't halt. [95:41] But if the answer came back, "No, P is never gonna halt on P," then [95:45] I halt immediately. Okay, so and that's it. I've described what Q does. [95:53] And the thing about Q is that Q's behavior on P was the opposite of P's [96:00] behavior on P. I mean, that's how we designed Q specifically so that Q on P [96:09] had the opposite behavior as P on P. Okay, so [96:13] now, of course, what do we do? Well, the same thing that [96:16] Russell did and so forth, and Cantor, we ask, "Well, what would Q do on [96:23] Q?" And because of this opposite behavior, [96:28] Q would halt on Q if and only if Q does not halt on [96:31] Q, which is a contradiction, because Q has to have the opposite behavior on [96:35] Q than Q does, but that's just contradictory. [96:38] - What a beautiful proof. Simple. [96:39] - It's absolutely beautiful. Yeah, I agree. And it's following the [96:43] same logic of Russell and Cantor. I mean, going back to [96:47] Cantor basically, because Russell is also quoting Cantor in [96:50] Cantor basically, because Russell is also quoting Cantor in his letter to Frege. So, therefore, the [96:54] conclusion is that the halting problem is not computably [96:58] decidable. And now we can immediately prove Godel's [97:02] decidable. And now we can immediately prove Gödel's theorem using this, actually. It's an immediate consequence. So why don't we just do that? [97:06] I view this as the simplest proof [97:08] I view this as the simplest proof of Gödel's theorem. You don't need the Gödel sentence to [97:12] prove Gödel's theorem. You can do it with the halting problem. So, suppose [97:19] that we could write down a computable axiomatization of all [97:23] that we could write down a computable axiomatization of all of the true facts of elementary mathematics, meaning arithmetic [97:29] and finite combinatorial things such as Turing [97:33] and finite combinatorial things such as Turing machine computations and so on. So in fact, all those [97:37] finite combinatorial processes are formalizable inside arithmetic with the [97:40] finite combinatorial processes are formalizable inside arithmetic with the standard arithmetization coding process. But let [97:44] me just be a little bit informal and say suppose we could write down a complete [97:48] me just be a little bit informal and say, suppose we could write down a complete theory of elementary finite mathematics. [97:52] So we have a, an axiomatization of that theory. [97:56] So we have an axiomatization of that theory. Then we could produce all possible theorems from those [98:00] axioms in the way that I was describing earlier with [98:03] axioms in the way that I was describing earlier with Hilbert's program. I mean, if we had a complete theory of elementary [98:07] mathematics, we could construct a theorem enumeration machine that [98:11] mathematics, we could construct a theorem enumeration machine that produced all the theorems and only the theorems from that [98:15] theory.... so now, I have this theorem enumeration device on my desk, and I announce [98:22] theory. So now I have this theorem enumeration device on my desk, and I announce that I'm open for business to solve the halting problem. So you give me a program [98:26] and input that you wanna run that program on, [98:29] and input that you want to run that program on, and I'm going to answer the halting problem. And the way I'm going to do it is I'm just [98:33] gonna wait for the [98:35] going to wait for the statement coming out of the theorem enumeration device that asserts either that [98:39] P does halt on that input or I wait for the statement that P does not [98:43] P does halt on that input or I wait for the statement that P does not halt on that input. But one of them's going to happen because it was a [98:47] complete theory that was enumerating all the true statements of elementary [98:50] complete theory that was enumerating all the true statements of elementary mathematics. So therefore, if I had such a system, I could solve the halting [98:54] problem, but we already proved that you cannot solve the halting problem, [98:58] problem, but we already proved that you cannot solve the halting problem, so therefore you cannot have such a complete theory of [99:02] arithmetic. So that proves Gödel's theorem. [99:05] - Maybe to take a little bit of a tangent, can you speak... You've written a wonderful book about proofs and the art of mathematics. [99:09] So what can you say about proving stuff in mathematics? What is the process of [99:13] say about proving stuff in mathematics? What is the process of [99:17] proof? What are the tools? What is the art? What is the science of [99:20] proving things in mathematics? [99:22] - proving things in mathematics? So this is something that I find so wonderful to teach young [99:26] mathematicians who are learning how to become mathematicians and [99:30] mathematicians who are learning how to become mathematicians and learning about proof, and I wrote that book when I was teaching such a [99:34] proofwriting class in New York. [99:37] proofwriting class in New York. So many universities have such a course, the proofreading course, which is usually [99:41] taken by students who have learned some mathematics. [99:45] taken by students who have learned some mathematics. Usually, they've completed maybe the calculus sequence and are making the kind of [99:48] transition to higher mathematics, which tends to involve [99:52] much more proof, and it's a kind of challenging step for them. [99:56] Many math departments have this kind of course on proofwriting where the [100:00] students would get exposed to how to write proofs. I wasn't [100:04] happy with most of the other books that exist for those [100:08] kind of courses, and the reason was that they were so often so dull because [100:15] they would concentrate on, like, these- [100:20] totally uninteresting parts of what it's like to write a [100:23] proof, these kind of mechanistic [100:26] procedures about how to write a proof. You know, if you're going to prove an [100:30] implication, then you assume the hypothesis and argue for the conclusion, and so on. [100:34] And all of that is true and fine and that's good to know, except if that's all that you're [100:38] saying about the nature of proof, then I don't think you're really [100:42] learning very much. So I felt that it was possible to have a [100:46] much better kind of book, one that was much more [100:49] interesting and that had interesting theorems in [100:53] it that still admitted of elementary proof. So I wrote this [100:57] book and tried to fill it with all of the [101:01] compelling mathematical statements with very elementary [101:05] proofs that exhibited lots of different proof styles in [101:09] it. And so, I found that the students appreciated it a lot. [101:12] - We should say, we dedicate the book to my students, may all their [101:16] theorems be true, proved by elegant arguments that flow effortlessly from [101:20] hypothesis to conclusion while revealing fantastical mathematical beauty. [101:27] Are there some interesting proofs that maybe illustrate, [101:33] for people outside of mathematics or for people who just take math classes- [101:37] - Right [101:37] - ...in high school and so on? [101:39] - Yeah, let's do a proof. There's one in the book. [101:41] We can talk about it. I think it's a nice problem. It's in [101:44] the discrete math, yeah, the 5.1, that one, [101:48] more pointed at than pointing. Okay. So this is the [101:52] following problem. Suppose you're gathered with some [101:55] friends, you know, in a circle, and you can point [101:59] at each other however you want, or yourself, whatever, it doesn't [102:02] matter, and you can point at more than one person, you know, use all your fingers or [102:06] your feet or whatever you want. So maybe you point at three of your friends or [102:10] something and they point at two or three of their friends or whatever, and one person [102:14] is pointing at 10 people and somebody isn't pointing at anybody maybe, or and various [102:18] people are pointed at also, right? So the question is, could we arrange a pattern of [102:24] pointing so that everyone was more pointed at [102:30] than they are pointing at others? So in other words, maybe [102:33] there's seven people pointing at me, but I'm only pointing at five people and [102:37] maybe there's, you know, 20 people pointing at you, [102:41] but you're only pointing at 15 people or something like that, right? So I want to [102:45] know. There's a similar question on Twitter. [102:49] For a group of people on Twitter, could you arrange [102:54] that everyone has more followers than following? Yeah, it's the same question. [103:00] Mathematically, it's identical. [103:02] Although, I don't know, it's not identical, because I said you could point at yourself, [103:06] and I think that's not... Can you follow yourself? [103:09] - No, I don't think so, no. [103:10] - I don't think you can. Okay. So can you arrange it [103:13] so that everyone is more pointed at than pointing? And in my book, [103:17] I give a couple of different proofs of this. I think I give an induction proof [103:21] and then there's another proof. I think there's three different proofs in there. [103:25] But why don't we just talk about my favorite proof? [103:28] Suppose it were possible to arrange that we're all more pointed at than pointing, [103:32] okay? Now what we're going to do, we're going to agree, [103:36] we're going to give a dollar to everyone that we're pointing at. [103:40] Okay? And so what happens? Everybody made money, [103:46] because I was pointed at by more people than I'm pointing, so I got [103:50] $10, but I only paid out $7. And similarly, you [103:54] got paid $20, but you only paid out $15. So, [103:57] if everyone is more pointed at than pointing, then everyone makes money. [104:01] But it's obviously impossible for us to make money as a group by just trading [104:05] money with ourselves. [104:07] And therefore, it can't be possible that we're all more pointed at than pointing. [104:13] And this proof illustrates something. It's one of my habits that I [104:16] suggest in the book: to anthropomorphize your mathematical ideas. [104:22] You should imagine that the mathematical objects [104:26] that are playing a role in your question are [104:29] people, or active, somehow, animals, or [104:32] something that maybe have a will and a goal and so on. [104:36] This is this process of anthropomorphizing. [104:40] And it often makes the problems easier to understand because we all [104:44] are familiar with the fact that it's difficult to make money, [104:48] and the proof is totally convincing because of our knowledge that [104:52] we can't make money as a group by trading [104:56] dollars between us, you know, without any new money coming into the group. [105:01] But that by itself is actually a difficult [105:04] mathematical claim. I mean, if someone had to [105:07] prove that you can't make money by trading within a [105:11] group, you know, it can't be that everyone in the group [105:15] makes money just by shifting money around in the group. Maybe you think that's [105:19] obvious, and it is obvious if you think about money. But if you had asked the [105:22] question, you know, about mathematical functions of a certain kind and so on, [105:26] then maybe it wouldn't be as clear as it is when you're talking about this [105:30] money thing, because of [105:33] we can build on our human experience about the difficulty of getting [105:37] money and, you know, or other resources. It doesn't have to be money, it could be candy, [105:41] whatever. You know, we just know that you can't easily get [105:45] more things in that kind just by trading within a group. [105:48] - And we should say that sometimes the power of proof is such that the [105:52] non-obvious can be shown, and then over time that becomes obvious. [105:56] So in the context of money, [105:58] or social systems, there's a bunch of things that are non-obvious. [106:01] And the whole point is that proof can guide us [106:05] to the truth, to the accurate description [106:09] of reality. We just proved a property of money. [106:14] - It's interesting to think about, well, what if there were infinitely many [106:18] people in your, in your group? Then it's not true anymore. [106:22] The theorem fails. In fact, you can arrange that everyone is strictly more [106:26] pointed than pointing. And also, you can if everyone has even just one dollar bill— [106:35] ...then you can arrange that afterwards everyone has infinitely many dollar [106:39] bills. Cause in terms of cardinality, that's the same. It's just, say, countable infinity in [106:42] each case. If you had countably many friends and everyone has one dollar bill, then you can arrange [106:46] a pattern of passing those dollar bills amongst each other so that afterwards [106:50] everyone has infinitely many dollar bills. What you need is for each person [106:54] to be attached to, you know, one of the train cars or [106:58] something. So, think of everyone as coming from Hilbert's train, [107:03] but also think of them as fitting into Hilbert's Hotel. So just have [107:06] everyone on the Nth car give all their [107:10] money to the person who ends up in the Nth room. So they each [107:14] give one dollar to that person. So afterwards, that person has infinitely many dollars, but [107:18] everyone only paid out one dollar. So it's a way of making it happen. [107:23] - To what degree, sticking on the topic of infinity, [107:27] should we think of infinity as something real? [107:33] - That's an excellent question. I mean, a huge part of the philosophy of [107:37] mathematics is about this kind of question: what is the nature of [107:41] the existence of mathematical objects, including infinity? [107:45] But I think asking about infinity specifically is [107:49] not that different than asking about the number five. What is— [107:53] ...what does it mean for the number five to exist? What are the numbers [107:57] really, right? This is maybe one of the fundamental questions of mathematical [108:02] ontology. I mean, there's many different positions to take on the question of the nature of [108:06] the existence of mathematical objects or abstract objects in [108:10] general. And there's a certain kind of conversation that sometimes happens [108:14] when you do that, and it goes something like this. Sometimes people find it [108:21] problematic to talk about the existence of abstract objects [108:25] such as numbers, and there seems to be a kind of wish that we [108:29] could give an account of the existence of numbers or other [108:32] mathematical objects or abstract objects that was more [108:35] like, you know, the existence of tables and chairs and rocks and so on. [108:42] And so there seems to be this desire to reduce mathematical existence to [108:49] something, you know, that we can experience physically in the real [108:53] world. But my attitude about this attempt [109:00] is that it's very backward, I think, because [109:06] I don't think we have such a clear understanding of the nature of [109:10] physical objects, actually. I mean, we all have experience [109:14] about existing in the physical world, as we must, because we do [109:18] exist in the physical world, but I don't know of any [109:24] satisfactory account of what it means to exist [109:27] physically. I mean, if I ask you, say, "Imagine a certain kind of [109:35] steam locomotive," you know, and I describe the engineering of [109:39] it and the weight of it and the nature of the gear linkages and [109:45] you know, and I show you schematic drawings of the whole design and so [109:49] on and, you know, we talk in detail about every single detailed [109:52] aspect of this steam locomotive. But then suppose [109:56] after all that conversation, I say, "Okay, now I would like [110:00] you to tell me what would it mean for it to exist physically, I mean, as [110:04] opposed to just being an imaginary steam locomotive?" Then [110:08] what, what could you possibly say about it? I [110:12] mean, except by saying, "Oh, I just mean that it exists in the physical world." But what does that mean? [110:16] That's the question, right? It's not an answer to the question. That is the question. [110:20] So I don't think that there's anything sensible that [110:23] we can say about the nature of physical existence. It is a profound [110:27] mystery. In fact, it becomes more and more mysterious [110:31] the more physics we know. I mean, back in, say, [110:35] Newtonian physics, one had a picture of the nature of physical objects [110:39] as, you know, little billiard balls or something, or maybe they're infinitely divisible or something [110:43] like that. Okay, but then this picture is upset with the [110:47] atomic theory of matter. But then that picture's upset [110:51] when we realize that the atoms actually can be split and consist of electrons and [110:55] protons and neutrons and so on. But then that picture's upset [110:58] when we realize that those things themselves are built out of quarks and leptons and so on, and [111:02] who knows what's coming. Furthermore, all of those things, the nature of their [111:06] existence is actually as wave functions in [111:10] you know, some cloud of probability and so on. So it just becomes [111:14] more and more and more mysterious the more we learn, and not at all [111:18] clarifying. So the nature of what it means to [111:22] say that, you know, there's an apple on my [111:25] desk, and to give an account of what that physical existence [111:29] really is at bottom, I think, is totally absent. Whereas we [111:33] do seem to have a much more [111:36] satisfactory account of the nature of abstract existence. I mean, I [111:40] can talk about the nature of the empty set. You know, this is the [111:44] predicate which is never true or something like that. I can talk [111:48] about those kind of logical properties or the [111:51] singleton of the empty set and so on. I mean, of course, it's very difficult if you go very [111:56] far with it, but the point is that it doesn't get more and more mysterious. The more that you [112:00] say, it becomes only more and more clear. So it seems to me that, [112:07] we don't really have any understanding of what the [112:11] physical world is as opposed to the abstract world, and it's the [112:15] abstract world where existence is much more clear. [112:19] - It is very true [112:21] that we don't know anything about the soda bottle or the steam locomotive just because we can [112:25] poke at it. Again, we anthropomorphize, and that actually gets us into [112:29] trouble sometimes because I'm not feeling the quantum mechanics when [112:33] I'm touching it. [112:34] - That's right. [112:34] - And therefore, it's easy to forget and feel like this is real and [112:41] mathematical objects are not, but you're making the opposite argument. [112:44] When you draw a distinction between numerals and numbers, which numerals are [112:48] the representation of the number on the page, and so on, [112:52] but could you say that a number is real? Do numbers exist? [112:57] - I happen to think so. I mean, I'm on the side of realism in [113:01] mathematics, and I think that these abstract objects do have a real [113:05] existence in a way that we can give an account of, in a way I just tried to describe. [113:10] - So, you would describe it as the size of a set with four elements in it? [113:14] - Well, there are different ways to understand the nature of four. I mean, actually, this gets into [113:18] the question of structuralism, which is maybe a good place to talk about it. [113:24] - What is structuralism? [113:25] - Structuralism is a philosophical position in mathematics, [113:29] or the philosophy of mathematics, by which one emphasizes that what's [113:33] important about mathematical objects is not what they're made out of or [113:37] what their substance or essence is, but rather how they function in a [113:40] mathematical structure. And so, what I call the [113:44] structuralist attitude in mathematics is that we should [113:48] only care about our mathematical structures up [113:52] to isomorphism. If I have a mathematical structure of a certain kind, [113:56] and I make an exact copy of it using different individuals [114:00] to form the elements of that structure, [114:03] then the isomorphic copy is just as good mathematically, and there's no [114:07] important mathematical difference that would ever arise [114:11] from working with this isomorphic copy instead of the original [114:14] structure. And so, therefore, that's another way of saying [114:18] that the substance of individuals, you know, in a mathematical [114:22] structure is irrelevant with regard to any mathematical property of that [114:28] structure. And so, to ask a question like, "What is the number four really?" is an [114:37] anti-structuralist thing because, you know, if you have [114:41] if you have a structure, say, the natural numbers, you know, with all the numbers in it: 0, [114:45] 1, 2, 3, 4, and so on, then [114:48] I could replace the number four with something else, like, you [114:52] know, this bottle of water [114:55] could play the role of the number four in that structure, and it would be [114:59] isomorphic. And it wouldn't matter at all for any mathematical [115:03] purpose to use this alternative mathematical system, you know? [115:07] That's to say that we don't care what the number four is [115:11] really. That is irrelevant. The only thing that matters is what are the [115:15] properties of the number four in a given mathematical system, you [115:18] know, and recognizing that there are other isomorphic copies of that [115:22] system, and the properties of that other system's number four are [115:26] going to be identical to the properties of this system's number [115:30] four with regard to any question that's important about the number four. But those [115:34] questions won't be about essence. So, in a sense, [115:38] structuralism is an anti-essential in mathematics. [115:42] - So, is it fair to think of numbers as a kind of pointer to [115:46] a deep underlying structure? [115:48] - Yeah, I think so, because I guess part of the point of [115:51] structuralism is that it doesn't make sense to consider mathematical [115:56] objects or individuals in isolation. [115:59] What's interesting and important about mathematical objects is how they interact with [116:03] each other and how they behave in a system, and so maybe one wants to [116:07] think about the structural role that the objects play, you know, in a larger [116:11] system, a larger structure. There's a famous question [116:15] that Frege had asked actually when he was looking into the nature of [116:19] numbers, because in his logicist program, right, he was trying to [116:23] reduce all of mathematics to logic. And in that [116:26] process, he was referring to the Cantor-Hume [116:30] principle that, you know, whenever two sets are [116:34] equinumerous, then they have the same number of elements, I mean, if and only [116:37] if. And he founded his theory of number on this [116:41] principle, but he recognized that there was something that [116:45] dissatisfied him about that situation, which is that the [116:49] Cantor-Hume principle does not seem to give [116:53] you criteria for which things are numbers. It only tells [116:56] you a kind of identity criteria for when two numbers are equal to [117:00] each other. Well, two numbers are equal just in case the sets of [117:04] those sizes are equinumerous, so that's the criteria for number [117:07] identity. But it is not a criteria for what is a [117:11] number. And so this problem has become known as the Julius [117:14] Caesar problem because Frege said we don't seem to have any way of telling [117:20] from the Hume principle whether Julius Caesar is a [117:24] number or not. So he's asking about the essence of number and [117:28] whether... Of course, one has a sense that he picked maybe what he was trying to [117:35] present as a ridiculous example, [117:36] because maybe you have the idea that well, obviously Julius Caesar is not a [117:40] number, and there's a lot of philosophical writing that seems to take that line [117:43] also, that obviously the answer is that Julius Caesar is not a [117:47] number. But the structuralists disagree with that [117:51] position. The structuralist attitude is, [117:54] "Look, you give me a number system. If Julius Caesar isn't a number, then [118:00] I can just... let's take the number 17 out of that system and plug [118:04] in Julius Caesar for that role, and now I've got a new number system, and [118:08] now Julius Caesar happens to be the number 17." [118:10] And that's totally fine, you know. So the point of [118:14] structuralism is is that the question of [118:18] whether Julius Caesar is a number or not is irrelevant to [118:21] mathematics. It is irrelevant because it is not about [118:25] structure, it's about this essence of the mathematical objects. [118:30] So that's the structuralist criticism of Frege's point. [118:35] - You've kind of made the case that you can [118:38] say more concrete things about the existence of objects in mathematics [118:42] than you can in our physical reality, about which to us human brains, [118:47] things are obvious or not. So what's more real? The [118:51] reality we see with our eyes or the reality we can express in mathematical theorems? [118:59] - I'm not quite sure. I mean, I live entirely in the Platonic realm, and I don't [119:08] really understand the physical universe at all. So I don't have strong views. [119:13] - Let's talk about the Platonic realm. Is it- because you live there, is it real? Or- [119:19] - Oh yeah, totally, yeah. This is the realist position in mathematics is that [119:23] abstract objects have a real existence. And okay, what's meant by that [119:27] is that there's some sense of existence in which those objects can be regarded as real. [119:32] - How should we think about that? How should we try to visualize that? What does it mean to [119:36] live amongst abstract objects? [119:41] - Right. [119:41] - Because life is finite. We're all afraid of death. We f- [119:46] fall in love with other physical manifestations of objects. [119:52] And you're telling me that maybe reality actually exists elsewhere, [119:56] and this is all just a projection- [119:59] - Well, I mean- [119:59] - ... from the abstract realm. [120:02] - Do abstract objects exist in a place and at a time? That's very debatable, I think. [120:07] - Right. And what does place and time mean? [120:08] - Uh, all time, yeah, so... [120:10] - So what's more real, physics or the mathematical Platonic space? [120:16] - Well, the mathematical Platonic realm [120:19] is... I'm not sure I would say it's more real, but I'm saying we [120:23] understand the reality of it in a much deeper and more- [120:27] ...a more convincing way. I don't think we understand the nature of physical [120:31] reality very well at all. And I think [120:34] most people aren't even scratching the surface of the [120:38] question as I intend to be asking it. So, you know, obviously we [120:42] understand physical reality. I mean, I knock on the table- [120:44] ...and so on, and we know all about what it's like to, you know, have a birthday [120:48] party or to drink a martini or whatever. And so we, we, we [120:52] have a deep understanding of existing in the physical world. [120:56] But maybe understanding is the wrong word. We have an experience of [121:00] living in the world- [121:01] - Yeah, experience. [121:01] - ...and riding bicycles and all those things, but I don't think we actually [121:05] have an understanding at all. I mean, very, very little [121:09] of the nature of physical existence. I think it's a profound [121:12] mystery. Whereas I think that we do have something a little better of an [121:19] understanding of the nature of mathematical existence and abstract existence. [121:23] So that's how I would describe the point. [121:26] - Somehow it feels like we're approaching some deep truth from different directions, [121:34] and we just haven't traveled as far in the physics [121:38] world as we have in the mathematical world. [121:41] - Maybe I could hope that someone will give, you know, the [121:45] convincing account, but it seems to be a profound mystery to me. I can't even [121:49] imagine what it would be like to give an account of physical existence. [121:52] - Yeah, I wonder, like a thousand years from now as physics progresses... [121:56] - Right [121:56] - ...what this same conversation would look like. [121:59] - Right. That would be quite interesting. [122:00] - Do you think there's breakthroughs a thousand years from now on the mathematics side? [122:04] Because we've just discussed, and we'll return to, a lot of turmoil a century ago. [122:11] - Right. [122:12] - Do you think there's more turmoil to be had? [122:14] - It's interesting to me because I have my feet in two worlds [122:18] of mathematics and philosophy, and to compare the [122:22] differences between these subjects. And one of the, one of the [122:26] big... There's many cultural differences, but one of the big cultural differences is [122:30] towards the idea of progress in the [122:34] subject. Because mathematics has huge progress. We [122:38] simply understand the mathematical ideas much, much [122:41] better, you're continually improving our understanding and [122:45] there's growth in knowledge. We understand the nature of infinity now better [122:49] than they did 100 years ago. I mean, definitely better. And they [122:52] understood it better 100 years ago than they did, you know, for the previous thousands of years [122:56] and so on. So, in almost every part of mathematics, there's [123:00] improved understanding of the core issues so much [123:04] so that, you know, the questions at hand become [123:08] totally different and the field sort of moves on to more [123:11] difficult, interesting questions. Whereas in philosophy, [123:15] there's... That's a little bit true that there's [123:19] progress. But meanwhile, it's also true that there are these [123:23] eternal questions that have been with us for thousands of years [123:27] and in fact, so much so that you can find a lot of philosophers [123:30] arguing the important contribution of philosophy is in [123:34] asking the questions rather than answering them because it's hopeless [123:38] to answer them. I mean, the nature of these deep philosophical [123:42] questions is so difficult. Less of a sense of [123:46] progress is what I'm trying to say. I don't see any reason to [123:50] think that the progress in mathematics, in the growth in our mathematical [123:54] understanding and knowledge won't simply continue. And [123:58] so, a thousand years from now, maybe the mathematics that they will be doing at that time [124:04] would probably be completely unrecognizable to me. I maybe [124:08] wouldn't even begin to understand what they're talking about, even without sort of [124:12] witnessing, you know, the intervening [124:16] developments. So if you bring someone from ancient [124:19] times to today, they maybe wouldn't even understand what we're talking about [124:23] with some of the questions. But I feel that, [124:27] you know, if Archimedes came and we were able to [124:30] communicate, I think I would be able to tell him, you [124:34] know, about some of the things that are going on in [124:37] mathematics now and, and maybe, you know... [124:43] Or, or anyone from that time, I mean. So I think it is possible to [124:49] have this kind of progress even when the subject kind of shifts [124:53] away from the earlier concerns as a result of the progress, basically. [124:57] - To take a tangent on a tangent since you mentioned [125:01] philosophy, maybe potentially more about the questions and maybe [125:05] mathematics is about the answers, I have to say you are a [125:08] legend on MathOverflow, which is like Stack Overflow [125:12] but for math. You're ranked number one all time on there with currently [125:15] over 246,000 reputation points. How do you approach answering difficult questions on [125:23] there? [125:24] - Well, MathOverflow has really been one of the great pleasures of [125:28] my, of my life. I've really enjoyed it. I mean... And I've [125:32] learned so much from interacting on MathOverflow. I've been on there since [125:39] 2009, which was shortly after it started. I mean, it wasn't exactly at the start, but a little [125:43] bit later. And and [125:48] I think it gives you the stats for how many characters I typed and I don't [125:53] know how many million it is, but uh, this enormous amount of um, [126:01] time that I've spent thinking about those questions and it has really just been [126:05] amazing to me. Uh- [126:06] - How do you find the questions that grab you and how do you go about- [126:10] - Right [126:10] - ... answering them? [126:11] - So, I'm interested in any question that I find interesting. [126:15] So... And it's not all questions. Sometimes certain kinds of [126:18] questions just don't appeal to me that much. [126:21] - So you go outside of set theory as well? [126:23] - So, I think when I first joined MathOverflow, I [126:27] was, I was basically one of the only, one of the few [126:31] people in logic who was answering. I mean, there were other people who know [126:35] some logic, particularly from category theory and other parts of [126:38] mathematics that aren't in the most traditional parts of [126:42] logic, but they were answering some of the logic questions. So I really found myself [126:46] able to make a contribution in those very early days by [126:49] engaging with the logic-related questions. But [126:54] there weren't many logic people asking questions either. But what I found was [126:57] that there was an enormous amount of interest [127:01] in topics that were logic-adjacent. So a [127:05] question would arise, you know, in group theory, but it had a logic aspect or an [127:09] analysis or whatever, and there would be some logic [127:12] angle on it. And what I found was that I was often able [127:16] to figure out an answer by learning enough about [127:20] that other subject matter. This is what was so rewarding for me, because basically I had to learn enough. [127:25] had to learn enough. My expertise, my main expertise was [127:28] logic, but someone would ask a question, you know, that, that [127:32] was about, say, the axiom of choice in this other subject [127:35] matter or the continuum hypothesis or something like that in an, in the other [127:39] subject matter. And I would have to learn enough about that other subject and [127:43] the context of the question in order to answer and I was often able to do [127:47] that. And so I was quite happy to do that. And, and also [127:51] I learned a lot by doing that because [127:54] I had to learn about these other problem areas. And so it really [127:57] allowed me to grow enormously as a mathematician. [128:01] - To give some examples of questions you've answered, what are some reasonable [128:05] sounding statements that are independent of ZFC? What are the most [128:09] misleading alternate definitions in taught mathematics? Is [128:13] the analysis as taught in universities in fact the analysis of definable [128:16] numbers? Solutions to the continuum hypothesis? [128:20] Most unintuitive application of the axiom of choice? Non-trivial [128:24] theorems with trivial proofs? Reductio ad absurdum or the [128:29] contrapositive? What is a chess piece [128:33] mathematically? We should say you worked quite a bit on infinite chess, which we [128:37] should definitely talk about. It's awesome. You've worked on so many fascinating [128:40] things. Has philosophy ever clarified mathematics?... [128:44] why do we have two theorems when one implies the other? [128:48] And, of course, just as an example you've given a really, a [128:52] great, almost historical answer on the topic of the [128:56] continuum hypothesis. Maybe that's a good place to go. We've touched on it a little [129:00] bit, but it would be nice to lay out what is the continuum [129:03] hypothesis that Cantor struggled with. And I would love to also speak to the [129:07] psychology of his- his own life story, his own struggle with it. [129:11] It's the human side of mathematics is also fascinating. [129:14] So what is the continuum hypothesis? [129:16] - So the continuum hypothesis is the question that arises [129:20] so naturally whenever you prove that there's more than one size of [129:23] infinity. So Cantor proved that the infinity of the real numbers is strictly larger [129:30] than the infinity of the natural numbers. But immediately when you prove that, [129:36] one wants to know, well, is there anything in between? I mean, what could be a [129:40] more natural question to ask [129:42] immediately after that? And so Cantor did ask it, and he spent his [129:46] whole life thinking about this question. And so the continuum hypothesis [129:50] is the assertion that there is no infinity in between the natural numbers [129:54] and the real numbers. And, of course, Cantor knew many sets [129:58] of real numbers. Everything in between... I mean, everything that's in that [130:02] interval would be equinumerous with some set of real [130:05] numbers. But we know lots of sets of real numbers. I mean, there's all these various [130:09] closed sets, Cantor sets, and so on. There's Vitali sets. We have all kinds of [130:13] sets of real numbers. And so you might think, well, if the continuum [130:17] hypothesis is false, then we've probably seen the- the set already. We just have [130:21] to prove, you know, that it's strictly in between. But it turned [130:24] out that for all the sets that anyone ever could define or pick [130:28] out or observe, for all the sets of real numbers, it was always the case [130:32] either that they were countable, in which case they're equinumerous [130:36] with the natural numbers or else finite. Or they were [130:40] fully equinumerous with the whole real line. And so [130:44] they were never strictly in between. I mean, you're in this situation and you [130:48] have 100, thousands of sets that are [130:52] candidates to be in between, but in every single case, [130:56] you can prove it's on one side or the other [130:59] and not strictly in between. And so in every situation [131:03] where you're able to figure out whether it's in between or not, it's [131:06] always never strictly in between. [131:09] - Now, Cantor was obsessed with this. [131:11] - I think he was. Yeah, I'm not a historian, so I don't know the exact history. [131:15] - Well, everything I've seen, it seems to be the question that broke him, huh? Um, [131:19] I mean, just struggling with different opinions on the hypothesis [131:23] within himself and... ...Desperately chasing, trying to prove it. [131:29] - So he had a program for proving it, which has been [131:33] affirmed in a certain respect. Of course, the continuum hypothesis holds [131:37] for open sets. That's easy to see. If you have an open [131:40] interval, then this is fully equinumerous with the whole [131:44] real line. Any interval is equinumerous with the whole line [131:47] because all you would need is a function, you know, like the arctangent function [131:51] or something that maps the whole real line into an interval. And [131:55] that's a one-to-one function. So we know the open sets [131:59] have the property that their non-trivial open sets are all [132:03] fully equinumerous with the whole real line. So, never strictly in between. [132:07] But remarkably, Cantor proved it also for the closed sets, [132:11] and that is using what's called the Cantor-Bendixson theorem. So, [132:15] it's quite a remarkable result. It's definitely not obvious. [132:20] And in this theorem actually was the origin of the ordinals. Cantor [132:24] had to invent the ordinals in order to make sense of his Cantor-Bendixson process. [132:31] - Can you define the open and the closed set in this context? [132:34] - Oh, yeah. Sure. So a set of reals is open if every [132:38] point that it contains is surrounded by a little interval of [132:42] points, the whole tiny little interval. But that [132:46] tiny little interval is already just by itself equinumerous with the whole line. [132:49] So that's why that question is sort of easy for open sets. A closed [132:53] set is a complement of an open set, and there's a lot of [132:57] closed sets that are really complicated of varying [133:00] sizes. So of course, any closed interval is a closed set, but it's not only those. [133:04] There's also things like the Cantor set, which you get by omitting middle [133:08] thirds. Maybe some people have seen this construction. Or you can [133:12] imagine sort of randomly taking a lot of little tiny [133:16] open intervals, you know, all over the line and so on. So that altogether would be an open [133:20] set, and the complement of it would be a closed set. So you can imagine just [133:24] kind of tossing down these open intervals, and what's left over [133:27] is the closed set. Those sets can be quite complicated, and they can have [133:31] isolated points, for example, if the two open intervals were just [133:35] kissing and leaving only the one point between them. But also you could [133:39] have sequences that are converging to a point, that would [133:43] also be a closed set, or convergent sequences of convergent [133:47] sequences and so on. That would be a closed set also. [133:50] - The Cantor set is constructed by iteratively removing open intervals, middle thirds, [133:54] like you mentioned, from the interval, [133:56] and trying to see, can we do a thing that that goes in between? [134:00] - Right. So the question would be, can you produce a set [134:05] that has an intermediate size? an intermediate cardinality, right? [134:09] And Cantor proved, with the closed set, "No, it's impossible." Every closed [134:13] set is either countable or equinumerous with the whole real line. [134:18] And the Cantor program for solving the Continuum Hypothesis was, [134:25] a sort of working up. So you did it for open sets and for closed sets, [134:29] and you sort of work up. Maybe he wants to go into what are called the Borel sets, [134:32] which are sort of combinations of open and closed sets. And there's a vast [134:36] hierarchy of Borel complexity. And it [134:40] turns out that the Continuum Hypothesis has been proved also [134:44] for the Borel sets in this hierarchy. But then one wants to go beyond. [134:48] What about more complicated sets? So there's this hierarchy of complexity [134:52] for sets of real numbers. And Cantor's idea was to sort of work your way up the [134:56] hierarchy by proving that the Continuum Hypothesis [135:00] was more and more true for those more and more complicated sets, based on our [135:04] understanding of the earlier cases. And that has [135:07] been carried out to a remarkable degree. It turns out that one begins to need [135:15] large cardinal assumptions, though, in order to get to [135:19] the higher realms, even at the level of projective hierarchy, [135:23] which are sets that you can define by using quantifiers over the real numbers [135:27] themselves. So you get this hierarchy on top of the Borel hierarchy, [135:32] the hierarchy of projectively definable sets. And it [135:35] turns out that if you have enough large cardinals, then the projective sets [135:42] also are always either countable or equinumerous with the whole real [135:45] line. And then one can try to go beyond this and so [135:49] on. So I view all of those results which came, you know, in the past 50 [135:53] years, the later ones, as fulfilling this Cantor idea that goes back, [136:01] you know, 120 years to his idea that we would prove the Continuum [136:05] Hypothesis by establishing more and more instances for greater and [136:09] greater complexity of sets. But of course, [136:13] even with what we know now, it hasn't fully succeeded and it [136:17] can't because the hierarchy of complexity doesn't include [136:21] all sets of real numbers. Some of them are, sort of, transcending this hierarchy [136:25] completely, in a way. And [136:29] so the program can't ever fully be successful, especially in light [136:33] of the independence result. [136:34] - Yeah. Well, spoiler alert, can you go to the independence result? [136:38] - Sure. [136:39] - So what does that mean? So the Continuum [136:43] Hypothesis was shown to be independent from the ZFC axioms of mathematics? [136:46] - Right. So the ZFC axioms were the axioms that were [136:50] put forth first by Zermelo in 1908 in regard to his [136:54] proof of the well-order theorem using the axiom of choice. That [136:58] wasn't fully ZFC. At that time, it was just Zermelo theory because he [137:02] sort of... There was a kind of missing axiom, the replacement axiom, and the [137:06] foundation axiom were added later, and that's what makes the Zermelo-Fraenkel [137:10] axiomatization, which became, sort of, standard. [137:13] Actually, there's another aspect, which is Zermelo's original theory allowed [137:17] for the existence of ur-elements, or these [137:20] atoms, mathematical objects that are not sets [137:25] but out of which we build the set theoretic universe, [137:28] whereas set theorists today generally don't use ur-elements at all. I, [137:36] I argue that it's really the philosophy of structuralism that [137:40] leads them to omit the ur-elements because it turns out that [137:44] if you adopt ZFC axioms with ur-elements, ZFCU it's called, or ZFA, then any [137:52] structure that exists, any mathematical structure that exists in that set theoretic universe [137:56] with the atoms is isomorphic to a structure that doesn't use the atoms at all. [138:02] And you don't need the atoms if you're a structuralist because you only care about [138:06] the structures up to isomorphism anyways, and the theory is simply more [138:10] elegant and clear without the atoms. They're just not [138:13] needed. And so that's why today when we talk about set theory, generally we [138:17] talk about the atom-free version, and ZFC has no [138:20] ur-elements. Okay. So we formulate the ZFC [138:25] axioms of set theory. These are expressing the main [138:28] principle ideas that we have about the nature of sets and set existence. And [138:38] Canter had asked about the continuum hypothesis [138:41] in the late 19th century, and it remained open, totally open until 1938. [138:50] - We should mention, I apologize, that it was the number one [138:54] problem in the Hilbert's 23 set of problems formulated at the [138:58] beginning of the century. [138:59] - That's right. [138:59] - Maybe you can comment on why did he put that as number one. [139:02] - So... Right. So Hilbert had introduced at his famous address at the [139:06] turn of the century this list of problems that he thought [139:11] could guide or were important to consider in the [139:15] coming century of mathematics. I mean, that's how people talk about it now, although I'm not sure at [139:19] all... Of course, I can't really speak for Hilbert at all, but if [139:23] you were a very prominent mathematician, [139:27] I find it a little hard to believe that Hilbert would have conceived of his list [139:31] in the same way that we now take his lists. I mean, [139:35] having observed the century unfold, we know that that list of [139:39] 23 problems did in fact guide whole research programs, and [139:43] it was extremely important and influential. But at the time, Hilbert [139:47] would have no reason to think that that would be true, and he was [139:51] just giving a lecture and had a list of problems that [139:55] he thought were very important. And so I tend to I would find [139:59] it more reasonable to think that he was just making a list of problems that he thought were [140:03] extremely interesting and important and fundamental in a way without [140:07] the kind of heavy burden of [140:11] guiding this 20th century research. Although it turns out [140:15] that in fact that's exactly what they did. [140:18] And we already discussed how Hilbert's views on the nature of set [140:22] theory and the fundamental character, that quote [140:25] where he said, "No one will cast us from the paradise that [140:29] Canter has created for us." So, so I think [140:33] Hilbert was convinced by Canter on the importance and the [140:37] fundamental nature of the continuum hypothesis for the foundations of mathematics, [140:41] which was a critically important development for the unity of [140:44] mathematics. I mean, before set theory emerged as a foundation of mathematics, [140:48] you know, there are different subjects in mathematics. [140:52] There's algebra and there's analysis, real analysis, and topology and [140:56] geometry, and so on. There are all these disparate subjects [141:00] with their own axioms, separate axioms, right? [141:03] And sometimes it happens, like when you're proving, say, the fundamental [141:07] theorem of algebra, you know, that the complex numbers are an algebraically closed [141:11] field that you can solve any polynomial equation in. [141:16] But the proof methods for that theorem come from [141:19] other parts of mathematics. You know, those topological proofs and so [141:23] on. And so how does that [141:27] work? I mean, if you have totally different axiom systems, but you're using results from [141:31] one subject in another subject, it's somehow incoherent [141:35] unless there's one underlying [141:38] subject. So the unity of mathematics was provided by the [141:42] existence of a mathematical foundation like set theory. And at the time, it was set theory. [141:47] And so it's critically important to be able to have a [141:51] single theory in which one views all of mathematics as taking [141:55] place to resolve that kind of transfer and borrowing [141:59] phenomenon that was definitely happening. So that must [142:03] have been part of Hilbert's thinking about why it's so important to have a uniform [142:07] foundation, and set theory was playing that role at the time. Now, of course, we have [142:11] other possible foundations coming from category theory or type [142:14] theory, and there's univalent [142:18] foundations now. So there are sort of competing foundations now. There's no [142:21] need to just use one foundation, one set theoretic foundation. Although [142:25] set theory continues to, in my view, have an extremely successful [142:29] meta-mathematical analysis as a foundation, I think is much more [142:33] successful than set theory for any of those other foundations, but [142:37] it's much less amenable though to things like computer proof and so on, which is part of [142:41] the motivation to find these alternative foundations. So, yeah, okay, so [142:45] just to talk about Hilbert though, I think he was motivated [142:49] by the need for a unifying foundation of [142:52] mathematics, and set theory was playing that role, and the continuum hypothesis [142:56] is such a core, fundamental question to ask, so it [143:00] seems quite natural that he would put it on the list. There were other [143:04] logic-related questions though, like Hilbert's tenth problem is also related to logic. [143:08] This is the question about Diophantine equations, and [143:12] he asked to provide an algorithm to decide whether a given [143:16] Diophantine equation has a solution in the integers. So a Diophantine [143:19] equation is just, I mean, it's maybe a fancy way of talking about [143:23] something that's easy to understand, a polynomial equation, except it's [143:27] not just one variable, many variables. [143:31] So you have polynomials in several variables over the [143:35] integers, and you want to know, can you solve it? So the problem is, [143:38] as stated by Hilbert, to provide an [143:42] algorithm for answering the question whether a given [143:45] polynomial equation has a solution in the integers. [143:49] So he's sort of presuming that there is an algorithm, but he wants to know what it [143:53] is. What is the algorithm? But the problem was solved by proving that there is no [144:01] algorithm. It's an undecidable problem, like the halting problem. [144:05] There is no computable procedure that will correctly decide whether a given [144:09] polynomial equation has a solution in the integers. So that's quite [144:13] a remarkable development, I think. There were also a few other [144:17] logic-related questions on the list. [144:20] - And so eventually, continuum hypothesis was shown to be independent from ZFC [144:24] axioms, as we've mentioned. So, how does that make you feel? [144:29] What is independence, and what does that mean? [144:30] - But once you tell the story, the historical story... [144:32] - Yes [144:32] - ...is really quite dramatic. [144:34] - Yeah, that's great [144:34] - I think, because Cantor poses the question, you know, late 19th century. [144:39] And then it's totally open. Hilbert asks about it, you know, at the turn of the [144:43] 20th century. Nobody has any clue. There's no answer [144:47] coming until 1938. This is four decades later, right? So a long [144:53] time, and Gödel, Kurt Gödel, proved half of it. What he proved is that [145:03] if the axioms of set theory are consistent, then there is a set theoretic world [145:10] where both the axiom of choice and the continuum hypothesis are true. [145:17] So what he's doing is showing this is called the constructible universe, Gödel's L. [145:24] So he solved this. This is the same result [145:28] where he answers the safety question of the axiom of choice, but [145:31] also for the continuum hypothesis. They're true in the same set theoretic universe [145:37] we get. So if ZF, without the axiom of choice, is consistent, then so is [145:41] ZFC plus the continuum hypothesis is the result. 1938. It's really such a beautiful [145:47] argument. It's just incredible, I think, because [145:51] he's building an alternative mathematical [145:54] reality. That's the structure of the proof, is that, okay, [145:58] if there's any mathematical reality, if there's any set theoretic [146:02] world, then we're going to build another one, a separate one, a [146:05] different one, maybe different. Maybe it's the same as the original one, it could be. [146:09] If we started already in the one that he built, then it would be the same. But [146:13] there's no reason to assume it was the same. So he has this kind of [146:17] model construction method to build this [146:20] alternative set theoretic reality, the constructible universe. And then [146:24] he proves that the axiom of choice is true there, and also the continuum hypothesis is [146:28] true there, and it's just amazing. Really beautiful argument. [146:32] Okay, so then for the other part of the independence, that's only half of it, [146:36] because Gödel shows basically [146:40] that you can't refute the continuum hypothesis, but that's not [146:44] the same thing as proving that it's true. He showed [146:48] that if set theory is consistent... [146:52] without the continuum hypothesis, then it's consistent with the continuum hypothesis. [146:55] So that's not the same thing as proving that it's true. Yeah. [146:59] And then it didn't come until 1963, when Paul Cohen invented the method of forcing. [147:06] And proved that if there's a model of set [147:10] theory, then there's a model of set theory in which the continuum [147:13] hypothesis is false. So Cohen also is [147:19] giving us this extremely powerful tool for building [147:23] alternative mathematical realities, is how I think about [147:26] it. He's explained to us how to take any set theoretic [147:30] world and build another different one in which the continuum hypothesis is [147:34] false. The forcing extension. [147:37] - It's just such a fascinating technique, [147:40] tool of forcing. Maybe I'm anthropomorphizing it, [147:44] but it seems like a way to escape one mathematical universe into another, or to [147:52] expand it or to alter it. So you travel between mathematical [147:55] universes. Can you explain the technique of forcing? [147:57] - Yeah, exactly. It's all those things. It's so wonderful. I mean, that's exactly how [148:01] I think about it. I mean... [148:03] - And we should mention, maybe this is a good place to even give a bigger [148:07] picture. One of your more controversial ideas in mathematics as [148:11] laid out in the paper, The Set-Theoretic Multiverse, you [148:15] describe that there may not be one true [148:18] mathematics, but rather multiple mathematical universes, and [148:21] forcing is one of the techniques that gets you from one to the other, so... [148:25] - The- [148:25] - Can you explain the whole shebang? The whole... [148:27] - Yeah, sure. Let's get into it. So the lesson of Cohen's result and Gödel's [148:34] result and so on, these producing these alternative set theoretic [148:38] universes. We've observed that the continuum hypothesis is [148:42] independent and the axiom of choice is independent of the other axioms, [148:46] but it's not just those two. We have thousands of independence results. [148:50] Practically every non-trivial statement of infinite [148:53] combinatorics is independent of ZFC. I mean, this is the [148:56] fact. It's not universally true. There are [149:00] some extremely difficult prominent results where [149:03] people proved things in ZFC, but for the most [149:07] part, if you ask a non-trivial question about infinite [149:11] cardinalities, then it's very likely to be independent of [149:14] ZFC. And we have these thousands of arguments, these [149:18] forcing arguments that are used to establish that. And [149:22] so how should we take that? I mean, on the one hand, if you have [149:26] a theory and it doesn't answer any of the questions that you're [149:30] interested in... Okay, so what does that mean? If you're following what I [149:34] call the universe view or the monist view, [149:38] you might naturally say, "Well, look, ZFC is a weak theory, and there's the true [149:46] set theoretic reality out there, and we need a better theory [149:50] 'cause the current theory isn't answering the questions. Everything's [149:53] independent." And so that seems like a quite reasonable thing [149:57] to take. If you think that there is... that every set theoretic question has a [150:01] definite answer and there's a unique set theoretic truth or a unique [150:05] fact of the matter, right, this is the universe view. [150:09] - And by the way, to reiterate, [150:11] independent means it cannot be proved or disproved within this [150:14] axiomatic system within this theory. [150:16] - Right. Exactly. So to be independent means you can't prove it and also you can't prove that [150:20] it's false. You can't refute it. [150:22] - And you're saying that's why the statement is so traumatic or sad, that [150:26] most of the interesting stuff, as you said, has been shown to be independent. [150:31] of ZFC. [150:31] - But, but that's an interesting way to put it, I think, because it reminds me of this, [150:35] uh... when I was a graduate student in Berkeley, there was [150:39] another graduate student who was working with a non-logic [150:43] professor in C-star algebras or something [150:47] like this. So it's a part of analysis or functional analysis, [150:51] and they were looking at a question, and it turned out to be [150:55] independent of ZFC, right? And the attitude of this [150:59] other professor was that, "Oh, I guess I asked the wrong [151:02] question." But my attitude and the [151:06] attitude of all the set theorists was when you ask a question that [151:10] turns out to be independent, then you asked exactly the right question because this is the [151:14] one... You know, it's carving nature at its joints. [151:18] You're adjudicating the nature of set theoretic reality [151:22] by finding these two realms. You find one of these [151:25] dichotomies. You know, there's the worlds where it's true and the worlds where it's false. [151:28] And so when you ask that question, that's to be celebrated. It means you asked exactly [151:32] the right, interesting, fascinating question. So it's not a kind of bleak [151:36] thing that you can't prove it and you can't refute it, and that's such a disaster. [151:40] Rather, it means that you found this... this... this cleavage in reality, in [151:48] mathematical reality, and it's good to know about those when they happen, you know? [151:52] - Carving nature at its joints. So what can you do about the [151:56] things that are shown to be independent from ZFC? [152:00] - Right. So... [152:00] - What are the techniques? [152:01] - So one thing is that because of the incompleteness theorem, [152:04] we know that there's going to be... For any [152:08] theory that we can write down, there's going to be things that we can't [152:12] prove, true things we can't prove in it. So there's those things are gonna be [152:16] independent. And so we're already aware of the fact that there will always be these [152:23] independent phenomenon for any theory that we write. And [152:27] furthermore, some of those theories we won't even be able to prove [152:31] that they're consistent, you know, like the consistency of their own theory. So that's called the [152:34] consistency-strength hierarchy. [152:37] So it's a direct consequence of Gödel's second incompleteness theorem that [152:42] for any theory we can write down, then towering over it is this [152:46] incredibly tall tower of consistency strength, [152:49] where the strength in theories aren't just adding another [152:53] axiom, but they're adding another axiom even whose consistency was not [152:57] provable in the previous layers of the hierarchy. [153:01] So, and so how lucky we are to find the large [153:04] cardinal axioms that instantiate exactly this feature of increasing [153:12] consistency strength, this unending and extremely tall hierarchy of consistency [153:19] strength of axioms. And it exactly fulfills the prediction [153:23] that Gödel's theorem makes about that kind of [153:27] thing. Except, it's the axioms in the large cardinal [153:31] hierarchy aren't, you know, metalogical [153:35] self-referential statements of the form that sometimes arise in the Gödel [153:38] analysis, but rather they're professing [153:42] existence of big infinities, these large cardinal axioms. And so [153:47] it's such a welcome development, and yet it's [153:51] also known that the continuum hypothesis is [153:54] independent of all of the known large cardinal axioms. So [154:00] none of the large cardinal axioms we can prove, none [154:04] of them can settle the continuum hypothesis. So the independence [154:08] phenomenon is still there for things like the continuum [154:11] hypothesis and the cardinal combinatorics that I mentioned. [154:17] - So you're building this incredible hierarchy [154:21] of axiomatic systems that are more powerful than the ZFC. [154:24] - More powerful than ZFC and then more powerful than that, more powerful than that, and so on. [154:28] It keeps going forever, and it will never be finished. [154:32] - And still, to this day, the continuum hypothesis does not... [154:36] - It's not settled by any of the large cardinal axioms. [154:39] - Wow. Wow. [154:44] What does that mean? How does that make you feel? Will it ever be settled? [154:47] - Yeah, well, it's part of my multiverse view, I guess. So which [154:51] we started by, I was describing the universe view, which [154:55] is the view that, look, there are facts of the matter about all [154:59] of these questions and that it will turn out, if you're a universe view [155:02] person, which I'm not, but if you are, then you will hold [155:06] that there is a right answer to the continuum hypothesis question, and there's a [155:10] right answer to the large cardinal questions [155:14] and so on. And that what we should be aiming to do is figure out this [155:18] one true set theory, okay? In contrast I take the developments [155:24] of set theory over the past half century or more as evidence that there isn't such a [155:31] unique set theoretic reality. Rather, [155:35] what we've been doing for decades now is producing more and [155:39] more alternative set theoretic universes in which the [155:43] fundamental truths are differing from one to the other. And that [155:47] is the answer to the continuum hypothesis question. The fact that [155:53] given any model of set theory, there's a forcing extension where the continuum [155:57] hypothesis is true, and another one where it's false. You can sort of [156:01] turn it on and off like a light switch. And that's the fundamental nature of the [156:05] continuum hypothesis is that you can have it or you can have the negation as you like [156:10] within a very closely related set theoretic world. [156:14] Wherever you happen to be living, there's a closely related one where [156:18] CH is true, where the continuum hypothesis is true, and one [156:22] where it's false. And that itself is a kind of answer. [156:25] It's not a singularist answer, a universe view [156:29] answer. It's a pluralist answer. And this [156:33] led me to my views on the multiverse view of set theory and [156:37] pluralist truth, namely the fundamental nature of set theoretic truth [156:41] has this plural character in that [156:45] there isn't a singular meaning to the fundamental terms, but [156:49] rather, there's this choice of alternative set-theoretic universes [156:53] that have different truths. [156:55] - So, what does the multiverse view of mathematics enable you to [156:58] do? What does it empower you to do and what are the limitations? [157:02] What are the things it breaks about mathematics as a field, as a [157:06] space of knowledge, and what does it enable? [157:10] - First of all, I guess one should say that these different philosophical [157:14] positions that you might take in the philosophy of set theory, like the multiverse [157:18] view or the universe view, we don't ever disagree about [157:21] the mathematics. We're all agreeing on what the theorems are. [157:25] It's a question of philosophical perspective on the underlying meaning [157:29] or the context, or really what is a philosophy of mathematics for, right? [157:36] And I mean, if you look back in history, for example, like [157:40] to the time of calculus with Newton and Leibniz, right? [157:44] They famously developed the ideas of calculus using their concepts of infinitesimals, [157:51] and those foundations were roundly mocked by [157:55] Bishop Berkeley and so on who talked about, you know, what are these [157:59] same evanescent increments, and shall we not call them the [158:02] ghosts of departed quantities? But the [158:06] foundations really were kind of completely suspect, I think, [158:10] at the time. And that foundation [158:14] of infinitesimal calculus really only became rigorous in the [158:17] 1950s or so with the development of non-standard analysis and [158:21] Robinson's work. Okay, so the point I'm trying to make is that, do you [158:24] need a robust, rigorous foundation of mathematics to make enduring insights in [158:32] mathematics? And the answer, regrettably, is apparently not because [158:39] in calculus, even with that lousy, creaky foundation of infinitesimals not even [158:47] well understood that Newton and Leibniz had, they proved all the [158:51] fundamental theorems of calculus and, you know, they had all the main insights [158:57] in those early days with that extremely bad [159:00] foundation. And so that shows you something about the relevance of the kind of [159:07] foundational views on mathematics and how important they are for [159:11] mathematical developments and progress and insight. I mean, because I [159:15] view those early mathematical developments in calculus as [159:18] genuinely mathematical and extremely important [159:23] and insightful, even though the foundations weren't any good, [159:27] from, you know, by contemporary perspectives. Okay. [159:30] So, rather... So when it comes to the philosophy of set theory and [159:34] the dispute between the universe view and the pluralism, my view is that the choice [159:41] of the philosophical perspective doesn't actually have to do with the [159:44] mathematical developments directly at all. Rather, it [159:48] tells us, "Where should set theory go? What [159:52] kind of set theory should we be looking at? What kind of [159:56] questions should we be asking?" So if you have a [160:00] universe mentality, the universe view, then you're [160:04] gonna be pushed to try to find and articulate the [160:08] nature of the one true set-theoretic universe. [160:12] And I think that remark is really well borne out by the developments with [160:16] Hugh Woodin, who's one of the most prominent mathematicians [160:20] and philosophers with the universe view and his theory of ultimate [160:24] L and so on. And he's really striving. [160:26] - Who was also your advisor. [160:28] - He was also my supervisor. My graduate supervisor. [160:30] - Which is a, a personal story as well. [160:32] - This, this fundamental dispute, yeah, on this question. [160:37] he is uh, has a very strong and successful [160:41] research program, sort of trying to give legs [160:45] to finding the nature of the one true set theoretic [160:48] universe. And it's driving the questions that he's asking and the [160:52] mathematical programs that he's pursuing. Whereas if you have a [160:56] pluralist view, as I do, then you're gonna be led and [160:59] attracted to questions that have to do with the interaction of [161:03] different set theoretic universes. Or maybe you wanna [161:06] understand the nature of how are the models of set theory related to their [161:10] forcing extensions and so on. And so this led to things, [161:14] um that I call, say, set theoretic potentialism, where you think about a set theoretic [161:18] universe in a potentialist way. Not in [161:22] the sense of potential infinity directly, because all of these universes have [161:26] infinite sets inside them already. But they're potentialist in the sense [161:29] that we could have more sets. The universe could be wider [161:33] and taller and so on, you know, by forcing or by [161:37] extending upward. And so we wanna understand the nature of [161:41] this realm of set theoretic universes. [161:45] And, and that's quite some exciting work. And so with [161:48] Benedikt Loewe and I, we proved some theorems on the modal logic of [161:52] forcing and set theoretic potentialism under end extension. I've done a bunch [161:56] of work on this topic. And, and also I [162:00] I mounted together with Gunter Fuchs and Jonas Riets, who was one of my own PhD students, the topic of set theoretic [162:04] my own PhD students, the topic of set theoretic [162:08] geology, which is studying... It's taking the metaphor of [162:12] forcing. I mean, in forcing, you have the ground model and the forcing [162:15] extension. And when I was first working with Jonas [162:20] he said, "I wanna undo forcing. I wanna go [162:23] backwards." And I at first said, "But Jonas, it doesn't work [162:27] that way. You start in the model, in the ground model, and you go out, you go to the bigger one. [162:31] bigger one. You know, that's how forcing works." And he said, "No, no, I wanna go [162:35] backwards." And, and so he was quite persistent, actually. [162:38] And um, and so finally, I said, "Okay, let's, let's do it. Let's [162:42] take it seriously." And so we sat down and, and s- and started [162:46] thinking, you know, more precisely and carefully and deeply about the nature [162:50] of taking a set theoretic universe and seeing where did it come [162:53] from by forcing, which was a new way of thinking about forcing at the time. [162:58] - Like reverse engineering the forcing? [163:00] - Yeah, something like that. Forcing is a way of producing a new [163:04] universe. And so you could start somewhere and go to that new universe, or you could look [163:08] where you are and say, "Well, look, I got here by doing that already in the past." [163:12] So we defined models of the bedrock model [163:16] and ground, you know, sort of undoing the forcing. And, and [163:20] really, it was quite fruitful. And I view this as part of the sort of pluralist [163:24] perspective, except the difference is that set theoretic geology is [163:28] amenable to the universe view. So even though the work [163:32] was inspired by this philosophical view on the multiverse view, nevertheless, the [163:39] central ideas of geology have now been picked up [163:43] by the people with the research program in the universe view. Because it turns [163:47] out that set theoretic geology is helping them or us to [163:51] discover the nature of the one true universe relates to its [163:55] mantle. There's this concept of the set theoretic mantle that I had introduced in [163:59] a way that is extremely interesting. And so it's [164:03] historically quite funny, I think, because this research program [164:07] that grew entirely out of the pluralist point of [164:10] view ended up being picked up by the [164:14] universe point of view research program in a, in a way that is quite important. [164:20] - Can you prove something in the world that you arrived at through forcing and [164:27] then take some of that back to the ground model? [164:30] - Yeah, absolutely. And that's a really powerful argument method, actually. People often [164:34] want to do that. Suppose you're in some set theoretic [164:38] context. You know, you could think about as living in a set theoretic [164:41] universe, and you want to prove something in that universe only. [164:45] But maybe one way to do it is to first [164:49] construct this forcing extension and then use the features [164:53] about this forcing extension to realize that certain things must have already been [164:57] true in the ground model. And then you throw the forcing extensions away and you... [165:01] - Oh, cool [165:01] - ...yeah. So this can happen. To pick a more elementary [165:05] example, if you think about the early days of people [165:08] reasoning with the complex numbers before they really understood them. [165:14] So they would have these algebraic equations that they're trying to [165:16] solve, you know, and they would have the tools and methods of [165:20] doing it, but then in the course of, you know, so they would have to do things to the polynomial [165:24] and change the factors and so on, and produce other polynomials and solve them and [165:28] so on. And sometimes, they could produce solutions. [165:33] in the middle of their construction, they were led to, like, the [165:37] square root of minus five or something, you know, in the [165:40] construction. And they didn't have any meaning for that, but they [165:44] would just do it symbolically, you know. And, and [165:48] eventually, it would turn in, you know, because of the methods that they had, they [165:52] would combine and they would cancel and so on, and all the complex parts would cancel out and they'd end [165:56] up with this, you know, actual answer, you know, three plus square root of [166:00] 17 or whatever. And, and they could check it and it worked. It was [166:04] a solution of the original equation. And so it must have been [166:08] bewildering to them because they would start with this question purely [166:12] in the real numbers, an algebraic question, and they would [166:15] march on their method and proceed through the land of nonsense, you [166:19] know, with these square roots of negative numbers and then end up with [166:23] an answer that was real again that they could verify was correct. [166:29] And so, I view this kind of forcing argument that I was just describing [166:33] in a similar way. You start in set theory, and you go to [166:37] this land of nonsense in the forcing extension, this imaginary world. [166:41] And you argue and you come back. I mean, you make a consequence in the ground model, [166:45] and it's such a beautiful way of arguing. [166:47] - So, speaking of the land of nonsense, I have to ask you about surreal numbers, but [166:51] first, I need another bathroom break. [166:54] All right, we're back, and there's this aforementioned [166:58] wonderful blog post on the surreal numbers, and [167:04] that there's quite a simple surreal number generation [167:08] process that can basically construct all numbers. [167:11] So, maybe this is a good spot to ask, [167:15] what are surreal numbers and what is the way we can generate all numbers? [167:20] - So, the surreal number system is an amazing, [167:24] amazingly beautiful mathematical system that was introduced by John Conway. [167:30] - Rest in peace, one of the great mathematicians ever on this earth. [167:33] - Yes, absolutely. And I really admire his [167:37] style of mathematical thinking and working in mathematics, and the [167:41] surreal number system is a good instance of this. So, the way I think about the [167:44] surreal numbers system is what it's doing is providing us [167:48] a number system that unifies all the other number systems. So, it [167:52] extends the real numbers. Well, not only, it extends the [167:56] integers, the natural numbers and the integers and the rational numbers, and the real [167:59] numbers, but also the ordinals and the [168:03] infinitesimals. So, they're all sitting there inside the surreal numbers, and [168:10] it's this colossal system of numbers. It's not a [168:14] set even. It's a proper class, it turns out, because it contains all [168:17] the ordinal numbers. But it's generated from nothing [168:23] by a single rule, and the rule is, so we're [168:27] gonna generate the numbers in stages, in transfinite sequence of [168:31] stages. And at every stage, we take the numbers that we [168:35] have so far and in all possible ways, we divide them into [168:39] two sets, a lower set and an upper set, or a left set and [168:43] a right set. So we divide them into these two sets, so that [168:47] everything in the left set is less than everything in the right set, and then at that [168:51] moment, we create a new number that fits in the gap [168:56] between L and R. Okay? That's it. That's all we do. So, let me say it again. [169:05] The rule is, we proceed in stages, and at any [169:08] stage, then in all possible ways, we divide the [169:12] numbers we have into two collections, [169:16] the left set and the right set, so that everything in the left set is less than everything in the right [169:19] set. And we create a new number, a new surreal number that will fit in that gap. [169:27] Okay. So, for example, we could start... At the beginning, we don't have any numbers. [169:31] We haven't created anything yet, and so, well, [169:35] we could take nothing, and we could divide it into two sets, the empty lower [169:39] set and the empty upper set. I mean, the two empty sets. [169:43] And everything in the empty set is less than everything in the empty set because that's a vacuous [169:47] statement. So we satisfy the conditions, [169:51] and we apply the number generation rule, which says we should create [169:55] a new number. And this is what I call the Big Bang of [169:59] numbers, the surreal genesis when the number zero is [170:03] born. Zero is the firstborn number that is bigger than [170:07] everything in the empty set and less than everything in the empty [170:09] set. Okay, but now we have this number zero, and so [170:13] therefore, we now can define new gaps. [170:17] Because if we put zero into the left set and have an [170:21] empty right set, then we should create a new number that's bigger than [170:25] zero and less than everything in the empty set, and that number is called the number [170:29] one. And similarly, at that same stage, we could have put zero into the right set, [170:36] and so that would be the firstborn number that's less than zero, which is called [170:40] minus one. So now we have three numbers, minus one, [170:43] zero and one, and they have four gaps because there could be a number below [170:47] minus one or between minus one and zero or between zero and one [170:51] or above one, and so we create those four new [170:55] numbers. The first number above one is called two. The first number between zero and one [170:59] is called 1/2, and then on the negative side, we have minus 1/2 and minus [171:03] two and so on. So now we have, what is that, seven numbers? [171:07] seven numbers. So there's eight gaps between them. So at the next [171:11] birthday, they call them, the next stage will be born all the numbers [171:15] between those gaps, and then between those and between those and so [171:18] on. And as the days progress, we get more and more [171:21] numbers, but those are just the finite birthdays, because as I said, it's a [171:25] transfinite process. So at day omega, that's the [171:29] first infinite day, we're going to create a lot of [171:33] new surreal numbers. So every real number will [171:37] be born at that stage because every real number fills a [171:41] gap in the previously born rational numbers that we had just talked [171:44] about. It's not all the rationals, because actually the rational numbers that are born at the [171:48] finite stages are just the rationals whose denominator is a power of [171:52] two, it turns out. Those are called the dyadic rationals. [171:56] So the real numbers are all born on day omega, [171:59] but also some other numbers are born on day omega, namely, [172:04] the ordinal omega itself is the firstborn number that's bigger than all those [172:08] finite numbers, and minus omega is the firstborn number [172:12] that's less than all those finite numbers. But also, we have [172:16] the number epsilon, which is the firstborn number that's strictly bigger than [172:20] zero and strictly less than all the positive rational [172:24] numbers. So that's going to be an infinitesimal number in that [172:27] gap, and so on. On day omega plus one, we [172:31] get more numbers, and then omega plus two and so on. And the numbers just keep coming [172:35] forever. So, this is how you build the surreal number [172:38] system. And then it turns out you can define the arithmetic [172:42] operations of addition and multiplication in a natural way that [172:46] is engaging with this recursive definition. So we have sort of [172:50] recursive definitions of plus and times for the [172:53] surreal numbers. And it turns out you can prove [172:57] that they make the surreal numbers into what's called an ordered [173:01] field. So they satisfy the field axioms, which means that you have distributivity [173:05] and commutativity of addition and multiplication. [173:09] multiplication, and also you have reciprocals for [173:12] every non-zero number. You can divide by the number. So you can add [173:16] and multiply and divide and subtract. And furthermore, you can take [173:20] square roots. And furthermore, every odd degree polynomial has a root, [173:27] which is true in the real numbers, because if you think about, say, a cubic or a [173:31] fifth degree polynomial, then you know it's going to cross the [173:35] axis, because it has opposite behaviors on the two [173:38] infinities, because it's an odd degree polynomial. So on the positive side, [173:42] it's going to the positive infinity. On the negative side, it would be going to minus infinity. [173:46] So it has to cross. So we know in the real numbers, [173:49] every odd degree polynomial has a root. And [173:53] that's also true in the surreal numbers. So that makes it what's called a [173:57] real closed field, which is a very nice mathematical theory. [174:02] So it's really quite interesting how we can find copies [174:06] of all these other number systems inside the surreal numbers. [174:09] - But the surreal numbers are fundamentally discontinuous as you're worried about. [174:12] What are the consequences of this? [174:14] - Right. So the surreal numbers have a property that they form [174:18] a non-standard model of the real field, which means that [174:24] they provide a notion of infinitesimality that one can use to develop [174:28] calculus on the grounds of Robinson's non-standard theory that I had [174:31] mentioned earlier. But they don't have [174:35] the least upper bound property for subcollections. There's [174:39] no set of surreal numbers, no non-trivial set of surreal numbers [174:43] has at least upper bound, and there are no convergent sequences in [174:47] the surreal numbers. And so for the sort of ordinary [174:51] use in calculus based on limits and [174:54] convergence, that method does not work in the surreal numbers [174:58] at all. So that's what I mean when I say the surreal numbers are fundamentally [175:02] discontinuous. They have a fundamental discontinuity going [175:05] on. But you can still do calculus with them, because you have [175:09] infinitesimals if you use these non-standard [175:12] methods, the infinitesimal-based methods to calculus. And [175:16] people do that. I once organized a [175:20] conference in New York, and we had John Conway as a speaker at that conference. And there [175:24] was a question session, and someone asked him, I mean, [175:28] it's a bit rude, I think, but they [175:32] asked it and the question was, "What is your greatest [175:36] disappointment in life?" I mean, I would never ask a question like that at a conference [175:40] in a very public setting. But Conway was extremely graceful, [175:44] and he answered by saying that, [175:47] "The surreal numbers..." Not the numbers themselves, but the reception [175:51] of the surreal numbers, because he had ambition that the [175:55] surreal numbers would become a fundamental number [175:59] system used throughout mathematics and science, because it was able to do [176:05] non-set analysis, it was able to do calculus, it unified the ordinals and so on. And it's [176:09] such a unifying, amazing structure, beautiful structure [176:13] with elegant proofs and sophisticated ideas all around [176:17] it. And he was disappointed that it never really achieved that unifying [176:25] status that he had the ambition for. And this, [176:29] he mentioned as his greatest disappointment. [176:32] - Yeah, Donald Knuth tried to celebrate it. It never quite took hold. [176:36] - So I don't want to give the impression though that the surreal numbers are not widely studied, [176:40] because there are thousands of people who are... [176:41] - Sure [176:42] - ...studying it. In fact, Philip Ehrlich, who is one of the world experts on [176:45] the surreal numbers, mentioned to me once that Conway was his own [176:50] worst enemy with regard to that very issue, because [176:54] in the Conway style, everything is a game. And he [176:57] treated the surreal numbers as a kind of plaything, a [177:00] toy, and maybe that makes people [177:04] not take it seriously. Although my view is that it is [177:07] extremely serious, useful, and profound, [177:11] and I've been writing a whole series of essays on the surreal numbers for [177:15] my Substack at Infinitely More. And I just find the whole subject so [177:20] fascinating and beautiful. I mean, it's true. I'm not [177:24] applying it in engineering, which maybe was part of this Conway ambition. [177:30] - And I just wanted to, before I forget, mention [177:34] the Conway, turning everything into a game. It is a fascinating [177:38] point that I didn't quite think about, which I think the Game of Life is just an [177:41] example of exploration of cellular automata. I think cellular automata is one of the [177:45] most incredible, complicated, fascinating... It feels like an [177:49] open door into a world we have not quite yet explored. And it's such [177:53] a beautiful illustration of that world, the Game of Life, but calling it a [177:57] game, maybe life balances it, 'cause that's your powerful word, [178:01] but it's not quite a game. It's a fascinating [178:04] invitation to an incredibly complicated and fascinating mathematical [178:08] world. I think every time I see cellular automata and the fact that [178:12] we don't quite have mathematical tools to make sense [178:16] of that world, it fills me with awe. Speaking of a thousand years from [178:20] now, it feels like that is a world we might make some progress on. [178:24] - The Game of Life is a sort of playground for computably undecidable [178:27] questions because in fact, you can prove that the [178:31] question of whether a given cell will ever become alive [178:36] is computably undecidable. In other words, [178:39] given a configuration and you ask, "Will this particular cell ever [178:43] you know, be alive?" "...in the evolution?" And you can prove that that [178:49] question is equivalent to the Halting Problem. It's computably [178:53] undecidable. It's semi-decidable in the sense that if it will [178:57] become alive, then you will know it at a finite stage because you could just run the [179:01] Game of Life algorithm and let it run. And if it ever did come [179:05] alive, you could say, "Yeah, it was alive." But if you've run it for a thousand [179:09] years and it hasn't come alive yet, then you don't necessarily seem to [179:13] have any basis for saying, "No, it won't ever come alive" if the behavior was very [179:17] complicated. [179:18] Maybe if you have a complete understanding of the evolution of the behavior, then you can say [179:22] no, but you can prove you won't always have that understanding- [179:25] ... precisely because the problem is equivalent to the halting problem. [179:28] - And nevertheless, when you sit back and look and visualize the thing, some [179:31] little mini cellular automata civilizations are born and die quickly, [179:35] and some are very predictable and boring, but some have this [179:39] rich incredible complexity. And maybe that [179:43] speaks to a thing I wanted to ask on the halting problem and decidability. [179:50] You've mentioned this thing where if you understand the program deeply, you [179:54] might be able to say something. So can we say something interesting [179:57] about maybe once statistically how many programs [180:02] we know something about in terms of whether they halt or not? Or what does it mean to [180:06] understand a program deeply enough to be able to make a prediction? [180:11] - The main lesson of computability theory in my view [180:16] is that it's never the case that you can have a thorough [180:22] understanding of the behavior of a program by looking at the [180:25] program, and that the content of what you learn from [180:29] a program, I mean, in the most general case, is always obtained just by [180:33] running it and looking at the behavior. And the [180:37] proof of that is there's a theorem called Rice's Theorem, which [180:41] makes that idea completely robust. But I want to just take a little detour towards [180:48] another question riffing on something that you just [180:51] said. Namely, one can ask the question, [180:55] What is the behavior of a random program? So you [180:59] have some formal computing language, you know, and you want to, you know, look [181:03] at the collection of all programs of a certain size. Maybe there's only finitely [181:07] many. And [181:10] can you say something about the behavior of a randomly chosen one, like with a [181:14] certain likelihood it will have a certain behavior? And the answer turns out [181:18] to be extremely interesting. Once years ago, [181:21] Alexey Myasnikov asked me a question. He had this concept of a [181:25] decision problem with a black hole, and what that means is [181:29] it's a decision problem which is possibly difficult in the worst [181:33] case, but the difficulty was concentrated in a very [181:36] tiny region called the black hole. And outside of that black hole, it was very easy. [181:42] And so, for example, this kind of problem is a terrible problem to use if [181:46] you're basing your encryption scheme, you know, you don't [181:50] want to use a black hole problem because if someone can rob the bank [181:54] 95% of the time, you know, then that's not what you want, [181:58] or even any non-trivial percent of the time is too dangerous. [182:01] So you don't want to use problems that are, you know, almost every case is easily [182:08] solved as the basis of your encryption. And the question Alexey [182:12] asked me was, "Does the halting problem have a black [182:15] hole?" You know? And so if we take, say, the standard model of [182:19] Turing machines, it's one-way infinite tape with zeros [182:23] and ones on the tape and so on, the head moving back and forth, and you know, it [182:27] stops when it gets into the halt state, then it turns [182:31] out we proved that there is a black hole. And what that [182:35] means is there's a computer procedure that decides correctly [182:39] almost every instance of the halting problem. Even though the halting problem is not [182:43] decidable, we can decide almost every instance. So, more [182:47] precisely, there's a collection of Turing machine programs [182:51] such that we can easily decide whether a program's in that [182:55] collection or not. And for the programs in the collection, [182:59] we can decide the halting problem for those programs [183:02] easily. And furthermore, almost every program is [183:06] in the collection in the sense that as the number of states goes to, you know, [183:10] becomes large, the proportion of programs in the collection goes to 100%. [183:18] So the asymptotic density of the programs is one. [183:23] And the proof was quite fascinating because it's one of these situations where [183:26] the theorem sounds really surprising, I think, to many people when I first tell it, [183:30] I mean, to computability experts. Then it's sort of [183:34] intriguing to think that you can solve almost every instance of a halting [183:38] problem. But then when they hear the proof, it's [183:42] completely a letdown. Unfortunately, nobody likes the theorem after the proof. [183:47] And so the proof is so simple, [183:50] though. If you know how a Turing machine operates, there's this infinite [183:54] paper tape on which the machine writes zeros and ones, and the head moves [183:58] back and forth according to rigid instructions. And the instructions are [184:01] all of the form, [184:05] if the machine is in such and such a state and it's reading such and such symbol [184:09] on the tape, then it should write this symbol on the tape and it should [184:13] change to this new state specified, and it should either move left or right [184:17] as specified. So a program consists of instructions like that. If you look at, [184:25] If you look at a program, you know, one of the states is the halt state and that's [184:29] when the program halts. But you can calculate how many programs [184:35] don't have any instruction that transitions to the halt [184:38] state. You can easily calculate the proportion. And [184:42] in the limit, it goes to 1 over E squared, 13 and a half [184:46] percent. If you calculate the limit, the [184:50] proportion of programs with end states that don't [184:54] ever halt because they don't have any instruction saying halt. [184:58] Those programs obviously never halt because they can't halt. They don't have any [185:02] instruction that says halt. [185:04] - So 13% of programs, you could say, [185:06] - 13%, you can say they don't halt, because you just look at them and you can understand them. [185:10] - There's no halt state. [185:11] - There's no... They never change to the halt state, so they can't halt. [185:13] - I mean, that nevertheless is beautiful to know. [185:17] - So that's a kind of trivial reason for non-halting, you know. [185:21] And when I first made that observation, I thought, "Okay, this is the proof [185:24] strategy." Because we wanted... I wanted to say at first the [185:28] goal was, look, that's a stupid reason for a program not to [185:32] halt. And I just want to pile up as many stupid reasons as I can think of... [185:37] ...until it gets more than 50%, and then I can say most. [185:43] - That was brilliant. [185:43] - Yeah. That was my goal. [185:44] - I love this. [185:45] - Yeah. So we thought more about it, though, and we hit the [185:48] jackpot because we found one gigantic stupid reason that [185:52] converged to 100%. I mean, in the limit. And so, the stupid reason for a [186:00] program not to halt is that, well, if you think about [186:04] the behavior, see, the head is sitting there. It's on the leftmost cell of the [186:07] tape at the very beginning. It's in the start [186:10] state, and the head is following an instruction. And the instruction says, [186:14] "When you're in the start state," which it is, "and you're reading something on the tape, [186:18] then you should write something and you should change to a new state, and you should either move [186:22] left or right." But half of them move left. [186:27] But if you move left and you are already at the end, then the head falls [186:31] off. And so the computation stops because the head fell off the tape. [186:37] That's a pretty stupid reason. Okay, but that's half of them already just like [186:40] that. Okay, and then some of them went right, and they changed to a new [186:44] state. And amongst those, you know, the new state, half of those ones are going left and [186:48] half are going right from that place, and then most of those are [186:52] changing to a new state. When there's a lot of states, it's very likely that the next state that you [186:56] transition to is new. And so you get this [186:59] random walk behavior, if you know what that means, where half go left and half go right at [187:03] each step. And there's a theorem due to Pólya which is [187:07] called the Pólya recurrence theorem, which says when you have [187:11] a random walk, a one-dimensional random walk, then it's very [187:15] likely to come back to where you started. And when that happens for [187:18] us, then half of them from that place fall off on the next step. [187:23] And so you can show using this kind of analysis that [187:28] the probability one behavior of a random Turing machine is [187:32] that the head falls off the tape before it repeats a [187:35] state. And that is the stupid proof that [187:39] shows how to solve the halting problem. Because when that happens, we can answer the halting problem [187:42] saying, "No, the computation stopped because the machine crashed, not because [187:46] it halted, so therefore it doesn't count as halting on some [187:50] accounts." Or, you know, if you want to define that as halting, crashing as halting, [187:54] then... But in any case, however it is that you set up your formalism, you're [187:58] going to be able to answer the question for the behavior of the [188:01] machine when the head falls off. [188:03] - So statistically, in the limit, you solve the halting problem. [188:08] - Yes, exactly. Computably solve it. Yeah. [188:11] - What do we take from that? Because you didn't solve the halting problem. [188:15] - No, it's impossible to fully solve... [188:17] ...the halting problem correctly in all cases. [188:20] - That's pretty cool. That's kind of... I mean, I don't know. This is... [188:22] - It's a probabilistic way... I mean, it's probabilistic in the sense that [188:26] we're solving almost all instances... [188:28] ...computably. There are versions of this that are maybe more interesting [188:32] from the point of view of complexity theory and actually useful. I mean, there's the whole [188:36] P-NP problem and so on. And there's this genre of NP-complete [188:39] problems, which are problems that are [188:42] infeasible. They would take exponential time to solve them in [188:46] the ordinary way. And they're not known to be polynomial time solvable, [188:50] although in these cases it's an open question whether there is a polynomial time [188:54] algorithm, a feasible algorithm. And for most for most of the NP-complete [189:01] problems, you can prove that there's a [189:04] polynomial time approximation that solves almost all instances... [189:09] ...in a feasible amount of time. So like the knapsack problem, you know, [189:12] packing problems, and so on, other kinds of problems, satisfaction problems, [189:16] when... Depending on how you set up the formalism, you can prove, [189:20] and I've proven many instances of this but also I [189:23] think it's widespread for almost all the NP-complete [189:27] problems, the difficult problems, and these are important problems for industrial [189:31] application when these are problems that we actually want to solve. We can have [189:37] feasible algorithms that solve almost every instance of them. [189:42] - The amount of fields and topics you've worked on is truly [189:45] incredible. I have to ask about P versus NP. This is one of the big [189:50] open problems in complexity theory. So for people who don't know, it's about the relation [189:53] between computation time and problem complexity. Do you think it will ever be [189:57] solved? And is there any chance the weird counterintuitive [190:03] thing might be true that P equals NP? [190:06] - Yeah, that's an interesting question. Sometimes people ask about whether it could be [190:09] independent, which I think is... ...An interesting question for logicians. [190:15] And of course, well, one has to say if you're entertaining [190:19] the idea of independence, you know, over which theory? Because [190:23] every statement is going to be independent over an extremely weak [190:26] theory. So that's, you know, it doesn't make sense to say it's independent all by [190:29] itself. You're only independent relative to a theory, right? So the way I think [190:33] about P-NP is that... I mean, of course it's a theoretical question about [190:40] the asymptotic behavior of these problems. I mean, for a [190:44] problem to be in P means that there, you know, there is a computable [190:48] decision procedure that runs in time bounded by [190:52] some polynomial. But the coefficients on that polynomial could be [190:55] enormous, and the degree could be incredibly high. And so for small values of [191:02] inputs, then it doesn't make sense to talk about this polynomial [191:06] time feasibility with respect to, say, the range of problem inputs that we will [191:10] ever give it in our lifetime or in [191:14] the span of human civilization or whatever. I mean, because it's an [191:18] asymptotic property, it's really in the limit as the [191:22] size of the inputs goes to infinity, that's the only time that polynomial [191:26] or NP becomes relevant. And so maybe it's [191:29] important to keep that in mind when. Sometimes you find [191:33] kind of overblown remarks made about, you know, if P [191:37] equals NP, then this will be incredibly important for human civilization [191:41] because it means that we'll have feasible algorithms for solving these incredibly important- [191:45] ... problems in NP. You know, that it would [191:49] cause immense wealth for human societies and so on because we [191:53] would be able to solve these otherwise intractable problems, and [191:56] that would be the basis of new technology and industry and so forth. I [192:00] mean, people make these kind of remarks, but- [192:03] - Of course [192:04] - ... you have to temper those remarks by the realization [192:07] that P and P equal NP or P not equal NP are [192:11] not about these practical things at all because of the asymptotic [192:15] nature of the question itself. [192:19] Okay, that's on the one hand. But on the second hand, we already have the [192:22] algorithm, so we could use it already, except it's a terrible algorithm because [192:26] it involves all this incredible amount of coding and so on. [192:30] - And on the third hand, like you said, we already have approximation algorithms [192:33] that- [192:34] - Yes [192:34] - ... that from a pragmatic perspective, solve [192:38] all the actual real engineering problems of human civilization. [192:42] - Like the SAT solvers work amazingly well, you know, in lots and lots of [192:46] cases, even though we can prove we don't expect... If P is not equal to NP, then there won't [192:50] be a polynomial time SAT solver. But the actually the SAT solver [192:55] approximations, you know, are really quite amazing. [192:59] - Sorry to ask the ridiculous question, but who is the greatest mathematician... [193:02] ... of all time? Who are the possible candidates? Euler, [193:06] Gauss, Newton, Ramanujan, Hilbert. We [193:10] mentioned Gödel, Turing, if you throw him into the bucket. [193:14] - So this is, I think, an incredibly difficult question to [193:19] answer. Personally, I don't really think this way [193:23] about ranking the mathematicians by greatness. [193:28] - So you don't have, like... You know, some people have a Taylor Swift poster in their dorm room. [193:31] You don't have it. [193:33] - I mean, if you forced me to pick someone, it would probably be Archimedes because- [193:37] ... he had such incredible achievements in such an early [193:43] era, which totally transcended the work of the other people in his era. [193:49] But I also have the view that I want to learn [193:53] mathematics and gain mathematical insight from whoever can [193:57] provide it and wherever I can find it. And this isn't always [194:00] just coming from the greats. And sometimes the greats are doing things [194:05] that are just first and not... You know, somebody else could have easily [194:08] been first. And so there's a kind of luck aspect to it when you go back and [194:12] look at, you know, the achievements. And because of this progress [194:16] issue in mathematics that we talked about earlier, namely, we really do understand things [194:20] much better now than they used to. And when you look back at the [194:24] achievements that had been made, then maybe you can imagine, you know, [194:27] thinking, "Well, you know, somebody else could've, could've had [194:31] that insight also." And maybe they [194:35] would have. It's already a known phenomenon that disparate mathematicians [194:40] end up proving essentially similar results at approximately the [194:43] same time. But okay, the person who did it first is getting the credit and so on. [194:48] - What do you make of that? Because I see that sometimes when mathematicians... [194:52] This also applies in physics and science, where completely separately, [194:57] discoveries are made... ...Maybe at a very similar time. What does that mean? [195:01] - It's relatively common. I mean, I think it's certain [195:05] ideas are in the air and being thought about but not fully articulated, and so [195:11] this is the nature of growth in knowledge. [195:13] - Do you understand where ideas come from? [195:16] - Not really. [195:17] - I mean, what's your own process when you're thinking through a problem? [195:22] - Yeah, that's another difficult question. I suppose it has to do [195:25] with... I mean, my mathematical style, my style as a mathematician, is that [195:32] I don't really like difficult mathematics. [195:37] What I love is simple, clear, easy-to-understand arguments that [195:45] prove a surprising result. That's my favorite [195:48] situation. And actually, so the question of whether it's a new result [195:52] or not is somehow less important to me. And so that has to do with this [195:55] question of the greats and so on, whoever does it first. Because I think, for example, if [195:59] you prove a new result with a bad argument or complicated argument, [196:07] that's great because you proved something new. But I still [196:10] want to see the beautiful simple because that's what I can understand. Also, [196:18] I mean, I'm kind of naturally skeptical about any [196:22] complicated argument because it might be wrong. And- [196:26] ...if I can't really understand it fully, like every single [196:30] step all at once in my head, then I'm just worried maybe it's [196:34] wrong. And so these different styles, sometimes mathematicians get [196:37] involved with these enormous research projects that involve [196:41] huge numbers of working parts and- [196:44] ...different technology coming together. I mean, mathematical technology, not physical [196:48] technology. [196:48] - And sometimes it actually involves now more and more something like the Lean programming [196:52] language where some parts are automated, so you have this gigantic- [196:54] - Yeah, yeah, I see. Well, that's another issue because maybe those things are, you [196:58] know, less subject to skepticism when it's validated- [197:02] ...by Lean. But I'm thinking about the case where the arguments [197:06] are just extremely complicated, and so I sort of worry whether [197:10] it's right or not, whereas you know, I like the simple thing. And [197:13] so, so I tend to have often worked on things that are [197:17] a little bit off the beaten path from what other people are [197:21] working on from that point of view. [197:23] - Your curiosity draws you towards simplicity. [197:25] - Yeah. I wanna work on the things that I can understand and that are s- [197:29] And luckily, I've found that I've been able to make contributions [197:36] that other people seem to like, you know, in this way, [197:40] in this style. And so I've been kind of fortunate from that point of view. [197:44] I mean, my process always, though, and I've recommended this always to my students, [197:51] is just a kind of playful curiosity. So whenever I have... [197:55] whenever there's an idea or a topic, then I just play around with it and [198:03] change little things or understand a basic case and then [198:07] make it more complicated or press things a little bit on this [198:11] side or apply the idea to my favorite example, you know, that's relevant or, [198:17] and see what happens, or you just play around with ideas, and this [198:21] often leads to insights that then lead to [198:24] more methods or more, you know, then pretty soon you're making [198:28] progress on the problem. And so this is basically my [198:32] method, is I just, you know, fool around with the ideas until I can [198:36] see a path through towards something interesting. [198:41] And then prove that, and that's worked extremely well for me. [198:45] So I'm pretty pleased with that method. [198:47] - You do like thought experiments where you anthropomorphize, like you mentioned? [198:51] - Yeah, yeah. So this is a basic tool. I mean, I use this all the time. You know, you [198:55] imagine a set-theoretic model, a model of ZFC as like [199:00] a place where you're living, and you might travel to distant lands by [199:04] forcing, and this is a kind of metaphor for what's going on. Of course, you know, the actual [199:08] arguments aren't anything [199:10] like that because there's not land, and you're not traveling and you're not... [199:13] - But you allow your mind to visualize that kind of thing, in the natural real world. [199:16] - And it helps you to understand, particularly when there's parts of the argument that are in [199:19] tension with one another, then you can imagine that people are fighting or [199:23] something. And those kind of metaphors, you know, or you imagine it in [199:27] terms of a game-theoretic, you know, two players trying to win. So that's kind of [199:31] tension. And those kind of metaphorical ways of understanding a mathematical [199:35] problem often are extremely helpful in realizing, [199:38] aha, the enemy is going to pick this thing to be like [199:42] that because, you know, it makes it more continuous or whatever, [199:46] and then we should do this other thing in order to... So it [199:50] makes you realize mathematical strategies for finding the [199:54] answer and proving the theorem that you want to prove because of the [199:57] ideas that come out of that anthropomorphization. [200:01] - What do you think of somebody like Andrew Wiles, who spent seven years [200:05] grinding at one of the hardest problems in the history of mathematics? And [200:09] maybe contrasting that a little bit with somebody who's also brilliant, Terence [200:13] Tao, who basically says if he hits a wall, he [200:17] just switches to a different problem and he comes back and so on. So it's [200:21] less of a focused grind for many years without [200:25] any guarantee that you'll get there, which is what Andrew Wiles went through. [200:30] Maybe Grigori Perelman did the same. [200:32] - I mean, Wiles proved an amazing theorem, the Fermat's Last Theorem result is [200:36] incredible. This is a totally different style than my own [200:40] practice, though, of working in isolation. I mean, for me, [200:44] mathematics is often a kind of social activity. I have- [200:48] I counted, I mean, it's pushing towards a hundred collaborators, co-authors on [200:53] various papers and so on. And, you know, anybody has an idea they [200:57] want to talk about with me, if I'm interested in it, then I'm gonna wanna [201:01] collaborate with them and we might solve the problem and have a joint paper or [201:04] whatever. You wanna have a joint paper? Let me- [201:06] - Yeah, exactly. Let's go. [201:08] - So my approach to, like, making mathematical progress [201:12] tends to involve working with other people quite a lot rather than just working on [201:16] my- ...own, and I enjoy that aspect very much. So I, [201:20] personally, I couldn't ever do what Wiles did. Maybe I'm missing out. Maybe if [201:24] I locked myself, you know, in the bedroom and just worked on whatever, then, [201:29] uh, I would solve it. But I tend to think that no, actually, like [201:33] being on MathOverflow so much and I've gotten so [201:37] many ideas, so many papers have grown out of the MathOverflow [201:41] conversations and back and forth. Someone posts an, you know, someone posts a [201:45] question and I post an answer on part of it, and then someone else has an idea and it turns into a [201:49] full solution, and then we have a three-way paper coming out of that. That's happened [201:52] many times. And so for me, it's... I enjoy this [201:56] kind of social aspect to it. And it's not just the social [202:00] part. Rather, that's the nature of mathematical investigation as I see it, is [202:08] putting forth mathematical ideas to other people and they [202:12] respond to it in a way that helps me learn, helps them [202:16] learn, and I think that's a very productive way of undertaking mathematics. [202:20] - I think it's when you work solo on mathematics, from my [202:24] outsider perspective, it seems terrifyingly lonely. [202:28] And because you're, especially if you do stick to a single [202:32] problem, especially if that problem has broken many brilliant [202:36] mathematicians in the past, that you're really putting all your chips [202:40] in. And just the torment- [202:41] ...the rollercoaster of day to... that day. Because I imagine [202:47] you have these moments of hopeful break, mini breakthroughs, and then [202:52] you have to deal with the occasional realization [202:56] that, no, it was not a breakthrough, and that disappointment. [203:00] And then you have to go, like, a weekly, maybe daily [203:05] disappointment where you hit a wall, and you have no other person to [203:09] brainstorm with. You have no other avenue to pursue. And it's [203:17] I don't know. The mental fortitude it takes to go through that. But every- [203:21] Everybody's different. Some people are recluse and just [203:24] really find solace in that lone grind. I have to ask about [203:32] Grisha Grigori Perelman. What do you think of him famously [203:36] declining the Fields Medal and the Millennial Prize? [203:39] So he stated, "I'm not interested in money or fame. The prize is [203:43] completely irrelevant to me. If the proof is correct, then no [203:47] other recognition is needed." What do you think of him turning down the prize? [203:52] - I guess what I think is that mathematics is full of a [203:56] lot of different kinds of people. And my attitude is that, [204:00] hey, it doesn't matter. Maybe they have a good math idea, and so I want to [204:04] talk to them and interact with them. And so I think the Perelman [204:07] case, you know, is maybe an instance where, you know, he's [204:15] such a brilliant mind and he solved this extremely famous and [204:19] difficult problem, and that is a huge achievement. [204:23] But he also had these views about, you know, [204:27] prizes and somehow, I don't really fully understand why he would turn it down. [204:33] - I do think I have a similar thing, just observing Olympic [204:36] athletes that, in many cases, don't get paid very much, [204:40] and they nevertheless dedicate their entire lives for the pursuit... [204:42] ...of the gold medal. I think his case is a reminder that some of the greatest [204:47] mathematicians, some of the greatest scientists and human beings do the thing [204:51] they do, take on these problems for the love [204:55] of it, not for the prizes or the money or any of that. [204:59] Now, as you're saying, if the money comes, you could use it for [205:02] stuff. If the prizes come, and the fame, and so on, that might be [205:06] useful. But the reason fundamentally the greats do it is because of the art itself. [205:13] - Sure, I totally agree with that. I mean, I share the view. That's, [205:16] you know, that's why I'm a mathematician [205:20] is because I find the question so compelling and I've spent my whole life [205:24] thinking about these problems. But, you know, if I won an award - [205:32] - Yeah, it's great. It's great. I mean, I'm pretty sure you don't contribute to [205:35] MathOverflow for the wealth, and the power. That you gain. [205:43] I mean, it's genuine curiosity. [205:46] - Well, you asked who the greatest mathematician is, and [205:50] of course, if we want to be truly objective about it, we would need a kind of an [205:53] objective criteria. [205:55] - Criteria, yeah. [205:55] - About how to evaluate the relative strength and the [205:58] reputation of various mathematicians. And so, of course, we should use [206:02] MathOverflow score. ...Because - [206:06] - That you're definitively. I mean, nobody's objectively the greatest mathematician of [206:10] all time. [206:10] - Yes, that's true. I've also argued that tenure and promotion decisions [206:14] should be based... [206:15] - Based on MathOverflow. [206:16] - ...Yeah. So my daughter introduced me to her boyfriend. [206:20] and told me that she had a boyfriend. And I, um- [206:25] - asked him what his MathOverflow... [206:26] - I wanted to know, first of all, what is his chess rating, [206:30] and secondly, what is his MathOverflow score? [206:34] - Oh, man. Well, that's the only way to judge a person, I think. That's, I [206:38] think, objectively correct. Yeah. [206:41] I mean, since you bring up chess, I've got to ask you about infinite chess. I can't let [206:45] you go. You've, I mean, you worked on a million things, but infinite chess is one of [206:49] them. Somebody asked on MathOverflow, the mathematical definition of chess. [206:54] - Right. [206:54] - So can we talk about the math of chess and the math of infinite chess? What [206:58] is infinite chess? [206:59] - Oh, yeah, absolutely. Infinite chess is fantastic. Chess ordinarily is [207:03] played on this tiny, tiny board. It's an eight by eight board, right? So [207:07] when you play chess, normally it's on the eight by eight board. But we want to play [207:10] infinite chess, so on the, on the [207:15] integer board. It's infinite in all four directions, you [207:19] know, but it still has the chessboard pattern, and maybe there's pieces on this board, [207:22] maybe infinitely many pieces we allow. But one difference from [207:26] finite ordinary chess, in infinite chess, we don't play from a standard starting [207:33] position. Rather, you... The [207:37] interesting situation is that you present a position where there's a lot of [207:40] pieces already on the board in a complicated way, and you say, "What would it [207:44] be like to start from this position or from that one?" You know, and we want to [207:48] produce positions that have interesting features, meaning [207:51] mathematically interesting features. And so I can tell you for [207:56] example, probably a lot of people are familiar with, say, the [208:04] mate in two genre of chess problem. [208:07] You know, you have a chess problem and it's white to mate in two, which means that [208:11] white is going to make two moves, but the second move is going to be a checkmate. [208:15] Or maybe mate in three or mate in five or whatever. We can have mate in [208:19] N positions for any N. I mean, in infinite chess, you can create a position [208:26] which is not mate in N for any N, but [208:33] white has a winning strategy that will win infinitely many moves. So in other words, [208:39] let me say it again. There are positions in infinite chess that [208:43] white can definitely win. Infinitely many moves, white is [208:47] going to make checkmate. But there's no particular N [208:51] for which white can guarantee to win in N moves. [208:56] - There's no N? [208:57] - No N. So it's not mate in N for any N, but it's a white [209:01] win, infinitely many. The way to think about it is, [209:05] white is going to win, but black controls how long it takes. [209:09] - Ah, got it. [209:10] - But it's doomed. Black can say, "Well, I know you're gonna win, but this time it's gonna... [209:14] you're gonna take a thousand moves at least." [209:17] Or maybe in a different way of playing, black can say, "Well, I know you're gonna win, but this time you're [209:21] gonna have to take a million moves." For any number, black can say that. So it's [209:25] these really interesting positions. There's a position in my first [209:29] infinite chess paper. So it's black to play in this position, and [209:34] if black doesn't move that rook there, [209:38] then white is gonna checkmate pretty quickly. [209:41] - By the way, can we describe the rules of infinite chess? [209:44] - Right. So the rules of infinite chess are there's just the ordinary pieces, [209:48] and they move on this infinite board, which is just a chessboard, but extended in [209:52] all directions- infinitely, with no edge. So there's no boundary. [209:57] But the pieces move just like you'd expect. So the knights move just the same and the [210:02] rooks move, you know, on the ranks and files, and the bishops move on the same color [210:06] diagonals and, just like you would expect, except they can move as far as they [210:10] want, you know, if there's no intervening piece in the way. [210:13] The one thing is that, okay, so the white pawns always [210:17] move upwards and the black pawns always move downwards, but when they're [210:21] capturing, the pawns, you know, capture on the diagonal. So I [210:25] think the piece movement is pretty clear. There's a couple [210:28] of differences that you have to pay attention to from ordinary chess. For [210:32] example, there's this threefold repetition [210:36] rule in ordinary chess, but we just get rid of this for infinite [210:40] chess because, of course, threefold repetition is just a proxy for infinite [210:44] play. The real rule is infinite play is a draw, not [210:47] threefold repetition is a draw. That's just a kind of convenient [210:51] approximation to the, what I view as the actual rule, which is that [210:55] infinite play is a draw. So the only way to win is to make checkmate on [210:59] the board at a finite stage of play. And if you play infinitely, you [211:03] haven't done that, and so it's a draw. [211:05] - And the pawns can't be converted into- [211:06] - And there's no promotion 'cause there's no edge. Right, exactly. And [211:10] this position that we were just talking about is a position with game value omega, which [211:14] means that because it has an ordinal value, white is [211:18] going to win, but black can play as though [211:21] counting down from omega. What is the nature of counting down from [211:25] omega? If you're black and you need to count down from omega, then [211:30] you have to say a finite number, [211:33] and then after that, it's gonna be at most that many numbers [211:36] afterwards to count down, right? So the nature of counting down from omega is [211:40] that you take this giant step on the first count, [211:44] and then after that, you subtract one each time. You can't subtract one from [211:48] omega because that's not an ordinal. So if you count down from omega, you have [211:52] to go to some finite number, and then if you just subtract one each time, then [211:56] that's how many more moves you get. [211:58] So that's the sense in which black can make it take as long as he wants [212:02] because he can pick his initial number to be whatever he wants. [212:05] - By the way, I just noticed that you were citing a MathOverflow question, which is really [212:09] cool. [212:10] - That's right, yeah. My interest in infinite chess was born on MathOverflow 'cause someone asked [212:14] this question. [212:15] - Noam Elkies asked this question. That's so cool to see a MathOverflow citation [212:19] in an arXiv paper. That's cool. How do you construct the position- [212:28] - Right [212:28] - the position that satisfies this? Is there an algorithm for construction? [212:31] - No. This is an act of mathematical creativity, really, to come up [212:35] with... I had a co-author, my co-author, Corey Evans. He's a [212:38] US national master chess player. [212:42] A very strong chess player. He's also a philosophy professor of law. [212:49] - Your collaborations are wonderful. That's great. [212:53] - So I met him because he was a grad student at CUNY where I was at the time in New York. [212:57] And also he was my son's chess coach for when my son was [213:01] playing chess competitively in elementary school. [213:05] Then Corey was the coach. And so we knew him that [213:08] way. And that was right around the time when I was getting interested in [213:12] infinite chess, and I knew I needed a chess-knowledgeable partner. And [213:19] so Corey was invaluable for the paper because [213:25] the proofs in infinite chess are extremely [213:28] finicky because you create these positions, [213:32] but the details of the argument have to do with kind of chess [213:36] reasoning, you know? My chess reasoning [213:40] wasn't quite up to it because I would create [213:44] the positions. Almost all the positions are ones that I made, [213:48] but this is like after many generations, [213:50] of being corrected by Corey because Corey would come and say, "Hey, you know, this pawn [213:54] is hanging, and it breaks your argument, and" [213:57] "or, or, you know, this bishop can leak out" "of the cage," or whatever. And so... [214:03] the process was I knew kind of [214:07] in terms of these ordinals what we needed to create with [214:10] the position, and I would struggle to do it and create something that sort [214:14] of had the features that I wanted, and then I would show it to Corey and he would say, [214:18] "Look, it doesn't work because of this and that," and so on. And so this kind of back and [214:22] forth was extremely helpful to me, and eventually we, you know, converged [214:26] on arguments that were correct. [214:30] So it's... yeah, it's quite interesting. Also, maybe [214:33] another thing to say is the follow-up paper to this one was a three-way [214:37] paper with also Corey and myself and my [214:41] PhD student, Norman Perlmutter, in which we improved the bound. [214:44] So we were aiming to produce more and more chess positions with higher and higher ordinal values. [214:48] chess positions with higher and higher ordinal values. [214:52] So the initial position was value omega, and then we made omega-squared and omega-cubed in the first paper, [214:56] omega-squared and omega-cubed in the first paper, and then in this three-way collaboration, we made omega to the 4th. [215:00] then in this three-way collaboration, we made omega to the 4th. [215:03] - The title of the paper: The Position in Infinite Chess with Game Value [215:07] Omega to the 4th. [215:09] - Right. And so, at the time, this was the best-known result, [215:13] the sort of state of the art, but since that time, it's been improved [215:17] now dramatically. And, in fact, we know now that every countable ordinal [215:22] arises as the game value of a position in infinite chess, so it's a fantastic result. [215:28] - Before I forget, let me ask about your views on AI and LLMs that are getting [215:37] better and better in mathematics. We've spoken about collaborators, and you have so many [215:41] collaborators. Do you see AI as a potential great collaborator to you as a [215:47] mathematician, and what do you think the future role of those- [215:50] kinds of AI systems is? [215:52] - I guess I would draw a distinction between what we have currently [215:56] and what might come in future years. I've played around with it and I've tried [216:03] experimenting, but I haven't found it helpful at all, [216:07] basically zero. It's not helpful to me. [216:10] helpful to me. And, you know, I've used various systems and so on, the [216:14] paid models and so on. My typical experience is interacting with AI on a [216:22] mathematical question is that it gives me garbage [216:26] answers that are not mathematically correct. [216:30] And so I find that not helpful and also frustrating. [216:36] Like, if I was interacting with a person, the frustrating [216:40] thing is when you have to argue about whether or not, you know, the [216:44] argument that they gave you is right, and you point out exactly the error, [216:47] in the AI saying, "Oh, it's totally fine." And, [216:52] you know, if I were having such an experience with a person, I would simply [216:56] refuse to talk to that person again. [216:58] But okay, one has to overlook these kind of flaws. [217:02] And so I tend to be a kind of skeptic about the value of the current AI systems as [217:09] far as mathematical reasoning is concerned. It seems not [217:13] reliable. Okay, but I know for a [217:17] fact that many, that there are several prominent mathematicians whom I have [217:21] enormous respect for, who are saying that they are using it in a way [217:27] that's helpful, and I'm often very surprised to hear that [217:31] based on my own experience, which is quite the opposite. And so [217:37] maybe my process isn't any good, although, you know, I use it for other [217:41] things, like, you know, for programming things or [217:44] for image generation and so on. It's amazingly [217:48] powerful and helpful. But for mathematical arguments, [217:52] I haven't found it helpful, and maybe I'm not interacting with it in the right way. [217:59] Yet, or it could be. And so maybe I just need to improve my [218:03] skill. But also maybe I wonder, like, these examples that [218:10] are provided by other people maybe involved quite a huge amount of [218:13] interaction, and so I wonder if maybe the mathematical [218:17] ideas are really coming from the person, you know, these great mathematicians [218:21] who are doing it rather than the AI. And so so I tend to be kind of skeptical. But [218:27] also, I'm skeptical for another reason, and that is [218:34] because of the nature of the large language model approach [218:38] to AI doing mathematics. Um, I recognize that the AI is trying to give me [218:48] an argument that sounds like a proof rather than an [218:52] argument that is a proof. The motivation is misplaced. And so I [218:59] worry that this is a very dangerous source of error [219:03] because it often happens in mathematics that, I mean, if I [219:07] think back to when I was an undergrad, you know, here at Caltech, and I [219:11] was a math major eventually, and at that [219:15] time, LaTeX was a pretty new thing, and I was learning LaTeX, and [219:19] so I was typing up my homeworks in LaTeX and they looked beautiful. [219:24] Actually, they looked like garbage. From my current standards, [219:28] I'm sure it was terrible. [219:29] Except at the time, you know, I didn't know anything. I was an undergrad, [219:33] and LaTeX was sort of unheard of. [219:37] And so I was producing these beautifully typeset, you know, [219:40] problem sets, solutions, and so on. And [219:44] I would print it up and submit it and so on, and the grades would come back, [219:47] terrible grades. And I realized what was happening [219:52] is that the, you know, the copy was so beautiful [219:58] mathematically typeset in this way. It looked like the kind of mathematics you find in a [220:01] book, you know? [220:02] Because basically that's the only time you saw that kind of mathematical typesetting was in [220:06] a, in a professional, you know, published book. [220:10] And those me- that mathematics was almost always correct- [220:13] ... in a book, right? And so I had somehow, you know, lost my- [220:20] ... because it was so beautiful, and I'm used to only seeing that kind of type [220:24] setting when an argument was, you know, totally right- [220:27] ... I wasn't critical enough, and making these sort of bonehead [220:31] mistakes in the proofs. And, and so, okay, so I, I corrected this, of course. [220:36] - But this kind of effect is very much real with the modern LLM system. That's right. [220:40] - And so I think that the chat programs [220:44] and so on are producing these arguments that look [220:46] really, they look like a... that's what they're striving to do, [220:50] that it's what they're designed to do. They're not designed to [220:54] make a logically correct argument. They're designed to make something that [220:58] looks like a logically correct argument. And it's easy to get [221:02] fooled if you're not skeptical. And so that's why I worry a bit when [221:05] people rely on AI for mathematical arguments. [221:10] I mean, using... tying them to Lean in the formal proof, [221:13] um verification systems and so on, this is a totally different [221:17] way of operating. But for the sort of ordinary person sitting down and using [221:21] chat to come up with a mathematical [221:23] argument, I think it's a dangerous source of error if you're [221:27] not especially attuned to this very issue that [221:31] the AI is going to produce something that's not grounded in [221:35] mathematical understanding, but rather something that is trying [221:39] to look like something that is grounded [221:41] in mathematical understanding. And those are not the same thing at all. And [221:46] furthermore, I really wonder if one can make a kind of system for [221:50] producing genuine mathematical insight that isn't based in what I would view as [221:56] mathematical understanding as opposed to the text [222:00] generation systems. The methods that are used, you know, they [222:04] don't seem close enough grounded in understanding of the underlying mathematical [222:08] concepts, but rather grounded in [222:12] the way words appear on a page in arguments about those concepts, which are [222:16] not the same. [222:17] - So there's a couple of things to say there. So one, I think there is a real skill in [222:23] providing the LLM system with enough information to be a good collaborator. [222:29] Because you really are dealing with a different... It's not a human being. You really have to load [222:33] in everything you possibly can from your body of [222:37] work, from the way you're thinking, and that's a real skill. And then the [222:41] other thing is, you know, for me, if it's at all anything [222:44] like programming, because I have a lot of colleagues and friends who [222:48] are programmers who kind of feel similarly to you. And for me, I've [222:55] gotten better and better and better at giving as much [222:59] information as possible to the systems in a really structured way, maybe [223:03] because I just like natural language as a way to express [223:07] my thinking. And then the benefit comes from the [223:11] inspiration that the system can provide by its ability to [223:16] know a lot of things and make connections between [223:20] disparate fields and between disparate concepts. And in that way, it provides [223:26] not the answer but the inspiration, the [223:29] handholding, the camaraderie that helps me get to the [223:33] answer, because it does know a lot more than me. Know, like knowledge. And if you [223:41] give it a lot of information and ask the broader questions, it can make some really [223:47] beautiful connections. But I do find that I have to be [223:51] extremely patient, like you said. [223:53] The, the amount of times I'll do something dumb where [223:57] I feel like, "Uh, you don't get this at all, do you?" That's a source of a lot [224:01] of frustration for us humans. Like, "This... Wait, this [224:04] thing doesn't understand at all." If you can have the patience to look past [224:08] that, there might be some brilliant little insights that it can provide. [224:16] - Right. [224:16] - At least for me in the realm of programming. I should say [224:20] programming, there's just so much training data. There's so much [224:23] there. And at least I see [224:27] the light at the end of the tunnel of promising possibilities [224:31] of it being a good collaborator, versus like [224:35] something that gives you really true genius-level insights. [224:39] - Right. It's probably true. Uh, I also find it likely that a [224:43] lot of the... As far as mathematical training data is concerned, [224:48] I just have to assume that math overflow answers are part of the training data. [224:52] - Yes, of course. [224:53] - It's so... [224:54] - And you're... [224:56] - So- [224:56] - I mean, you're talking to yourself, essentially. [224:57] - Yeah, maybe. [225:00] - Sorry for the ridiculously big question, but what idea in mathematics [225:06] is most beautiful to you? We've talked about so many. [225:10] - The most beautiful idea in mathematics is the [225:14] transfinite ordinals. These were the number system [225:17] invented by Georg Cantor about counting beyond [225:21] infinity, just the idea of counting beyond infinity. [225:24] I mean, you count through the ordinary numbers, the natural numbers: zero, one, two, [225:28] three, and so on. And then you're not done because after that comes omega, and then [225:35] omega plus one, and omega plus two, and so on. And you can always [225:39] add one. And so of course after you count through [225:43] all those numbers of the form omega plus N, then you get to [225:47] omega plus omega, the first number after all those. And [225:51] then comes omega plus omega plus one, and so on. You can always add [225:55] one. And so you can just keep counting through the ordinals. It never [225:58] ends. Eventually, you get to omega times three, omega times [226:02] four, and so on. And then the limit of those numbers, the first number that [226:06] comes after all those numbers will be omega squared. [226:10] And this one is the first compound limit ordinal [226:13] because it's a limit ordinal, is one of these numbers, an [226:16] ordinal that doesn't have an immediate predecessor like omega and [226:20] omega times two, omega times three. Those are all limit ordinals. [226:24] But omega squared is a limit ordinal, but it's also a [226:28] limit of limit ordinals because the omega times three, [226:32] omega times four, and so on, those are all limit ordinals that limit up to omega [226:36] squared. And then, of course, you form omega squared plus one, and [226:40] then omega squared plus two, and so on, and it never stops. And it's [226:44] just absolutely beautiful and amazing, and [226:47] furthermore, forms the foundation for these [226:51] transfinite recursive constructions that came later. I mean [226:55] starting with the Cantor-Bendixson theorem that I mentioned. And continuing with, [227:02] the construction of the V hierarchy [227:06] and Gödel's constructible universe is built this way, [227:10] and Zermelo's proof of the well-order principle using the [227:14] axiom of choice is a transfinite recursive construction. And, [227:18] and so the idea of just counting past infinity [227:22] is so simple and elegant, and has led to so much fascinating mathematics. [227:27] - Yeah, the infinity's not the end. And what about [227:30] philosophy? What to you is the most beautiful idea in philosophy? [227:35] - So I have a foot in both fields: philosophy and mathematics, and [227:41] in some contexts I seem to be required to choose whether I'm a mathematician or a [227:47] philosopher. I mean, my training is in mathematics. My PhD, all my degrees are [227:50] mathematics. But somehow I turned myself into a philosopher over [227:54] the years because my mathematical work was engaging with these philosophical [227:58] issues. And so when I went... In New [228:02] York, I had appointments first in mathematics only, but then eventually I was [228:06] also joining the philosophy faculty at the graduate [228:09] center. And when I went to Oxford for the first time, my main appointment was in [228:13] philosophy, and that's also true now [228:16] at Notre Dame although I'm also a concurrent professor in [228:20] mathematics. And I have math PhD students still and philosophy PhD students. And so [228:26] I don't really care to decide whether I'm a mathematician or a philosopher. [228:32] And my work is engaging with mathematics and with [228:35] philosophical issues in mathematics and with plain [228:38] philosophy, and there's this ample region between [228:42] these re- between these two subjects. So it's not necessary to [228:46] choose. I remember when I first went to Oxford and I told my [228:49] daughter that I was going to become professor of philosophy in Oxford, [228:54] And she looked at me plaintively and said, "Uh, [228:59] but, but Papa, you're not a philosopher. Because in her [229:03] mind, you know, her father was the mathematician and her mother was the [229:07] philosopher 'cause my wife, Barbara, is a [229:10] philosopher. Now also at Notre Dame. We're together there. And okay, but [229:17] fortunately, I don't really have to choose between them. So you [229:21] ask about the most beautiful idea in philosophy, and I would have to say [229:25] that I think it's the distinction between truth and proof, the one that we discussed [229:33] already. Um, it's, it's so profound and [229:40] gets at the heart of so many philosophical issues. I [229:44] mean, of course this is a distinction that's maybe born in mathematics [229:48] or mathematical logic, but that's already philosophical to a [229:52] degree, and it's ph- you know, fundamentally a philosophical distinction. The [229:59] truth is about the, [230:03] nature of the world and the way things are. It's about objective [230:06] reality in a sense. Whereas proof is about our [230:10] understanding of the world and about how we come [230:14] to know the things that we know about the world. [230:18] And so to focus on proof is to focus on the interaction that we have with [230:26] the objective reality. And, okay, I'm talking about the reality [230:30] of mathematics, not the physical world, because, as I said, I live in the Platonic realm [230:33] and I interact with mathematical reality, and so [230:37] proof is about the interaction and how we come to know the [230:41] facts that are true in this mathematical [230:45] reality, whereas truth is about what's really the case, [230:48] sort of apart from our knowledge of it. And this is, I think, such a [230:56] core way that I have of understanding the world [231:00] and the nature of logic and reasonings. [231:03] - And the gap between the two is full of fascinating [231:06] mysteries, both in the Platonic realm, but also in the [231:10] physics realm, and I would even say in the human [231:15] psychology, sociology, politics, geopolitics, all of [231:18] it, if you think about proof more generally, which is the process [231:22] of discovery versus the truth itself. And that's our journey whatever [231:31] field we're in. Well, I for one, am grateful for [231:37] how marvelous of a philosopher, mathematician, and human being you [231:40] are. It's truly an honor to speak with you today. [231:43] - Well, thank you so much. It's such a pleasure to be here, and thank you for inviting me. [231:47] - Thanks for listening to this conversation with Joel David Hamkins. [231:51] To support this podcast, please check out our sponsors in the description [231:54] where you can also find links to contact me, ask questions, get [231:58] feedback, and so on. Thank you for listening. As always, happy New Year. [232:05] I love you all.