Dr. Joel Hamkins on Lex Fridman: How Cantor broke math

1. 0:00 – 2:17

   Introduction

   1. LFLex Fridman0:00

      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, uh, 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, uh, a little bit of hate and a whole lot of love, and I wouldn't have it, uh, any other way. I'm grateful for all of it. This is the Lex Fridman Podcast. To support it, please check out our sponsors in the description where you can also find ways to contact me, ask questions, give feedback, and so on. And now, dear friends, here's Joel David Hamkins.

2. 2:17 – 49:27

   Infinity & paradoxes

   1. LFLex Fridman2:17

      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, and, uh, 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, and also Cantor was deeply religious himself. Second, there's a kinda mathematical civil war, the leading German mathematician, uh, Kronecker called Cantor a corrupter of youth and, uh, tried to block his career. Third, many fascinating paradoxes emerged from this, uh, like Russell's paradox about the set of all sets that don't contain themselves, and, uh, those threatened to make all of mathematics inconsistent. And finally, on the psychological side and the personal side, Cantor's own breakdown. He literally went mad spending his final years in and out of, uh, sanatoriums obsessed with proving the continuum hypothesis. So laying that all out on the table, uh, can you explain the idea of infinity that, uh, some infinities are larger than others and why was this so transformative to mathematics?

   2. JHJoel David Hamkins3:35

      Well, that's a really great question. I would wanna start talking about infinity and telling the story much earlier than Cantor actually because, I mean, you can go all the way back to ancient Greek times when Aristotle emphasized the potential aspect of infinity as opposed to the impossibility, according to him, of achieving an actual infinity, and Archimedes' method of exhaustion where he is trying to understand the, the area of a region by carving it into more and more triangles, say, and sort of exhausting the area and thereby understanding the total area in terms of the sum of the areas of the pieces that he put into it. And it proceeded on this kind of potential under- this potential as understanding of infinity for, for hundreds of years, thousands of years. Uh, almost all mathematicians were potentialists only and thought that it was incoherent to speak of an actual infinity at all. Um, Galileo is an extremely prominent exception to this, though he argued against this sort of potentialist orthodoxy in The Dialogue of Two New Sciences, really lovely account there that he gave, um, and that the- i- in many ways, Galileo was anticipating Cantor's developments except he couldn't quite push it all the way through and, uh, ended up throwing up his hands in confusion i- in a sense. I mean, the Galileo paradox is the idea or the observation that if you think about the natural numbers, I would start with zero but I think maybe he would start with one, the numbers one, two, three, four, and so on, and you think about which of those numbers are perfect squares. So zero squared is zero, and one squared is one, and two squared is four, three squared is nine, 16, 25, and so on. And Galileo observed that, that the perfect squares can be put into a one-to-one correspondence with all of the numbers. I mean, we just did it. I associated every number with its square. And so it seems like on the basis of this one-to-one correspondence that there should be exactly the same number of squares, perfect squares as there are numbers, and yet there's all the gaps in between the perfect squares, right? And, and this suggests that...... uh, you know, there should be fewer perfect squares, more numbers than squares because the numbers include all the squares plus a lot more in between them, right? And Galileo was quite troubled by this observation because he took it to cause a kind of incoherence in the comparison of infinite quantities, right? And another example is if you take two line segments of different lengths, and you can imagine drawing a kind of foliation, a fan of lines that connect them. So the endpoints are matched from the shorter to the longer segment, and the midpoints are matched and so on. So spreading out the lines as you go. And so every point on the shorter line would be associated with a- a unique distinct point on the longer line in a one-to-one way. And so it seems like the two line segments have the same number of points on them because of that, even though the longer one is longer. And so it makes, again, a kind of confusion of our ideas about infinity. And also with two circles, if you just place them concentrically and draw the rays from the center, then every point on the smaller circle is associated with a corresponding point on the larger circle, you know, in a one-to-one way. And- and again, that seems to show that the smaller circle has the same number of points on it as the larger one, precisely because they can be put into this one-to-one correspondence. Now, of course, the contemporary attitude about this situation is that those two infinities are- are exactly the same and that Galileo was right in those observations about the equinumerosity. And the way we would talk about it now is appeal to what, uh, what I call the Cantor Hume principle, or some people just call it Hume's principle, which is the idea that if you have two collections, whether they're finite or infinite, then we want to say that those two collections have the same size, they're equinumerous if and only if there's a one-to-one correspondence between those collections. And so Galileo was observing that line segments of different lengths are equinumerous and the perfect squares are equinumerous with the whole... All of the natural numbers, and- and two, any two circles are equinumerous and so on. And the- the tension between the Cantor Hume principle and what could be called Euclid's principle, which is that the whole is always greater than the part, which is a principle that Euclid appealed to in- in The Elements. I mean, many times when he's calculating area and so on, he wants... It- it's a kind of basic idea that if something is just a part of another thing, then the- the whole is greater than the part. And so what Galileo was troubled by was this tension between what we call the Cantor Hume principle and Euclid's principle. And it really wasn't fully resolved, I think, until Cantor, he's the one who really explained so clearly about these different sizes of infinity and so on in a way that was so compelling. And so he exhibited two different infinite sets and proved that they're not equinumerous. They can't be put into one-to-one correspondence. And it's traditional to talk about the uncountability of the real numbers. So Cantor's big result was that the set of all real numbers is an uncountable set. So maybe if we're gonna talk about countable sets, then I would suggest that we talk about Hilbert's Hotel, which really makes that idea perfectly clear.

   3. LFLex Fridman9:39

      Yeah, let's talk about the Hilbert's Hotel.

   4. JHJoel David Hamkins9:41

      Hilbert's Hotel is a hotel with infinitely many rooms. You know, each room is a full floor suite. So there's floor zero. I always start with zero because for me, the natural numbers start with zero, although that's maybe a point of contention for some mathematicians.

   5. LFLex Fridman9:56

      (laughs)

   6. JHJoel David Hamkins9:57

      The- the other mathematicians are wrong.

   7. LFLex Fridman9:58

      Well, like I mentioned to you, I'm a programmer, so starting at zero is a wonderful place to start.

   8. JHJoel David Hamkins10:01

      Exactly. So there's floor zero, floor one, floor two or room zero, one, two, three and so on, just like the natural numbers. So Hilbert's Hotel has a room for every natural number, and it's completely full. There's a person occupying room N for every N. But meanwhile, a new guest comes up to the desk and wants a room. "Can I have a room, please?" And the manager says, "Hang on a second, just give me a moment." And you see, when the other guests had checked in, they had to sign an agreement with, uh, with the hotel that maybe there would be some changing of the rooms, you know, during the stay. And so the manager sent a message up to all the current occupants and told every person, "Hey, can you move up one room, please?" So the person in room five would move to room six, and the person in room six would move to room seven and so on. And everyone moved at the same time. And of course, we never wanna be placing two different guests in the same room, and we wa- want everyone to have their own private room and... But when you move everyone up one room, then the bottom room, room zero becomes available, of course. And so he can put the new guest in that room. So even when you have infinitely many things, then the new guest can be accommodated, and that's a way of showing how the particular infinity of the occupants of Hilbert's Hotel, it violates Euclid's principle. I mean, it exactly illustrates this idea because adding one more element to a set didn't make it larger, because we can still have a one-to-one correspondence between the total new guests and the old guests by the room number, right?

   9. LFLex Fridman11:40

      So to just, uh, say one more time, the hotel is full.

   10. JHJoel David Hamkins11:45

       The hotel is full.

   11. LFLex Fridman11:46

       And then you could still squeeze in one more, and that breaks the, uh, traditional notion of mathematics and- and breaks people's brains about when they try to, uh, think about infinity, I suppose. This is a property of infinity.

   12. JHJoel David Hamkins11:59

       It's a property of infinity that sometimes when you add a- an element to a set, it doesn't get larger. That's what this example shows.... but one can go on with Hil- Hilbert's Hotel, for example. Uh, I mean maybe the next day, you know, 20 people show up all at once. We can easily do the same trick again, just move everybody up 20 rooms. And then we would have 20 empty rooms at the bottom, and those new 20 guests could go in. But on the following weekend, a giant bus pulled up, Hilbert's bus. And Hilbert's bus has, of course, infinitely many seats. There's seat zero, seat one, seat two, seat three, and so on. And so one wants to, uh... You know, all the people on the bus want to check into the hotel, but the hotel is completely full. And so what is the manager gonna do? And when I talk about Hilbert's Hotel in, when I teach Hilbert's Hotel in, in class, I always demand that the students provide, you know, the explanation of, of how to do it.

   13. LFLex Fridman13:00

       Mm-hmm.

   14. JHJoel David Hamkins13:00

       So maybe I'll ask you.

   15. LFLex Fridman13:02

       Mm-hmm.

   16. JHJoel David Hamkins13:02

       Can you tell me, yeah, what is your idea about how to fit them all in the hotel, everyone on the bus, and also the current occupants?

   17. LFLex Fridman13:08

       Uh, you, uh, you separate the hotel into even and odd rooms, and you squeeze in the new Hilbert bus people into the odd rooms and, uh, the previous occupants go into the even rooms.

   18. JHJoel David Hamkins13:20

       That's exactly right. So I mean, that's the, a very, uh, easy way to do it. If you just tell all the current guests to double their room number, so in room N you move to room 2 times N. So they're all gonna get their own private room, the new room, and it will always be an even number because 2 times N is always an even number. And so all the odd rooms become empty that way. And now we can u- put the bus occupants into the odd-numbered rooms.

   19. LFLex Fridman13:42

       And by doing so, you have now shoved an, an infinity into another infinity.

   20. JHJoel David Hamkins13:47

       That's right. So what it really shows... I mean, another way of thinking about it is that, well, we can define that a set is countable if it is equinumerous with a set of natural numbers. And, and a kind of easy way to understand what that's saying in terms of Hilbert's Hotel is that a set is countable if it fits into Hilbert's Hotel, 'cause Hilbert's Hotel basically is the set of natural numbers in terms of the room numbers. So to be equinumerous with a set of natural numbers is just the same thing as to fit into Hilbert's Hotel. And so what we've shown is that if you have two countably infinite sets, then their union is also countably infinite. If you put them together and form a new set with all of the elements of either of them, then that union set is still only countably infinite. It didn't get bigger. And that's a remarkable property for, uh, a, a notion of infinity to have, I suppose. But if you thought that there was only one kind of infinity, then it wouldn't be surprising at all, because if you take two infinite sets and put them together, then it's still infinite. And so if there were only one kind of infinity, then it shouldn't be surprising-

   21. LFLex Fridman14:53

       Mm-hmm.

   22. JHJoel David Hamkins14:53

       ... that the union of two countable sets is countable. So there's another way to push this a bit harder, and that is when, uh, when Hilbert's train arrives, and Hilbert's train has infinitely many train cars-

   23. LFLex Fridman15:08

       Mm-hmm.

   24. JHJoel David Hamkins15:08

       ... and each train car has infinitely many seats.

   25. LFLex Fridman15:12

       Mm-hmm.

   26. JHJoel David Hamkins15:13

       And so we have an infinity of infinities of the train passengers together with the current occupants of the hotel, and everybody on the train wants to check in to Hilbert's Hotel. So the manager can, again, of course, send a message up to all the rooms, uh, telling every person to double their room number again. And so that will occupy all the even-numbered rooms again and but free up again the odd-numbered rooms. So somehow we want to put the train passengers into the odd-numbered rooms. And so, well, every train passenger is on some car, let's say car C and seat S. So somehow we have to take these two coordinates, you know, C comma S, the car number and the seat number, and produce from it an odd number in a one-to-one way, you know? And that's, that's actually not very difficult. In fact, uh, one can just use, say, an easy way to do it is to just use the number 3 to the C times 5 to the S. 3 to the C, 3 to the car number, so 3 times 3 times 3, you know, the number of the car. You multiply 3 by itself, the number of the train car, and then you multiply 5 by itself the seat number times, and then you multiply those two numbers together. So 3 to the C times 5 to the S. That's always an odd number 'cause the prime factorization has only 3s and 5s in it. There's no 2 there. So therefore, it's definitely an odd number, and it's always different because of the uniqueness of prime factorization. So every number can be factored uniquely into primes. So if you have a number of that form, then you can just factor it, and that tells you the exponent on 3 and the exponent on 5. And so you know exactly which person it was, which car they came from and which seat they came from.

   27. LFLex Fridman17:10

       And prime factorization is every single number can be, uh, uh, decomposed into the atoms of mathematics, which is the prime numbers. You can multiply them together to ach- achieve that number.

   28. JHJoel David Hamkins17:22

       That's right.

   29. LFLex Fridman17:23

       And that's prime factorization. You're showing 3 and 5 are both prime numbers, odd. So through this magical formula, you can, uh, deal with this train, infinite number of cars, with each car having infinite number of seats.

   30. JHJoel David Hamkins17:41

       Exactly right. We've proved that if you have countably many countable sets, then the union of those sets, putting all those sets together into one giant set, is still countable, you know, 'cause the, the train cars are each countable, plus the current hotel is sort of like another train car, if you want to think about it that way. The current occupants of the hotel could, you know, have the s- same number as, as any of the train cars. So putting countably many countable sets together to make one big union set is still countable. It's quite remarkable, I think. I-... um, I mean, when I first learned this many, many years ago, I was completely shocked by it and transfixed by it. It was quite amazing to me that this notion of countable infinity could be closed under this process of infinitely many infinities adding up still to the very same infinity, which is a strong instance, a strong violation of Euclid's principle once again, right? So the new set that we built is... has many more elements than the old set in the sense that there's additional elements, but it doesn't have many more elements in terms of its size because it's still just a countable infinity, and it fits into Hilbert's Hotel.
3. 49:27 – 1:02:35

   Russell's paradox

   1. LFLex Fridman49:28

      You mentioned to me offline, uh, we were talking about Russell's paradox and that there's a, a nice another kind of anthropomorphizable proof of uncountability. Uh, I was wondering if you can lay that out.

   2. JHJoel David Hamkins49:41

      Oh yeah, sure. Absolutely.

   3. LFLex Fridman49:42

      Both Russell's paradox and the proof.

   4. JHJoel David Hamkins49:44

      Right. So let's, so we, we talked about Cantor's proof that the real numbers, the set of real numbers is an uncountable infinity, it's a strictly larger infinity than the natural numbers. But Cantor actually proved a, a much more general fact, namely that for any set whatsoever, the power set of that set is a strictly larger set. So the power set is the set containing all the subsets of the original set. So if you have a set and you look at the collection of all of its subsets, then Cantor proved that this is, this is a bigger set. They're not equinumerous. Of course, there's always at least as many subsets as elements because for any element you can make, the, the singleton subset that has only that guy as a member, right? So there's always at least as many subsets as elements. But the question is whether they, whether it's strictly more or not. And so Cantor reasoned like this. It's very simple. So kind of distilling the abstract diagonalization idea without encumbered by the complexity of the real numbers. So we have a set X and we're looking at all of its subsets. That's the power set of X. Suppose that X and the power set of X have the same size. Suppose to its contradiction they have the same size. So that means we can associate to every individual of X a subset. And so now let me define a new set. I mean, another set. I'm gonna define it. Let's call it D. And D is the subset of X that contains all the individuals that are not in their set. Every individual was associated with a subset of X, and I'm looking at the individuals that are not in tha- their set. Maybe nobody's like that. Maybe there's no element of X that's like that, or maybe they're all like that, or maybe some of them are and some of them aren't. I don't, it doesn't really matter for the argument. I defined a subset D consisting of the individuals that are not in the set that's attached to them. But that's a perfectly good subset. And so because of the equinumerosity, it would have to be attached to a, to a particular individual, you know. And-

   5. LFLex Fridman52:02

      Mm-hmm.

   6. JHJoel David Hamkins52:03

      ... but that, let, let's call that person, uh, it should be a name starting with D, so Diana.

   7. LFLex Fridman52:09

      Mm-hmm.

   8. JHJoel David Hamkins52:10

      And now we ask, is Diana an element of D or not? But if Diana is an element of D, then she is in her set. So she shouldn't be because the set D was the, the set of individuals that are not in their set.

   9. LFLex Fridman52:26

      Mm-hmm.

   10. JHJoel David Hamkins52:28

       So if Diana is in D, then she shouldn't be. But if she isn't in D, then she wouldn't be in her set. And so she should be in D.

   11. LFLex Fridman52:35

       Mm-hmm.

   12. JHJoel David Hamkins52:35

       That, that's a contradiction. So therefore, the number of subsets is always greater than the number of elements for any set. And the anthropomorphizing idea is the following. I like to talk about it this way. Uh, for any collection of people, you can, you can form more committees from them than there are people, even if you have infinitely many people.

   13. LFLex Fridman53:01

       Mm-hmm.

   14. JHJoel David Hamkins53:03

       Suppose you have an infinite set of people, and what's a committee? Well, a committee is just a list of who's on the committee basically, the members of the committee. So there's, there's all the two-person committees and there's all the one-person committees and there's the universal, the worst committee, the one that everyone is on. Okay, the best committee is the empty committee-

   15. LFLex Fridman53:23

       Yeah.

   16. JHJoel David Hamkins53:23

       ... with no members and never meets and so on, yeah. Or is the empty committee meeting all the time? I'm not sure. (laughs)

   17. LFLex Fridman53:29

       Yeah. That's, wow, that's a profound question.

   18. JHJoel David Hamkins53:31

       Yeah.

   19. LFLex Fridman53:32

       And does a, a committee with just one member meet also as a-

   20. JHJoel David Hamkins53:35

       Yeah. Maybe it's always in session. I don't know.

   21. LFLex Fridman53:37

       Yeah.

   22. JHJoel David Hamkins53:38

       So th- so the, the, the claim is that there's more committees than people.

   23. LFLex Fridman53:44

       Mm-hmm.

   24. JHJoel David Hamkins53:44

       Okay. Suppose not. Well, then we could make an association between the people and the committees. So we would have a kind of... Every committee could be named after a person in a one-to-one way. And I'm not saying that the person is on the committee that's named after them or not on it, whatever. Maybe sometimes that happens, sometimes it doesn't. I don't know. It doesn't matter. But let's form what I call committee D, which consists of all the people that are not on the committee that's named after them.

   25. LFLex Fridman54:14

       Mm-hmm.

   26. JHJoel David Hamkins54:16

       Okay? Maybe that's everyone. Maybe it's no one, maybe it's half the people. It doesn't matter. That's a committee. It's a set of people. And so it has to be named after someone. Let's call that person Daniella. So now we ask, is Daniella on the committee that's named after her? Well, if she is, then she shouldn't be because it was the committee of people who aren't on their, on their own committee. Uh, and if she isn't, then she should be. So again, it's a contradiction. So when I was teaching at Oxford, one of my students, uh, came up with the following different anthropomorphization of Cantor's argument. Let's consider all possible fruit salads. We have a given collection of fruits-

   27. LFLex Fridman55:06

       Mm-hmm.

   28. JHJoel David Hamkins55:07

       ... you know, apples and oranges and grapes, whatever. And a fruit salad consists of, uh, some collection of those fruits. So there's the banana, pear, grape salad and so on. There's a lot of different kinds of salad. Every set of fruits makes a salad, a fruit salad. Okay? And we want to prove that for any collection of fruits, even if there are infinitely many different kinds of fruit-... for any collection of fruits, there are more possible fruit salads than there are fruits. So if not, then you can put a one-to-one correspondence between the fruits and the fruit salads. So you could name every fruit salad after a fruit. Might not be, that fruit might not be in that salad, it doesn't matter. We're just, it's a naming, a one-to-one correspondence. And then, of course, we form the diagonal salad, which consists-

   29. LFLex Fridman55:58

       Uh-huh.

   30. JHJoel David Hamkins55:59

       ... of all the fruits that are not in the salad that's named after them.
4. 1:02:35 – 1:20:06

   Gödel's incompleteness theorems

   1. LFLex Fridman1:02:35

      I think this is a good moment to talk about, uh, Godel's, uh, incompleteness theorems. So can you explain them and, uh, what do they teach us about, uh, the nature of mathematical truth?

   2. JHJoel David Hamkins1:02:47

      Absolutely. It's one of the most profound developments in mathematical logic. I mean, the incompleteness theorems is 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, and Hilbert was famously supportive of set theory. I mean, there's this quote of him, um, saying, "No one shall cast us from the paradise that Cantor has created for us." And what I take him to mean by that is he was so captured by the idea of using set theory as a foundation of mathematics and it was so powerful and convenient and unifying in a way that was extremely important. And he wasn't, he didn't want to give that up, despite the danger of these paradoxes, these contradictions basically is how some people viewed them. And so-

   3. LFLex Fridman1:03:58

      This minefield of paradoxes. Yeah.

   4. JHJoel David Hamkins1:04:00

      Right. A minefield. That's a really good way of describing the situation. And so Hilbert said, "Well, look, we have to fix this problem." You know, we wanna use the set theory foundations, but we want to do it in a way that is trustworthy and reliable. We can't allow that the foundations of mathematics are in question, you know. This is a kind of attitude I think that underlies Hilbert and the Hilbert program. And so he proposed, "Look, we're gonna have this strong theory, this set theory that we wanna be proving our theorems in." Um, but, uh, I mean, on the one hand, we, we want it to be as strong as possible. We would like it to answer all the questions. The- there's another famous quote of Hilbert in his retirement address where, um, he proclaims, uh, "Wir müssen wissen, wir werden wissen." So, "We, we must know, we, we will know," in which he's very optimistic about the ability of mathematics to answer all of the questions of mathematics that we have posed. We have all these problems we wanna solve, and he is saying, "We're gonna do it. We're gonna solve all these problems." So we want to propose this strong theory, and one has the sense that he had in mind set theory, um, in which all the questions are gonna be answered. Okay? But secondly, we want to combine that with, in a very weak arithmetic, purely finitistic theory, we wanna prove that the reasoning process of the strong theory is safe. Okay? So in order to make sense of that point of view, you, you basically have to invent the philosophy of formalism, uh, where we can look at what is the proof, what is the nature of mathematical reasoning? And on Hilbert's way of thinking about this, uh, a proof is basically a- itself a finitistic kind of object. It's a sequence of, if you think about the nature of what a proof is, it's, it's a sequence of assertions which can be viewed as sort of sequences of symbols that conform with certain rules of logical reasoning. And, and this is a, a formalist way of understanding the nature of proof. So we think about a proof in a kind of syntactic, formal way. Even though the contents of those statements might be referring to infinite uncountable objects, the statements themselves are not infinite uncountable objects. The statements themselves are just finite sequences of symbols.

   5. LFLex Fridman1:06:33

      So we kind of think of proof as, um, maybe it's fair to say almost like a outside of math. It's like tools operating on math. And then for Hilbert, he thought proof is inside the axiomatic system. Something like this.

   6. JHJoel David Hamkins1:06:45

      Yeah. That's helpful.

   7. LFLex Fridman1:06:46

      That's wild. (laughs)

   8. JHJoel David Hamkins1:06:48

      The main thing about formalism is that you, you think of the process of doing mathematics. You divorce it from the meaning of the mathematical assertions, right? So the meaning of the mathematical assertions that you make in this infinitary theory has to do with these huge uncountable infinities and so on possibly. And, and, and, and that's, uh, a very sort of uncertain realm maybe and the source of the paradoxes and so on in some people's minds. And so, um, but the reasoning process itself is consists of writing down sequences of symbols on your, on your page and, you know, undertaking a, uh, an argument with them, which is following these finitary rules. And so, so, so if we divorce the meaning of the symbols from just the process of manipulating the symbols, it's a way of looking at the nature of mathematics as a kind of formal game in which the meaning may be totally absent.... I don't think it's necessarily part of the formalist view that there is no meaning behind, but rather it's emphasizing that we can divorce the meaning of the sentences from the process of manipulating those sentences.

   9. LFLex Fridman1:07:58

      Mm-hmm.

   10. JHJoel David Hamkins1:07:59

       And then Hilbert wanted to prove in this purely finitary theory that if we follow the rules of that game, we're never gonna get a contradiction.

   11. LFLex Fridman1:08:09

       Mm-hmm.

   12. JHJoel David Hamkins1:08:09

       So those were the two aims of the Hilbert program, is to found the strong infinitary theory, probably set theory, which is gonna answer all the questions and then secondly prove in the finitary theory that the strong theory is safe. In other words, consistent, you know.

   13. LFLex Fridman1:08:31

       What does the word "finitary" in finitary theory mean?

   14. JHJoel David Hamkins1:08:34

       Yeah. Well, this is of course philosophically contentious, and people have different ideas about what exactly it should mean. And so there's hundreds of papers (laughs) about exactly that, uh, question. But I- I like to take it just kind of informally. I mean, it means that we're talking about finite sequences of symbols and we're gonna have a f- a, a theory, you know, finite strings of symbols and we... A finitary theory would be one whose subject matter is about those kinds of things so that we can conceivably argue about the nature of these finite strings. So a, a proof is just a finite sequence of statements, so that every statement is either one of the axioms or follows by the laws of logic from the earlier statements in some specified manner, like using modus ponens or some other law of logic like that. Um, and such that the last line on the list is, you know, the theorem that you're proving. So that's what a proof is in this kind of way of thinking.

   15. LFLex Fridman1:09:29

       Mm-hmm.

   16. JHJoel David Hamkins1:09:29

       To take a specific example, I mean, I always conceive of the, perhaps the most natural finitary theory that one would be called upon to exhibit would be Peano arithmetic, the theory of Peano arithmetic, which, which is a first order theory of the nature of arithmetic. Um, but okay, so some people say, "Well, Peano arithmetic has these strong first order induction axioms and there's much, much weaker versions of arithmetic like I-sigma-naught or I-sigma-1 and so on which are, um, even more finitary than Peano arithmetic." So different philosophical positions take different attitudes about what is, what does it take to be finitary? How finitary do you have to be to be truly finitary?

   17. LFLex Fridman1:10:10

       So going to Perplexity, "Peano arithmetic is a foundational system for formalizing the properties and operations of natural numbers using a set of axioms called the Peano axioms. Peano arithmetic provides a formal language and axioms for arithmetic operations such as addition and multiplication over the natural numbers. The axioms define the existence of a first natural number, usually zero or one, the concept of successor function which generates the next natural number, rules for addition and multiplication built from these concepts, the principle of induction allowing proofs around all natural numbers." And it goes on. So it's a, a very particular kind of arithmetic that is finitary.

   18. JHJoel David Hamkins1:10:51

       You, in my, I view it as finitary, but there's a contentious view. I mean, not everyone agrees with that. That's what I was tr- trying to hint at.

   19. LFLex Fridman1:10:58

       Okay. I got it. (laughs) All right.

   20. JHJoel David Hamkins1:10:58

       Um, Peano arithmetic is one of the hugely res- hugely successful theories of the natural numbers and, and elementary number theory. Essentially, all of classical number theory, so what- whatever kind of theorems you want to be proving about the prime numbers or factorization or, uh, any kind of finitary reasoning about finite common

   21. LFLex Fridman1:11:19

       Mm-hmm.

   22. JHJoel David Hamkins1:11:19

       ... tutorial objects, all of it can be formalized in Peano arithmetic. I mean, that's the, the basic situation. Of course, one has to qualify those statements in light of the Godel incompleteness theorem. But, uh, for the most part, the classical, um, number theoretic analysis of the, of the finite numbers is, uh, almost entirely developable inside Peano arithmetic. So if we, if we go back to the Hilbert program, so Hilbert has these two goals, produce the strong theory which is gonna answer all the questions and then prove by purely finitary means that that theory will never lead into contradiction. And one can think about, well, the incompleteness theorem should be viewed as a decisive refutation of the Hilbert program. It-

   23. LFLex Fridman1:12:08

       Mm-hmm.

   24. JHJoel David Hamkins1:12:08

       ... it defeats both of those goals decisively, completely. But, but before explaining that, maybe one should think about, you know, what if Hilbert had been right? What would be the nature of mathematics in the world that Hilbert is telling us to search for?

   25. LFLex Fridman1:12:24

       And if I may go into, uh, Perplexity definition of Hilbert's program, "It was David Hilbert's early 20th century project to give all of classical mathematics a completely secure finitary foundation. In essence, the goal was to formalize all of mathematics in precise axiomatic systems and then prove, using only very elementary finitary reasoning about symbols, that these systems are free of contradiction."

   26. JHJoel David Hamkins1:12:51

       Right. Exactly right. Let's imagine what it would be like if he were, if he were- had been right. So we would have this finitary theory and it would prove that the strong theory was free of contradiction. So we could start enumerating proofs from the strong theory. We can... I mean, right now we can write a computer program that would systematically generate all possible proofs from a given theory. And so we could have, like, this theorem enumeration machine that just spit out theorems all day long in such a manner that every single theorem would eventually be produced by this device. And so if you had a mathematical question of any kind, you could answer it by just waiting for either the answer to come out yes-... from the machine or the answer to come out no. So the, the nature of mathematical investigation in Hilbert's world is one of just turning the crank of a theorem or enu- enumeration machine devoid of creative thinking or imagination. It's just getting the answer from the, from this by rote procedure. So, so Hilbert, in effect, is telling us, I mean, in, with this program, that the, the fundamental nature of mathematics is rote computation. I mean, the way I think about the Hilbert program seems extremely attractive in the historical context of being worried about the antinomies, the, the inconsistencies, and so how can we kind of block them. And so-

   27. LFLex Fridman1:14:31

       Mm-hmm.

   28. JHJoel David Hamkins1:14:31

       ... it seems natural, first of all, to have a strong theory that's gonna answer all the questions because the idea of logical independence and pervasiveness that we now know exists, um, just wasn't, uh, you know, there was no known, they didn't know anything like that happening ever. And so, um, it's natural to think that it wouldn't happen and also that they would be able to guard against this inconsistency. So it seems like the goals of the Hilbert program are quite natural in that historical context, but, you know, when you think a little more about what the nature of what it would be like, it shows you this kind of rote procedure, and now you're saying, "Well, that doesn't seem so unlikely." Maybe, I mean, in the light of the increasing computer power and so on, it's actually maybe turning into our everyday experience where the machines are calculating more and more for us and, um, in a way that, uh, could be alarming. Okay. But, okay, so to talk about the alternative to the Hilbert point of view, I mean, if he's wrong, then what is the nature of mathematical reality? Well, it would mean that we couldn't ever maybe, for the first goal, we couldn't ever write down a theory that answered all the questions. So we would always be in a situation where our best theory, even the infinitary theories, uh, would have questions that they stumble with and are unable to answer. Independence, uh, would occur. But then also, because of the failure of the second goal, we would also have to be constantly worrying about whether our theories were consistent or not, and we wouldn't have any truly convincing means of saying that they were free from contradiction. And the fact of Godel i- of Godel's Incompleteness Theorem shows that that is exactly the nature of mathematical reality actually. Those are the two incompleteness theorems. So the first incompleteness theorem says you cannot write down a computably axiomatizable theory that answers all the questions. Every such theory will be incomplete, assuming it, uh, includes a certain amount of arithmetic. And secondly, no such theory can ever prove its own consistency. So not only is it the case that the finitary theory can't prove the consistency of the strong infinitary theory, but even the infinitary theory can't prove its own consistency, right? That's the second incompleteness theorem. And so it's, in that sense, a decisive take-down of the Hilbert program, um, which is really quite remarkable the extent to which his theorem just really answered that whole puzzle. Um, it's quite amazing. I mean, there's another aspect, kind of easy to think about. I mean, if you're th- if you're wondering about theories that prove their own consistency, then, I mean, would you trust a theory that proves of itself that it's consistent? I mean, that's like, it's like the used car salesman telling you, "Oh, I'm trustworthy."

   29. LFLex Fridman1:17:39

       (laughs)

   30. JHJoel David Hamkins1:17:39

       I mean, it's not a reason to trust the used car salesman, is it? Just because he says that. So similarly, if you have a theory that proves its own consistency, well, I mean, even an inconsistent theory would prove its own consistency, and so it doesn't seem to be a logical reason to believe in the consistency if you have a theory that proves itself consistent.
5. 1:20:06 – 1:31:30

   Truth vs proof

   1. JHJoel David Hamkins1:20:06

   2. LFLex Fridman1:20:06

      So can we just linger on, uh, Godel's incompleteness theorem?

   3. JHJoel David Hamkins1:20:09

      Sure.

   4. LFLex Fridman1:20:09

      You mentioned the two components there. You know, there's so many questions to ask, like what- what is the difference between provability and, uh, truth? What is true and what is provable? Maybe that's a good line to draw.

   5. JHJoel David Hamkins1:20:21

      Yeah, this is a really core distinction that it's fascinating to me to go back and read th- even the early 20th century people before Godel and Tarski, and they were totally sloppy about this distinction-

   6. LFLex Fridman1:20:41

      (laughs)

   7. JHJoel David Hamkins1:20:41

      ... between truth and proof. It wasn't clear at all until Godel basically... Although even as late as Bourbaki has a kind of confusion in these foundational works, so this standard graduate level textbooks used in France in the presentation of logic, they are conflating truth and proof, to be true for them means to be provable. So in the early days, maybe it wasn't clear enough that the concept of truth needed a mathematical investigation or analysis, maybe it was already taken to be fully clear. But because of the incompleteness theorem, we realized that actually there's quite subtle things happening, right? And so why don't we talk about this distinction a bit? To me, it's absolutely core and fundamental to our understanding of mathematical logic now-

   8. LFLex Fridman1:21:33

      Mm-hmm.

   9. JHJoel David Hamkins1:21:34

      ... this distinction between truth and proof. So truth is on the semantic side of the syntax semantics dichotomy. Truth has to do with the nature of- of reality. I mean, okay, when I talk about reality, I'm not talking about physical reality, I'm talking about mathematical reality. So- so we have a concept of something being true in a structure, a statement being true in a mathematical structure, like maybe you have the real field or something and you wanna know does it satisfy this statement or that statement? Or you have a group of some kind, or maybe you have a graph, this is a particular kind of mathematical structure that has a bunch of vertices and edges and you want to know, um, you know, does- does this graph satisfy that statement? And Tarski gave this absolutely wonderful account of the nature of truth in what's now known as the disquotational theory of truth. And what Tarski says is the sentence, quote, "Snow is white," unquote, is true if and only if snow is white. And what he means by that is... Look, to say truth is a property of an assertion, so we can think of the assertion as a- syntactically. So th- this- the sentence is true if and only if the content of the sentence is the case, you know? So the sentence, "Snow is white," you know, in quotations, uh, is true, that just means that snow is white, and that- that's why it's called the disquotational theory because we- we remove the quotation marks-

   10. LFLex Fridman1:23:15

       Mm-hmm.

   11. JHJoel David Hamkins1:23:16

       ... from the assertion, right? And- and you can use this idea of disquotation to give a formal definition of truth in a mathematical structure of a statement in a formal language. So for example, if I have a formal language that allows me to make atomic statements about the objects and relations of the structure, and I can build up a formal language with, you know, with- with the logical connectives of "And" and "Or" and "Implies" and "Not" and so on, and maybe I have quantifiers, right? Then- for example, to say that the structure satisfies phi-and-psi, th- that single statement, phi-and-psi, I'm thinking of that as one statement, just means that it satisfies phi and it satisfies psi. And if you notice what happened there, I- at first the "And" was part of the sentence inside the sentence, but then in the second part, I was using the word "And" to refer to the conjunction of the two conditions. So-

   12. LFLex Fridman1:24:17

       Yeah, it has the disquotation.

   13. JHJoel David Hamkins1:24:18

       Yeah, it has the disquotation.

   14. LFLex Fridman1:24:20

       Yeah.

   15. JHJoel David Hamkins1:24:20

       And so this idea can be done for all the logical connectors and quantifiers and everything. You're- you're applying Tarski's idea of disquotation, and it allows you to define by induction the- the truth of any assertion in a formal language inside any mathematical structure. And so to say that a sentence is true, first of all it's ambiguous unless you tell me which structure you're talking about it being true in, um, 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- then we have a- a formal definition of what that means according to the Tarski recursive definition of truth. Okay, that's truth. Proof on the other hand, is, you know, 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- or arrangement of sentences in the formal language that accord with the logical rules of a proof system, so there's 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, um, uh, 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 ponens. This is the rule of modus ponens.And, you know, there's a lot of other rules. Some people would call this, uh, implication elimination. There's different kinds of proof 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. That proof- proofs preserve truth. They're truth preserving arguments. Okay? But also, um, the proof systems are also generally complete. They're both sound and complete, and complete means, um, that whenever a statement is a consequence, a logical consequence of some other statements, which means that whenever the assumptions are true, then the, then the consequence is also true in, in the structure. So whenever you have a logical consequence, then there is a proof of it. Okay? And the proof systems generally have both of those properties, they're sound and complete. There's a third property a lot of logicians talk about sound and complete, sound and complete this, sound and complete that, but actually there's a hidden third adjective that they should always be talking about in any such case, which is that, um, you should be able to recognize whether or not something is a proof or not. So there's a computable aspect, uh, to, to the proof systems. We want to be able to recognize whether something is a proof, it should be computably decidable whether a given sequence of statements is a proof or not. So we, we don't want a proof system in which someone claims to have a proof, but we can't check that fact that whether it's a proof or not.

   16. LFLex Fridman1:27:38

       Mm-hmm.

   17. JHJoel David Hamkins1:27:39

       We want to be able to, you know, to correctly adjudicate all claims to having a proof.

   18. LFLex Fridman1:27:46

       Yeah. Mathematician comes to mind that said he has a proof, but the margins are too small to contain it. (laughs)

   19. JHJoel David Hamkins1:27:52

       (laughs) Yeah, exactly. So-

   20. LFLex Fridman1:27:53

       So that doesn't count as proof.

   21. JHJoel David Hamkins1:27:55

       So generally, all the classical proof systems that are used are sound and complete and also computably decidable in the sense that we can decide whether something is a proof or not.

   22. LFLex Fridman1:28:04

       So what is, again, the tension between truth and proof? Which is more powerful and how do the two interplay with the contradictions that we've been discussing?

Episode duration: 3:52:17