Computability theory

The following is a conversation with Joel David Hamkins, a mathematician and philosopher specializing in set theory, the foundation of mathematics, and the nature of infinity. He is the number one highest rated user on MathOverflow, which I think is a legendary accomplishment. MathOverflow, by the way, is like StackOverflow but for research mathematicians. He is also the author of several books, including Proof in The Art of Mathematics and Lectures on the Philosophy of Mathematics. And he has a great blog, infinitelymore.xyz. This is a super technical and super fun conversation about the foundation of modern mathematics and some mind-bending ideas about infinity, nature of reality, truth, and the mathematical paradoxes that challenged some of the greatest minds of the 20th century. I have been hiding from the world a bit, reading, thinking, writing, soul-searching, as we all do every once in a while. But mostly, just deeply focused on work and preparing mentally for some challenging travel I plan to take on in the new year. Through all of it, a recurring thought comes to me, how damn lucky I am to be alive and to get to experience so much love from folks across the world. I want to take this moment to say thank you from the bottom of my heart for everything, for your support, for the many amazing conversations I've had with people across the world. I got a little bit of hate and a whole lot of love, and I wouldn't have it any other way. I'm grateful for all of it. This is the Lex Fridman Podcast.

Some infinities are bigger than others. This idea from Cantor at the end of the 19th century, I think it's fair to say, broke mathematics before rebuilding it. I also read that this was a devastating and transformative discovery for several reasons. So one, it created a theological crisis, because infinity is associated with God, how could there be multiple infinities? Also, Cantor was deeply religious himself. Second, there's a kind of mathematical civil war. The leading German mathematician, Kronecker, called Cantor a corrupter of youth and tried to block his career. Third, many fascinating paradoxes emerged from this, like Russell's paradox, about the set of all sets that don't contain themselves, and those threatened to make all of mathematics inconsistent. Finally, on the psychological and personal side, Cantor's own breakdown. He literally went mad, spending his final years in and out of sanatoriums, obsessed with proving the continuum hypothesis. So laying that all out on the table, can you explain the idea of infinity, that some infinities are larger than others, and why was this so transformative to mathematics?

Maybe a quick pause, a quick break, quick bathroom break. You mentioned to me offline we were talking about Russell's paradox and that there's another kind of anthropomorphizable proof of uncountability. I was wondering if you can lay that out. Oh yeah, sure. Absolutely.

I think this is a good moment to talk about Gödel's incompleteness theorems. So, can you explain them and what do they teach us about the nature of mathematical truth? Absolutely. It's one of the most profound developments in mathematical logic. I mean, the incompleteness theorems are when mathematical logic, in my view, first became sophisticated. It's a kind of birth of the subject of mathematical logic. But to understand the theorems, you really have to start a little bit earlier with Hilbert's program because at that time, you know, with the Russell Paradox and so on, there were these various contradictions popping up in various parts of set theory and the Burali-Forti paradox and so on. And Hilbert was famously supportive of set theory.

So, can we just linger on Gödel's incompleteness theorem? Sure.

Can you describe the halting problem? Because it's a thing that shows up in a very useful and, again, traumatic way through a lot of computer science, through a lot of mathematics. Yeah. The halting problem is expressing a fundamental property of computational processes. So given a program, or maybe we think of it as a program together with its input, but let me just call it a program. So given a program, we could run that program, but I want to pose it as a decision problem. Will this program ever complete its task? Will it ever halt? And the halting problem is the question, given a program, will it halt? Yes or no? And of course, for any one instance, the answer's either yes or no. That's not what we're talking about. We're talking about whether there's a computable procedure to answer all instances of this question.

To what degree, sticking on the topic of infinity, should we think of infinity as something real? That's an excellent question. I mean, a huge part of the philosophy of mathematics is about this kind of question, that what is the nature of the existence of mathematical objects, including infinity? But I think asking about infinity specifically isn't that different than asking about the number five. What is- what does it mean for the number five to exist? What are the numbers really, right?

To take a tangent on a tangent, since you mentioned philosophy, maybe potentially more about the questions, and maybe mathematics is about the answers, I have to say you are a legend on MathOverflow, which is like Stack Overflow but for math. You're ranked number one all time on there with currently over 246,000 reputation points. How do you approach answering difficult questions on there? Well, MathOverflow has really been one of the great pleasures of my life. I've really enjoyed it. And I've learned so much from interacting on MathOverflow. I've been on there since 2009, which was shortly after it started. I mean, it wasn't exactly at the start, but a little bit later. And I think it gives you the stats for how many characters I typed, and I don't know how many million it is, but this enormous amount of time that I've spent thinking about those questions, and it has really just been amazing to me.

And, of course, just as an example, you've given a really great, almost historical answer on the topic of the continuum hypothesis. Maybe that's a good place to go. We've touched on it a little bit, but it would be nice to lay out what is the continuum hypothesis that Cantor struggled with. And I would love to also speak to the psychology of his own life story, his own struggle with it. The human side of mathematics is also fascinating. So what is the continuum hypothesis? The continuum hypothesis is the question that arises so naturally whenever you prove that there's more than one size of infinity. So Cantor proved that the infinity of the real numbers is strictly larger than the infinity of the natural numbers. But immediately when you prove that, one wants to know, "Well, is there anything in between?" I mean, what could be a more natural question to ask immediately after that? And so Cantor did ask it, and he spent his whole life thinking about this question. The continuum hypothesis is the assertion that there is no infinity in between the natural numbers and the real numbers. And, of course, Cantor knew many sets of real numbers. Everything in between...

These are expressing the main principle ideas that we have about the nature of sets and set existence. And Cantor had asked about the continuum hypothesis in the late 19th century, and it remained open, totally open until 1938. We should mention, I apologize, that it was the number one problem in the Hilbert's 23 set of problems formulated at the beginning of the century.

And we should mention, maybe this is a good place to even give a bigger picture. One of your more controversial ideas in mathematics, as laid out in the paper, "The Set-Theoretic Multiverse," you describe that there may not be one true mathematics, but rather multiple mathematical universes, and forcing is one of the techniques that gets you from one to the other, so... Can you explain the whole shebang? The whole... Yeah, sure, let's get into it. So the lesson of Cohen's result and Gödel's result and so on, these producing these alternative set theoretic universes. We've observed that the continuum hypothesis is independent and the axiom of choice is independent of the other axioms, but it's not just those two. We have thousands of independence results. Practically every non-trivial statement of infinite combinatorics is independent of ZFC. I mean, this is the fact. It's not universally true. There are some extremely difficult prominent results where people proved things in ZFC, but for the most part, if you ask a non-trivial question about infinite cardinalities, then it's very likely to be independent of ZFC.

So speaking of the land of nonsense, I have to ask you about surreal numbers, but first, I need another bathroom break. All right, we're back, and there's this aforementioned wonderful blog post on the surreal numbers and that there's quite a simple surreal number generation process that can basically construct all numbers. So maybe this is a good spot to ask what are surreal numbers and what is the way we can generate all numbers? So the surreal number system is an amazing, an amazingly beautiful mathematical system that was introduced by John Conway.

And I just wanted to, before I forget, mention Conway turning everything into a game. It is a fascinating point that I didn't quite think about, which I think the Game of Life is just an example of exploration of cellular automata. I think cellular automata is one of the most incredible, complicated, fascinating... It feels like an open door into a world we have not quite yet explored. And it's such a beautiful illustration of that world, the Game of Life, but calling it a game... Maybe life balances it, because that's your powerful word, but it's not quite a game. It's a fascinating invitation to an incredibly complicated and fascinating mathematical world. I think every time I see cellular automata and the fact that we don't quite have mathematical tools to make sense of that world, it fills me with awe. Speaking of a thousand years from now, it feels like that is a world we might make some progress on.

The amount of fields and topics you've worked on is truly incredible. I have to ask about P versus NP. This is one of the big open problems in complexity theory. So for people who don't know, it's about the relation between computation time and problem complexity. Do you think it will ever be solved? And is there any chance the weird counterintuitive thing might be true, that P equals NP? Yeah, that's an interesting question. Sometimes people ask about whether it could be independent, which I think is-

Sorry to ask the ridiculous question, but who is the greatest mathematician of all time? Who are the possible candidates? Euler, Gauss, Newton, Ramanujan, Hilbert. We mentioned Gödel, Turing, if you throw him into the bucket. So this is, I think, an incredibly difficult question to answer. Personally, I don't really think this way about ranking mathematicians by greatness. Um...

Oh, man. Well, that's the only way to judge a person, I think. That's, I think, objectively correct. Yeah. I mean, since you bring up chess, I've got to ask you about infinite chess. I can't let you go. You've, I mean, you've worked on a million things, but infinite chess is one of them. Somebody asked on MathOverflow for the mathematical definition of chess. Right.

Sorry for the ridiculously big question, but what idea in mathematics is most beautiful to you? We've talked about so many. The most beautiful idea in mathematics is the transfinite ordinals. These were the number system invented by Georg Cantor about counting beyond infinity, just the idea of counting beyond infinity. I mean, you count through the ordinary numbers, the natural numbers, zero, one, two, three, and so on, and then you're not done because after that comes omega and then omega plus one and omega plus two and so on. And you can always add one. And so of course after you count through all those numbers of the form omega plus N, then you get to omega plus omega, the first number after all those. And then comes omega plus omega plus one and so on. You can always add one. And so you can just keep counting through the ordinals. It never ends.