YouSaid · the spoken record

Joel David Hamkins

We hold 128 passages that may be Joel David Hamkins’s. We do not publish them until we can confirm who spoke. See the correction.

On the record 2025

159
LINES ON RECORD
1
SITTING OR EPISODE
1
SOURCE
2025
ON RECORD

podcast

This is everything the corpus holds for Joel David Hamkins. It is not everything they have said on the record.

Every line below is reproduced as it was said and credited to the record it came from, and links to that record wherever it can be linked. Nothing here is summarised or generated. Directory · Search · Corrections

  1. “What are the techniques? So, one thing is that because of the incompleteness theorem, we know that this going And so we're already aware of the fact that there will always be these independence phenomenon for any theory that we write. And furthermore, some of those theories, we won't even be able to prove that they're consistent, like the consistency of the own theory. So that's called the consistency strength hierarchy. So it's a direct consequence of Girdle's second incompleteness theorem that for any theory we can write down then towering over it is this incredibly tall tower of consistency, strength, where the strength and theories aren't just adding another axiom, but they're adding another axiom even whose consistency was not provable in the previous layers of the hierarchy.”

    Lex Fridman Podcast31 December 2025Source ↗

  2. “But that's an interesting way to put it, I think, because it reminds me of this when I was a graduate student in Berkeley, there was another graduate student who was working with a non-logic professor in C-STAR algebras or something like this. So it's a part of analysis or functional analysis. And they were looking at a question and it turned out to be independent of CFC, right? And the attitude of this other professor was that, oh, I guess I asked the wrong question.”

    Lex Fridman Podcast31 December 2025Source ↗

  3. “Yeah, sure. Let's get into it. So the lesson of Cohen's result and girdle's result and so on, he's 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 CFC. I mean, this is the fact. It's not universally true. There are some extremely difficult prominent results where people proved things in CFC. For the most part, if you ask a non-trivial question about infinite cardinalities, then it's very likely to be independent of CFC. And we have these thousands of arguments, these forcing arguments that are used to establish that. And so how should we take that? I mean, on the one hand,”

    Lex Fridman Podcast31 December 2025Source ↗

  4. “To build this alternative set theoretic reality, the constructual universe. And then he proves that the aximo choice is true there and also the continuum hypothesis is true there. And it's just amazing. Really beautiful argument. Okay, so then for the other part of the independence, that's only half of it because Girdle shows basically that you can't refute the continuum hypothesis. But that's not the same thing as proving that it's true. He showed that If set theories consists in without the continuum hypothesis, then it's consistent with the continuum hypothesis. So that's not the same thing as proving that it's true. And then it didn't come until 1963 when Paul Cohen invented the method of forcing and proved that if this a model of set theory, then this a model of set theory in which the continuum This is false So, Cohen also is”

    Lex Fridman Podcast31 December 2025Source ↗

  5. “So he solved this. This is the same result where he answers the safety question of the axiom of choice, but also for the continuing hypothesis. They're true in the same center at a universe. We get, so if ZF without the axial choice is consistent, then so is ZFC plus the continuum hypothesis is the result. 1938. It's really such a beautiful argument. It's just incredible, I think, because he's building an alternative mathematical reality. That's the structure of the proof, is that, okay, if there's any mathematical reality, if there's any set theoretic world, then we're going to build another one, a separate one, a different one, maybe different. Maybe it's the same as the original one. It could be if we started already in the one that he built, then it would be the same. But there's no reason to assume it was the same. So he has this kind of model construction method.”

    Lex Fridman Podcast31 December 2025Source ↗

  6. “And then it's totally open. Hilbert asks about it at the turn of the 20th century. Nobody has any clue. There's no answer coming. Until 1938, this is four decades later, right? So a long time. And Kurt Girdle proved that. Half of it, what he proved is that If the axioms of set theory are consistent, then there is a set theoretic world where both the axiom of choice and the continuum hypothesis are true. So, what he's doing is showing this is called the constructible universe, girdles L.”

    Lex Fridman Podcast31 December 2025Source ↗

  7. “Core fundamental question to ask. So it seems quite natural that he would put it on the list. There were other logic related questions, though, like Hilbert's tenth problem is also related to logic. This is the question about Diophantine equations. And he asked to provide an algorithm to decide whether a given Deafantine equation has solution in the integers. So a Diophantine equation is just, I mean, it's a maybe a fancy way of talking about something that's easy to understand, a polynomial equation, except it's not just one variable, many variables. So you have polynomials in several variables over the integers, and you want to know, can you solve it? So the problem is, as stated by Hilbert, Provide an algorithm for answering the question whether a given polynomial equation has a solution in the integers.”

    Lex Fridman Podcast31 December 2025Source ↗

  8. “So that must have been part of Hilbert's thinking about why it's so important to have a uniform foundation and set theory was playing that role at the time. Now, of course, we have other possible foundations coming from category theory or type theory. And this univalent foundations now. So this sort of competing foundations now, there's no need to just use one foundation, one set theoretic foundation, although set theory continues to, in my view, have an extremely successful meta-mathematical analysis as a foundation, I think, is much more successful in set theory for any of those other foundations, but it's much less amenable, though, to things like computer proof and so on, which is part of the motivation to find these alternative foundations. So, yeah, okay, so just talk about Hilbert, though. I think he was motivated by the need for a unifying foundation of mathematics and said theory was playing that role and the continuum hypothesis is such a”

    Lex Fridman Podcast31 December 2025Source ↗

  9. “The proof methods for that theorem come from other parts of mathematics, you know, this topological proofs and so on. And so what is that, how does that work? I mean, if you have totally different axiom systems, but you're using results from one subject in another subject, it's somehow incoherent unless this one underlying subject. So the unity of mathematics was provided by the existence of a mathematical foundation like set theory, and at the time it was set theory. And so it's critically important to be able to have a single theory in which one views all of mathematics as taking place to resolve that kind of transfer and borrowing phenomenon that was definitely happening.”

    Lex Fridman Podcast31 December 2025Source ↗

  10. “With their own axioms, separate axioms, right? But sometimes it happens like when you're proving, say, the fundamental theorem of algebra, you know, that the complex numbers are an algebraically closed field that you can solve any polynomial equation in.”

    Lex Fridman Podcast31 December 2025Source ↗

  11. “And we already discussed how Hilbert's views on the nature of set theory and the fundamental character that where he said no one will cast us from the paradise that Cantor has created for us. So I think Hilbert was convinced by Cantor on the importance and the fundamental nature of the continuum hypothesis for the foundations of mathematics, which was a critically important development for the unity of mathematics. I mean, before set theory emerged as a foundation of mathematics, there were, you know, this different subjects in mathematics, this algebra and this analysis, real analysis and topology and geometry. And so there's all these disparate subjects.”

    Lex Fridman Podcast31 December 2025Source ↗

  12. “I find it a little hard to believe that Hilbert would have conceived of his list in the same way that we now take his list. I mean, having observed the century unfold, we know that that list of twenty three problems did in fact guide whole research programs, and it was extremely important and influential. But at the time, Hilbert would have no reason to think that that would be true. And he was just giving a lecture and had a list of problems that he thought were very important. And so I would find it more reasonable to think that he was just making a list of problems that he thought were extremely interesting and important and fundamental in a way without the kind of heavy burden of guiding this 20th century research, although it turns out that, in fact, that's exactly what they did.”

    Lex Fridman Podcast31 December 2025Source ↗

  13. “So, right. So Hilbert had introduced at his famous address at the turn of the century these list of problems that he thought could guide or were important to consider in the coming century of mathematics. I mean, that's how people talk about it now, although I'm not sure at all. Of course, I can't really speak for Hilbert at all, but if you were a very prominent mathematician,”

    Lex Fridman Podcast31 December 2025Source ↗

  14. “I argue that it's really the philosophy of structuralism that leads them to omit the earle elements because it turns out that if you adopt ZFC axioms with earle elements ZFCU it's called or ZFA. Than any structure that exists, any mathematical structure that exists in that set theoretic universe with the atoms is isomorphic to a structure that doesn't use the atoms at all.”

    Lex Fridman Podcast31 December 2025Source ↗

  15. “So the ZFC axioms were, the axioms that were put forth first by Zermello in nineteen oh eight in regard to his proof of the well order using the axiom of choice. That wasn't Feli ZFC at that time, it was just Zermello theory because he sort of, there was a kind of missing axiom, the replacement axiom, and the foundation axiom were added. Axiomization, which became sort of standard. Actually, there's another aspect which is Zermelo's original theory allowed for the existence of Er elements or these atoms, mathematical objects that are not sets, but out of which we build the set theoretic universe, whereas set theorists today generally don't use Er elements at all”

    Lex Fridman Podcast31 December 2025Source ↗

  16. “Realms even at the level of projective hierarchy, which are sets that you can define by using quantifiers over the real numbers themselves. So you get this hierarchy on top of the Borel hierarchy, the hierarchy of projectively definable sets. And it turns out that if you have enough large cardinals, then the projective sets also are Always either countable or equanumerous with the whole realign. And then one can try to go beyond this and so on. So I view all of those results which came, you know, in the past 50 years, the later ones, as fulfilling this candor idea that goes back, you know, one hundred and twenty years to his idea that we would prove the continuer, well, this is by establishing more and more instances for greater and greater complexity of sets. But of course,”

    Lex Fridman Podcast31 December 2025Source ↗

  17. “And candor proved with a clothes that no, it's impossible. Every close set is either countable or echonerous with the whole real line. What the CANR program for solving the continuum of all this was. Sort of working up. So you did it for OpenSets and for closed sets, and you sort of work up maybe he wants to go into what are called the BREL sets, which are sort of combinations of open and closed sets. And there's a vast hierarchy of Borel complexity. And it turns out that the continuum hypothesis has been proved also for the Borel sets in this hierarchy. But then one wants to go beyond. What about more complicated sets? So there's this hierarchy of complexity for sets of real numbers and Cantor's idea was to sort of work your way up the hierarchy by proving that the continuing hypothesis was more and more true for those more and more complicated sets based on our understanding of the earlier cases. And that has been carried out to a remarkable degree. It turns out that one needs, one begins to need large cardinal assumptions, though, in order to get to the higher”

    Lex Fridman Podcast31 December 2025Source ↗

  18. “Oh, yeah, sure. So a set of reels is open if every point that it contains is surrounded by a little interval of points, the whole tiny little interval. But that tiny little interval is already just by itself equinormous through the whole line. So that's why the question is sort of easy for OpenSet. A closed set is a complement of an open set. And there's a lot of closed sets that are really complicated of varying sizes. So of course any closed interval is a closed set, but it's not only those. There's also things like the cantor set, which you get by omitting middle thirds. Maybe some people have seen this construction. Or you can imagine sort of randomly taking a lot of little tiny open intervals all over the line and so on. So that altogether would be an open set and the complement of it would be a closed set. So you can imagine just kind of tossing down these open intervals and what's left over is the closed set. Those sets can be quite complicated. And they can have isolated points, for example, if the two open intervals were just kissing and leaving only the one point between them. But also you could have”

    Lex Fridman Podcast31 December 2025Source ↗

  19. “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. So 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, I mean, everything that's in that interval would be equinumerous with some set of real numbers. But we know lots of sets of real numbers. I mean, there's all these various closed sets, Canner sets, and so on, this Vitali said. We have all kinds of sets of real numbers. And so you might think, well, if the continued hypothesis is false, then we probably seen the set already. We just have to prove that it's strictly in between.”

    Lex Fridman Podcast31 December 2025Source ↗

  20. “So, the continuum of all this is the question that arises so naturally whenever you prove that there's more than one size of infinity. So candor proved that the infinity of the real numbers is strictly larger than the infinity of the natural numbers. But immediately when you prove that, Wants to know well, is there any?”

    Lex Fridman Podcast31 December 2025Source ↗

  21. “So, I think when I first joined Math Overflow, I was basically one of the only, one of the few people in logic who was answering. I mean, there were other people who know some logic, particularly from category theory and other parts of mathematics that aren't in the most traditional parts of logic, but they were answering some of the logic questions. So I really found myself able to make a contribution in those very early days by engaging with the logic related questions, but there weren't many logic people asking questions either. But what I found was that there was an enormous amount of interest in topics that were logic adjacent. So a question would arise, you know, in group theory, but it had a logic aspect or an analysis or whatever, and there would be some logic angle on it. And what I found was that I was often able to figure out an answer.”

    Lex Fridman Podcast31 December 2025Source ↗

  22. “The field sort of moves on to more difficult, interesting questions. Whereas in philosophy this a little bit true that there's progress, but meanwhile, it's also true that there are these eternal questions that have been with us for thousands of years. And in fact, so much so that you can find a lot of philosophers arguing that the important contribution of philosophy is in asking the questions rather than answering them. Because it's hopeless to answer them. I mean, the nature of these deposit questions is so difficult, less of a sense of progress is what I'm trying to say. I don't see any reason to think that the progress in mathematics in the growth in our mathematical understanding and knowledge won't simply continue. And so a thousand years from now, maybe the mathematics that they will be doing at that time”

    Lex Fridman Podcast31 December 2025Source ↗

  23. “It's interesting to me because I have my feet into worlds of mathematics and philosophy and to compare the differences between these subjects. And one of the big, there's many cultural differences, but one of the big cultural differences is towards the idea of progress in the subject. Because mathematics has huge progress. We simply understand the mathematical ideas much, much better continually improving our understanding and there's growth in knowledge. We understand the nature of infinity now better than they did a hundred years ago. I mean, definitely better. And they understood it better a hundred years ago than they did, you know, for the previous thousands of years and so on. So in almost every part of mathematics, there's improved understanding of the core issues so much so that the questions at hand become totally different.”

    Lex Fridman Podcast31 December 2025Source ↗

  24. “That well, there was something that dissatisfied him about that situation, which is that the Canerhume principle Does not seem to give you a criteria for which things are numbers. It only tells you a kind of identity criteria for when are two numbers equal to each other. Well, two numbers are equal just in case the sets of those sizes are equanumerous. So that's the criteria for number identity. But it's not a criteria for what is a number. And so this problem has become known as the Julius Caesar problem because Frege said, we don't seem to have any way of telling from the Hume principle whether Julius Caesar is a number or not. So he's asking about the essence of number and whether, of course, one has the sense that he picked maybe what he was trying to present as a ridiculous example because maybe you have the idea that, well, obviously Julius Caesar is not a number and there's a lot of philosophical writing that seems to take that line also that obviously the answer.”

    Lex Fridman Podcast31 December 2025Source ↗

  25. “Yeah, I think so, because I guess part of the point of structuralism is that it doesn't make sense to consider mathematical objects or individuals in isolation. What's interesting and important about mathematical objects is how they interact with each other and how they behave in a system. And so maybe one wants to think about the structural role that the objects play in a larger system, a larger structure. There's a famous question that Frege had asked, actually, when he was looking into the nature of numbers, because in his logic program, right, he was trying to reduce all mathematics to logic. And in that process, he was referring to the Kanner-Hume principle that, you know, whenever two sets are equinumerous, then they have the same number of elements. I mean, if and only if. And he founded his theory of number on this principle, but he recognized”

    Lex Fridman Podcast31 December 2025Source ↗

  26. “You know, in a mathematical structure is irrelevant with regard to any mathematical property of that structure. And so So, to ask a question, like, what is the number four really? Is an anti-structuralist thing? Because if you have a structure, say the natural numbers, you know, with all the numbers in at 0, 1, 2, 3, 4, and so on, then I could replace the number four with something else like this bottle of water could play the role of the number four in that structure. And it would be isomorphic. And it wouldn't matter at all for any mathematical purpose to use this alternative mathematical system. That's to say that we don't care what the number four is really. That is irrelevant. The only thing that matters is what are the properties of the number four in a given mathematical system, you know, and recognizing that there are other isomorphic copies of that system and the properties of that other system's number four are going to be identical to the property.”

    Lex Fridman Podcast31 December 2025Source ↗

  27. “Structuralism is a philosophical position in mathematics or the philosophy of mathematics by which one emphasizes that what's important about mathematical objects is not what they're made out of or what their substance or essence is, but rather how they function in a mathematical structure. And so what I call the structuralist attitude in mathematics is that we should only care about our mathematical structures up to isomorphism. If I have a mathematical structure of a certain kind and I make an exact copy of it using different individuals as to form the elements of that structure, then the isomorphic copy is just as good mathematically and there's no important mathematical difference that would ever arise from working with this isomorphic copy instead of the original structure. And so therefore, that's another way of saying that the substance of individual”

    Lex Fridman Podcast31 December 2025Source ↗

  28. “What it means to say that there's an apple on my desk and to give an account of what that physical existence really is at bottom, I think, is totally absent. Whereas we do seem to have a good A much more satisfactory account of the nature of abstract existence. I mean, I can talk about the nature of the empty set. This is the predicate which is never true or something like that. I can talk about those kind of logical properties or the singleton of the empty set and so on. I mean, of course, it's very difficult if you go very far with it, but the point is that it doesn't get more and more mysterious the more that you say it becomes only more and more clear.”

    Lex Fridman Podcast31 December 2025Source ↗

  29. “Since it has a profound mystery, in fact, it becomes more and more mysterious the more physics we know. I mean back in, say, Newtonian physics, then one had a picture of the nature of physical objects as, you know, little billiard balls or something, or maybe they're infinitely divisible or something like that. Okay, but then this picture is upset with the atomic theory of matter, but then that picture is upset when we realize that the atoms actually can be split and consists of electrons and protons and neutrons and so on. But then that picture is upset when we realize that those things themselves are built out of quarks and leptons and so on. And who knows what's coming? And furthermore, all of those things, the nature of their existence is actually as wave functions in some cloud of probability and so on. And so it just becomes more and more and more mysterious the more we learn and not at all clarifying. And so the nature of”

    Lex Fridman Podcast31 December 2025Source ↗

  30. “Imagine a certain kind of steam locomotive, and I describe the engineering of it and the weight of it and the nature of the gear linkages. And I show you schematic drawings of the whole design and so on. And we talk in detail about every single detailed aspect of this steam locomotive. But then suppose after all that conversation, I say, okay, now I would like you to tell me what would it mean for it to exist physically? I mean, as opposed to just being an imaginary steam locomotive, what could you possibly say about it? I mean, except by saying, oh, I just mean that it exists in the physical world. But what does that mean? That's the question, right? It's not an answer to the question. That is the question. So I don't think that there's anything sensible that we can say about the nature of physical.”

    Lex Fridman Podcast31 December 2025Source ↗

  31. “Sometimes people find it problematic to talk about the existence of abstract objects such as numbers, and there seems to be a kind of wish that we could give an account of the existence of numbers or other mathematical objects or abstract objects that was more like the existence of tables and chairs and rocks and so on. And so there seems to be this desire to reduce mathematical exists to something that we can experience physically in the real world. But my attitude about this attempt That it's very backward, I think, because Don't think we have such a clear existence of the nature of physical objects, actually. I mean, we all have experience about existing in the physical world as we must because we do exist in the physical world. But I don't know of any Satisfactory account of what it means to exist physically. I mean, if I ask you, say”

    Lex Fridman Podcast31 December 2025Source ↗

  32. “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 is... Isn't that different than asking about the number five? What does it mean for the number five to exist? What are the numbers really? This is maybe one of the fundamental questions of mathematical ontology. I mean, there's many different positions to take on the question of the nature of the existence of mathematical objects or abstract objects in general. And there's a certain kind of conversation that sometimes happens when you do that. And it goes something like this”

    Lex Fridman Podcast31 December 2025Source ↗

  33. “Ha ha ha. It's interesting to think about well, what if there were infinitely many people in your group? Then it's not true anymore. The theorem fails. In fact, you can arrange that everyone is strictly more pointed at than pointing. And also if everyone has even just $1 bill, then you can arrange that afterwards everyone has infinitely many dollar bills. Because in terms of cardinality, that's the same. It's just, say, countable infinity in each case. If you had countably many friends and everyone has $1 bill, then you can arrange a pattern of passing those dollar bills amongst each other so that afterwards everyone has infinitely many dollar bills. What you need is for each person to be attached to one of the train cars or something. So think of everyone as coming from Hilbert's train.”

    Lex Fridman Podcast31 December 2025Source ↗

  34. “and therefore it can't be possible that we're all more pointed at than pointing. And this proof illustrates something, it's one of my habits that I suggest in the book, to anthropomorphize your mathematical ideas. So you should imagine that the mathematical objects that are playing a role in your question are people or active somehow animals or something that maybe have a will and a goal and so on. This is this process of anthropomorphizing. And it often makes the problems easier to understand because we all are familiar with the fact that it's difficult to make money and the proof is totally convincing because of our knowledge that we can't make money as a group by trading dollars between us, you know, without any new money coming into the group.”

    Lex Fridman Podcast31 December 2025Source ↗

  35. “Because I was pointed at by more people than I'm pointing. So I got $10, but I only paid out seven dollars. And similarly, you got paid twenty dollars, but you only paid out fifteen dollars. So if everyone is more pointed at than pointing, then everyone makes money. But it's obviously impossible for us to make money as a group by just trading money with ourselves.”

    Lex Fridman Podcast31 December 2025Source ↗

  36. “I don't think you can. Okay, so can you arrange it so that everyone is more pointed at than pointing? And in my book, I give a couple of different proofs of this. I think I give an induction proof and there's another proof. I think there's three different proofs in there. But why don't we just talk about my favorite proof? Suppose it were possible to arrange that we're all more pointed at than pointing. Now what we're going to do, we're going to agree. Going to give a dollar to everyone that we're pointing at. Okay. So, what happens? Everybody made money.”

    Lex Fridman Podcast31 December 2025Source ↗

  37. “Let's do a proof. There's one in the book. We can talk about it. I think it's a nice problem. It's in the discrete math, yeah, the 5.1, that one, more pointed at than pointing. Okay, so this is the following problem. Suppose you're gathered with some friends, you know, in a circle, and you can point at each other, however you want, or yourself, whatever. It doesn't matter. And you can point at more than one person, you know, use all your fingers or your feet or whatever you want. So maybe you point at three of your friends or something and they point at two or three of their friends or whatever and one person is pointing at ten people and somebody isn't pointing at anybody maybe. And various people are pointed at also, right? So the question is, Could we arrange a pattern of pointing?”

    Lex Fridman Podcast31 December 2025Source ↗

  38. “Many universities have such a course, the proof writing course, which is usually taken by students who have learned some mathematics. Usually they've completed maybe the calculus sequence and are making the kind of transition to higher mathematics, which tends to involve much more proof. And it's a kind of challenging step for them. So many math departments have this kind of course on proof writing where the students would get exposed to how to write proofs. And I wasn't happy with most of the other books that exist for those kind of courses. And the reason was that they were so often so dull because they would concentrate on the totally uninteresting parts of what it's like to write, approve this kind of mechanistic procedures about how to write a proof. You know, if you're going to prove an implication, then you assume the hypothesis.”

    Lex Fridman Podcast31 December 2025Source ↗

  39. “So, this is something I find so wonderful to teach young mathematicians who are learning how to become mathematicians and learning about proof. And I wrote that book when I was teaching such a proof writing class in New York.”

    Lex Fridman Podcast31 December 2025Source ↗

  40. “Meaning, arithmetic, and finite combinatorial things such as Turing machine computations and so on. So in fact, all those finite combinatorial processes are formalizable inside arithmetic with the standard arithmetization coding process. But let me just be a little bit informal and say, suppose we could write down a complete theory of elementary finite mathematics. So we have an axiomization of that theory. Then we could produce all possible theorems from those axioms in the way that I was describing earlier with Hilbert's program. I mean, if we had a complete theory of elementary mathematics, we could construct a theorem enumeration machine that produced all the theorems and only the theorems from that theory.”

    Lex Fridman Podcast31 December 2025Source ↗

  41. “It's absolutely beautiful. Yeah, I agree. And it's following the same logic of Russell and Cantor. I mean, going back to Cantor basically, because Russell is also quoting Cantor in his letter to Frege. So therefore, the conclusion is that the halting problem is not computably decidable. And now we can immediately prove Girdles that you're using this. Actually, it's an immediate consequence. So, why don't we just do that? I view this as the simplest proof of Girdle's theorem. You don't need the Girdle sentence to prove Girdle's theorem. You can do it with the halting problem. So suppose that we could write down a computable axiomization of all of the true facts of elementary mathematics.”

    Lex Fridman Podcast31 December 2025Source ↗

  42. “Okay, so I'm just grabbing program Q, and program Q takes as input P, which is itself a program. And the first thing it does is it asks the halting subroutine program, would P halt on P? And if the answer comes back from the subroutine, yeah, that would hold, then what I do in program Q is I immediately jump into an infinite loop. So I don't halt. If P halts on P, I don't halt. But if the answer came back no, P is never going to hold on P, then I halt immediately. Okay, so that's it. I've described what Q does. And the thing about Q is that Q's behavior on P was the opposite of P's behavior on P. I mean, that's how we designed Q, specifically so that Q on P had the opposite behavior as P on P. Okay, so now, of course, what do we do? Well, the same thing that Russell did and so forth and candor we ask, well, what would Q do on Q?”

    Lex Fridman Podcast31 December 2025Source ↗

  43. “Okay, suppose toward contradiction, I mean, all these proofs are by contradiction, and this argument is going to be a diagonal argument in the same style as the Russell argument and the candor argument and Girdle's argument that we haven't talked about yet, so many diagonal arguments come in. So suppose towards contradiction that we had a procedure for determining whether a given program halted on a given input. Now, let me describe I'm going to use that procedure as a subroutine in the following process. And my process, let's call it Q, process Q. And it takes as input a program P. And the first thing it does is it asks that subroutine, hey, would P halt if I ran it on P itself, that's the diagonal part because we're applying P to P, right?”

    Lex Fridman Podcast31 December 2025Source ↗

  44. “And I could keep running it. And maybe in a week it would halt. And at that time, I could say, yes, it halted. So I can get the yes answers correctly for halting all the yes answers. But the problem is If it didn't halt yet, like maybe I waited a thousand years and it still hasn't halted. Don't seem entitled to say no, it's not going to halt. Yeah, because maybe in a thousand in one year it'll halt. And so at no point can I seem to say no. In order to say no, it won't ever halt.”

    Lex Fridman Podcast31 December 2025Source ↗

  45. “For any one instance, the answer is 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. So it's a decision problem is given as a scheme of instances for all possible programs that you could ask about what I want to know is, is there a computable procedure that will answer those questions? And it turns out the answer is no. The halting problem is computably undecidable. There is no computable procedure that will correctly answer all instances of whether a given program will halt. And of course, we can get half the answers in the sense that. Give me a program and you say, Will this halt? And I could take that program and I could run it.”

    Lex Fridman Podcast31 December 2025Source ↗

  46. “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? The halting problem is the question, given a program, will it halt yes or no? Course”

    Lex Fridman Podcast31 December 2025Source ↗

  47. “And discussing. So the incompleteness theorem is the question whether we could say write down a theory for arithmetic, say for the standard model of arithmetic where we have the natural numbers and plus and times and zero one and less than and so on in that formal language we can express an enormous number of statements about the nature not only of arithmetic but actually by various coding methods we can express essentially all of finite mathematics in that structure. So the question would be can we write down a computable list of axioms that will answer all those questions by proof? In other words, we want to have a complete theory. A theory of arithmetic that proves all and only the true statements. That would be the goal. Hilbert would love that. I mean that would be supportive of Hilbert's program to have such a complete theory of arithmetic”

    Lex Fridman Podcast31 December 2025Source ↗

  48. “Systems, there's a lot of different formal proof systems that exist that are studied by the proof theorists. And all of them have the property that they're sound, which means that if the premises of the argument are all true in a structure and you have a proof to get a conclusion, then the conclusion is also true in that structure. So that's what it means to be sound. Proofs preserve truth. Their truth preserving arguments. But also... The proof systems are also generally complete. They're both sound and complete, and complete means that whenever a statement is a consequence, a logical consequence of some other statements, which means that whenever the assumptions are true, then the consequence is also true in the structure. Whenever you have a logical consequence, then there is a proof of it.”

    Lex Fridman Podcast31 December 2025Source ↗

  49. “Okay, that's truth. Proof, on the other hand, is in this Hilbert way of thinking, we can develop proof theory. What is a proof for a mathematician, for a mathematical logician, a proof is a certain sequence or arrangement of sentences in the formal language that accord with the logical rules of a proof system. So the certain modes of reasoning that are allowed. So if you know A and you know A implies B in the proof, then at a later step you're allowed to write B as a consequence. So if you know A and you know A implies B, those are both two statements that are known, then you can deduce B as a consequence according to the rule of modus ponents. This is the rule modus ponents. And, you know, there's a lot of other rules. Some people would call this implication elimination, this different kinds of proof.”

    Lex Fridman Podcast31 December 2025Source ↗

  50. “And it allows you to define by induction the truth of any assertion in a formal language inside any mathematical structure. And so to And so maybe we have in mind the standard model of arithmetic or something with the natural numbers and the arithmetic structure. And I want to know, is a given statement true in that structure, then we have a formal definition of what that means according to the Tarski recursive definition of truth.”

    Lex Fridman Podcast31 December 2025Source ↗