Infinity, Paradoxes, Gödel Incompleteness & the Mathematical Multiverse | Lex Fridman Podcast #488

- 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. 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. 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 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 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. 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 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? - Well, that's a really great question. I would want to 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 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 understanding of infinity for hundreds of years, thousands of years. Almost all mathematicians were almost all mathematicians were potentialists only and thought that it was incoherent to speak of an actual infinity at all. 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. And that the... In many ways, Galileo was anticipating Cantor's developments, except he couldn't quite push it all the way through and ended up throwing up his hands in confusion 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 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 over 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 precisely because they can be put into this one-to-one correspondence. Of course, the contemporary attitude about this situation is that those two infinities are exactly the same, and that Galileo was right in those observations about the equinumerosity. We would talk about it now by appealing to 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. Galileo was observing that line segments of different lengths are equinumerous, and the perfect squares are equinumerous with all of the natural numbers, and any two circles are equinumerous, and so on. 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, is a principle that Euclid appealed to in the Elements many times when he's calculating area and so on. It's a basic idea that if something is just a part of another thing, then the whole is greater than the part. So what Galileo was troubled by was this tension between what we call the Cantor-Hume principle and Euclid's principle. It 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. He exhibited two different infinite sets and proved that they're not equinumerous; they can't be put into one-to-one correspondence. It's traditional to talk about the uncountability of the real numbers. Cantor's big result was that the set of all real numbers is an uncountable set. Maybe if we're going to talk about countable sets, then I would suggest that we talk about Hilbert's Hotel, which really makes that idea perfectly clear. - Yeah, let's talk about Hilbert's Hotel. - Hilbert's Hotel is a hotel with infinitely many rooms. 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. The other mathematicians are wrong. - Like I mentioned, I'm a programmer, so starting at zero is a wonderful place to start. - 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?" The manager says, "Hang on a second, just give me a moment." You see, when the other guests had checked in, they had to sign an agreement with the hotel that maybe there would be some changing of the rooms during this stay. 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 want to be placing two different guests in the same room, and we 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? - So, to just say one more time, the hotel is full. - The hotel is full. - And then you could still squeeze in one more, and that breaks the traditional notion of mathematics and breaks people's brains when they try to think about infinity, I suppose. This is a property of infinity. - It's a property of infinity that sometimes when you add an element to a set, it doesn't get larger. That's what this example shows. But one can go on with Hilbert's Hotel, for example. 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... You know, all the people on the bus want to check into the hotel, but the hotel is completely full. So what is the manager going to do? And when I talk about Hilbert's Hotel, when I teach Hilbert's Hotel in class, I always demand that the students provide, you know, the explanation of- of how to do it. So maybe I'll ask you. 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? - You separate the hotel into even and odd rooms, and you squeeze in the new Hilbert bus people into the odd rooms and the previous occupants go into the even rooms. - That's exactly right. That's a very 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 going to get their own private room, the new room, and it will always be an even number 'cause 2 times N is always an even number. And so all the odd rooms become empty that way. And now we can put the bus occupants into the odd-numbered rooms. - And by doing so, you have now shoved an infinity into another infinity. - 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 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 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... that the union of two countable sets is countable. So there's another way to push this a bit harder, and that is when Hilbert's train arrives, and Hilbert's train has infinitely many train cars... ...and each train car has infinitely many seats. 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 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 while 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, 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 actually not very difficult. In fact, 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 x 3 x 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 of 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. - And prime factorization is every single number can be decomposed into the atoms of mathematics, which is the prime numbers. You can multiply them together to achieve that number. And that's prime factorization. You're showing 3 and 5 are both prime numbers, odd. So through this magical formula, you can deal with this train, infinite number of cars, with each car having infinite number of seats. - 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, because the train cars are each countable, plus the current hotel. It's 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 same number 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 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 are 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. - Have you been able to sort of internalize a good intuition about countable infinity? Because that is a pretty weird thing. You can have a countably infinite set of countably infinite sets, and you can shove it all in and it still is a countable infinite set. - Yeah, that's exactly right. I mean, I guess, of course, when you work with these notions, the argument of of Hilbert's Hotel becomes kind of clear. There are many other ways to talk about it too. For example, let's think about, say, the integer lattice, the grid of points that you get by taking pairs of natural numbers, say, so the upper right quadrant of the integer lattice, yeah? So there's the, you know, row zero, row one, row two and so on, column zero, column one, column two and so on, and each row and column has a countable infinity of points on it, right? So those dots, if you think about them as dots, are really the same as the train cars if you think about each column of... in that integer lattice, it's a countable infinity. It's like one train car and then there's the next train car next to it, and then the next column next to that, the next train car. And so, but if we think about it in this grid manner, then I can imagine a kind of winding path winding through these grid points, like up and down the diagonals. Winding back and forth. So I start at the corner point and then I go down, up and to the left, and then down and to the right, up and to the left, down and to the right, and so on, in such a way that I'm going to hit every grid point on this path. So, this gives me a way of assigning room numbers to the points. Because every grid point is going to be the Nth point on that path for some N. And that that gives a correspondence between the grid points and the natural numbers themselves. So it's a kind of different picture. Before, we used this 3 to the C, 5 times 5 to the S, which is a kind of, you know, overly arithmetic way to think about it. But there's a kind of direct way to understand that it's still a countable infinity when you have countably many countable sets, because you can just start putting them on this list. And as long as you give each of the infinite collections a chance to add one more person to the list, then you're going to accommodate everyone in any of the sets in one list. - Yeah, it's a really nice visual way to think about it. You just zigzag your way across the grid to make sure everybody's included. That gives you an algorithm for including everybody. So, can you speak to the uncountable infinities? - Yeah, absolutely. - What are the integers and the real numbers- - Correct - and what is the line that Cantor was able to find? - Maybe there's one more step I want to insert before doing that. Which is the rational numbers. So we did pairs of natural numbers. Right? That's the train car, basically. But maybe it's a little bit informative to think about the rational, the fractions, the set of fractions, or rational numbers, because a lot of people maybe have an expectation that maybe this is a bigger infinity because the rational numbers are densely ordered. Between any two fractions, you can find another fraction, right? The average of two fractions is another fraction. And so, sometimes people, it seems to be a different character than the integers, which are discretely ordered, right? From any integer, there's a next one and a previous one, and so on. But that's not true in the rational numbers. And yet, the rational numbers are also still only a countable infinity. And the way to see that is actually it's just exactly the same as Hilbert's train again, because every fraction consists of two integers: the numerator and the denominator. And so if I tell you two natural numbers, then you know what fraction I'm talking about. I mean, plus the sign issue, I mean if it's positive or negative. But if you just think about the positive fractions, then, you know, you have the numbers of the form P over Q, where Q is not zero. So you can still do 3 to the P times 5 to the Q. The same idea works. with the rational numbers. So this is still a countable set. And you might think, "Well, every set is going to be countable because there's only one infinity." I mean, if that's a kind of perspective maybe that you're adopting, but it's not true, and that's the profound achievement that Cantor made is proving that the set of real numbers is not a countable infinity. It's a strictly larger infinity, and therefore there's more than one concept of infinity, more than one size of infinity. - So let's talk about the real numbers. What are the real numbers? Why do they break infinity? The countable infinity. Looking it up on Perplexity, real numbers include all the numbers that can be represented on the number line, encompassing both rational and irrational numbers. We've spoken about the rational numbers, and the rational numbers, by the way, are by definition, the numbers that can be represented as a fraction of two integers. - That's right. So with the real numbers, we have the algebraic numbers. We have, of course, all the rational numbers. The integers and the rationals are all part of the real number system. But then also, we have the algebraic numbers like the square root of 2 or the cube root of 5 and so on. Numbers that solve an algebraic equation over the integers, those are known as algebraic numbers. It was an open question for a long time whether that was all of the real numbers or whether there would exist numbers that are the transcendental numbers. The transcendental numbers are real numbers that are not algebraic. - And we won't even go to the surreal numbers about which you have a wonderful blog post. We'll talk about that a little bit later. - Oh, great. So it was Liouville who first proved that there are transcendental numbers, and he exhibited a very specific number that's now known as the Liouville constant, which is a transcendental number. Cantor also famously proved that there are many, many transcendental numbers. In fact, it follows from his argument on the uncountability of the real numbers that there are uncountably many transcendental numbers. So most real numbers are transcendental. - And again, going to Perplexity, "Transcendental numbers are 'real' or 'complex' numbers; they are not the root of any nonzero polynomial with integer or rational coefficients. This means they cannot be expressed as solutions to algebraic equations with integer coefficients, setting them apart from algebraic numbers." - So some of the famous transcendental numbers would include the number pi, you know, the 3.14159265 and so on. So that's a transcendental number. Also, Euler's constant, the e, like e to the x, the exponential function. - So you could say that some of the sexiest numbers in mathematics are all transcendental numbers? - Absolutely. That's true. Yeah, yeah. Although, you know, I don't know, square root of two is pretty - Square root. All right. So it depends. Let's not... Beauty can be found in in all the different kinds of sets, but yeah. - That's right. And if you have a kind of simplicity attitude, then zero and one are looking pretty good too, so... And they're definitely not - Sorry to take that tangent, but what is your favorite number? Do you have one? - Oh, gosh. You know- - Is it zero? - Did you know there's a proof that every number is interesting? You can prove it, because... - Yeah? What's that proof look like? - Yeah, okay. - How do you even begin? - I'm gonna prove to you- - Okay - ...that every natural number is interesting. - Okay. - Yeah. I mean, zero's interesting because it's the additive identity, right? That's pretty interesting. And one is the multiplicative identity, so when you multiply it by any other number, you just get that number back, right? And two is, you know, the first prime number. That's super interesting, right? And- Okay. So one can go on this way and give specific reasons, but I wanna prove as a general principle that every number is interesting. And this is the proof. Suppose, toward contradiction, that there were some boring numbers. Okay? - Oh, okay. - But if there was an uninteresting number- - Yes - ...then there would have to be a smallest uninteresting number. - Mm-hmm. Yes. - But that's a contradiction, because the smallest uninteresting number is a super interesting property to have. So therefore- - Ah, that's good. - ...there cannot be any boring numbers. - I'm gonna have to try to find a hole in that proof- because there's a lot of baked in in the word interesting, but yeah, that's a beautiful. - Right. - That doesn't say anything about the transcendental numbers, about the real numbers that you just proved from just- - That's right - ...four natural numbers. - Yeah. Okay, should we get back to Cantor's argument, or- - Sure. You've masterfully avoided the question. Well, you basically said, "I love all numbers." - Yeah, basically. - Is that what you said? - Yeah. That was my intention. - Back to Cantor's argument. Let's go. - Okay, so Cantor wants to prove that the infinity of the real numbers is different and strictly larger than the infinity of the natural numbers. So the natural numbers are the numbers that start with zero and add one successively, so zero, one, two, three, and so on. And the real numbers, as we said, are the numbers that come from the number line, including all the integers and the rationals and the algebraic numbers and the transcendental numbers and all of those numbers altogether. Now, obviously, since the natural numbers are included in the real numbers, we know that the real numbers are at least as large as the natural numbers. And so the claim that we want to prove is that it's strictly larger. So suppose that it wasn't strictly larger. So then they would have the same size. But to have the same size, remember, means by definition that there's a one-to-one correspondence between them. So we suppose that the real numbers can be put into one-to-one correspondence with the natural numbers. So therefore, for every natural number N, we have a real number, let's call it R sub N. R sub N is the Nth real number on the list. Basically, our assumption allows us to think of the real numbers as having been placed on a list, R1, R2, and so on. Okay, and now I'm going to define the number Z, and it's going to be... The integer part is going to be a zero, and then I'm going to put a decimal place, and then I'm going to start specifying the digits of this number Z. D1, D2, D3, and so on. And what I'm going to make sure is that the Nth digit after the decimal point of Z is different from the Nth digit of the Nth number on the list. Okay? So, to specify the Nth digit of Z, I go to the Nth number on the list, R sub N, and I look at its Nth digit after the decimal point. And whatever that digit is, I make sure that my digit is different from it. Okay? And then I want to do something a little bit more, and that is I'm going to make it different in a way that I'm never using the digits zero or nine. I'm just always using the other digits and not zero and it would form a kind of diagonal going down and to the right, and that, for that reason, this argument is called the diagonal argument because we're looking at the Nth digit of the Nth number, and those exist on a kind of diagonal going down. And we've made our number Z so that the Nth digit of Z is different from the Nth digit of the Nth number. But now it follows that Z is not on the list because Z is different from R1 because, well, the first digit after the decimal point of Z is different from the first digit of R1 after the decimal point. That's exactly how we built it. And the second digit of Z is different from the second digit of R2 and so on. The Nth digit of Z is different from the Nth digit of R sub N for every N. So therefore, Z is not equal to any of these numbers R sub N. And but that's a contradiction because we had assumed that we had every real number on the list, but yet here is a real number Z that's not on the list, okay? And so that's the main contradiction. - And so it's a kind of proof by construction. - Exactly. So given a list of numbers, Cantor's proving... It's interesting that you say that actually, because there's a kind of philosophical controversy that occurs in connection with this observation about whether Cantor's construction is constructive or not. Given a list of numbers, Cantor gives us a specific means of constructing a real number that's not on the list, is a way of thinking about it. There's this one aspect, which I alluded to earlier, but some real numbers have more than one decimal representation, and it causes this slight problem in the argument. For example, the number one, you can write it as 1.0000 forever, but you can also write it as 0.999 forever. Those are two different decimal representations of exactly the same number. - You beautifully got rid of the zeros and the nines. Therefore, we don't need to even consider that, and the proof still works. - Exactly, because the only kind of case where that phenomenon occurs is when the number is eventually zero or eventually nine. And so since our number Z never had any zeros or nines in it, it wasn't one of those numbers. And so actually, in those cases, we didn't need to do anything special to diagonalize. Just the mere fact that our number has a unique representation already means that it's not equal to those numbers. So maybe it was controversial in Cantor's day more than 100 years ago, but I think it's most commonly looked at today as, you know, one of the initial main results in set theory, and it's profound and amazing and insightful and the beginning point of so many later arguments. And this diagonalization idea has proved to be an extremely fruitful proof method, and almost every major result in mathematical logic is using in an abstract way the idea of diagonalization. It was really the start of so many other observations that were made, including Russell's paradox and the halting problem and the recursion theorem, and so many other principles are using diagonalization at their core. So... - Can we just step back a little bit? - This infinity crisis led to a kind of rebuilding of mathematics. So it'd be nice if you lay out the things it resulted in. So one is set theory became the foundation of mathematics. All mathematics could now be built from sets, giving math its first truly rigorous foundation. The axiomatization of mathematics, the paradoxes forced mathematicians to develop ZFC and other axiomatic systems, and mathematical logic emerged. Gödel, Turing, and others created entire new fields. So can you explain what set theory is and, how does it serve as a foundation of modern mathematics and maybe even the foundation of truth? - That's a great question. Set theory really has two roles that it's serving. There's kind of two ways that set theory emerges. On the one hand, set theory is its own subject of mathematics, with its own problems and questions and answers and proof methods. And so really, from this point of view, set theory is about the transfinite recursive constructions or well-founded definitions and constructions. And those ideas have been enormously fruitful and set theorists have looked into them and developed so many ideas coming out of that. But set theory has also happened to serve in this other foundational role. It's very common to hear things said about set theory that really aren't taking account of this distinction between the two roles that it's serving. It's its own subject, but it's also serving as a foundation of mathematics. So in its foundational role, set theory provides a way to think of a collection of things as one thing. That's the central idea of set theory. A set is a collection of things, but you think of the set itself as one abstract thing. So when you form the set of real numbers, then that is a set. It's one thing. It's a set, and it has elements inside of it. So it's sort of like a bag of objects. A set is kind of like a bag of objects. And so we have a lot of different axioms that describe the nature of this idea of thinking of a collection of things as one thing itself, one abstract thing. - And axioms are, I guess, facts that we assume are true, based on which we then build the ideas of mathematics. So there's a bunch of facts, axioms about sets that we can put together, and if they're sufficiently...... powerful, we can then build on top of that a lot of really interesting mathematics. - Yeah, I think that's right. So, I mean, the history of the current set theory axioms, known as the Zermelo-Fraenkel axioms, came out in the early 20th century with Zermelo's idea. I mean, the history is quite fascinating because Zermelo in 1904 offered a proof that what's called the axiom of choice implies the well-order principle. So he described his proof, and that was extremely controversial at the time. And there was no theory, there weren't any axioms there. Cantor was not working in an axiomatic framework. He didn't have a list of axioms in the way that we have for set theory now, and Zermelo didn't either. And his ideas were challenged so much with regard to the well-order theorem— —that he was pressed to produce the theory in which his argument could be formalized, and that was the origin of what's known as Zermelo set theory. - And going to perplexity, the axiom of choice is a fundamental principle in set theory which states that for any collection of non-empty sets, it is possible to select exactly one element from each set, even if no explicit rule to make the choices given. This axiom allows the construction of a new set containing one element from each original set, even in cases where the collection is infinite or where there is no natural way to specify a selection rule. So this was controversial and this was described before there's even a language for axiomatic systems. - That's right. So on the one hand, I mean, the axiom of choice principle is completely obvious that we want this to be true, that it is true. I mean, a lot of people take it as a law of logic. If you have a bunch of sets, then there's a way of picking an element from each of them. picking an element from each of them. There's a function. If I have a bunch of sets, then there's a function that, when you apply it to any one of those sets, gives you an element of that set. It's- it's a completely natural principle. I mean, it's called the axiom of choice, which is a way of sort of anthropomorphizing the mathematical idea. It's not like the function is choosing something. I mean, it's just that if you were to make such choices, there would be a function that consisted of the choices that you made. And the difficulty is that when you- when you can't specify a rule or a procedure by which you're making choices, then it's difficult to say choices, then it's difficult to say what the function is that you're asserting exists. function is that you're asserting exists. You know, you- you want to have the view that, well, there is a way of choosing. I don't have an easy way to say what the function is, but there definitely is one. Yeah, this is the way of thinking about the axiom of choice. - So we're going to say the- the- the three letters of ZFC may be a lot on this conversation. You already mentioned- - Right - ...Zermelo-Fraenkel set theory, that's the Z and the F and the C in that is this... and the C in that is this... Comes from this axiom of choice. - That's right. - So ZFC sounds like a super technical thing, but it is the set of axioms that's the foundation of modern mathematics. - Yeah, absolutely. So one should be aware also that there's huge parts of mathematics that don't... That pay attention to whether the axiom of choice is being used and they don't want to use the axiom of choice, so they work out the consequences that's- that are possible without the axiom of choice or with weakened forms of- of Zermelo-Fraenkel set theory and so on. And that's quite a- there's quite a vibrant amount of work in that area. I mean, but going back to the axiom of choice for a bit, it's maybe interesting to- to give Russell's description of how to think about the axiom of choice. So Russell describes, this rich person who has a- an infinite closet. And in that closet, he has infinitely many pairs of shoes and he tells his butler to "Please go and give me one shoe from each pair." And- and the butler can do this easily because he can... For any pair of shoes, he can just always pick the left shoe. I mean, there's a way of picking that we can describe. We always take the left one or always take the right one, or take the left one if it's a red shoe and the right one if it's a brown shoe or, you know. We can invent rules that would result in these kind of choice functions, so we can describe explicit choice functions. And for those cases, you don't need the axiom of choice you don't need the Axiom of Choice to know that there's a choice function. When you can describe a specific way of choosing, then you don't need to appeal to the axiom to know that there's a choice But the problematic case occurs when you think about the infinite collection when you think about the infinite collection of socks that the person has in their closet. And if we assume that socks are sort of indistinguishable within each pair, you know, they match each other, indiscernible, then the- the butler wouldn't have any kind of rule for which sock in each pair to pick. And so it's not so clear that he has a way of- of producing one sock from each pair because... Right? So that's what's at stake, is the question of whether you can specify a rule by which the choice function, you know, a rule that it obeys that defines the choice function, or whether there's sort of this arbitrary choosing aspect to it. That's when you need the axiom of choice to know that there is such a function. But of course, as a matter of mathematical ontology, we might find attractive the idea that, well, look, I mean, I don't- not every way of choosing the socks has to be defined by rule. Why should everything that exists in mathematical reality follow a rule or a procedure of that sort? If I have the idea that my mathematical ontology is rich with objects, then I think that, that there are all kinds of functions and ways of choosing. Those are all part of the mathematical reality that I wanna be talking about.... and so I don't have any problem asserting the Axiom of Choice. Yes, there is a way of choosing, But I can't t- necessarily tell you what it is. But in a mathematical argument, I can assume that I fix the choice function because I know that there is one. So it's a... The philosophical difference between working when you have the Axiom of Choice and when you don't is the question of this constructive nature of the argument. So if you make an argument and you appeal to the Axiom of Choice, then maybe you're admitting that the objects that you're producing in the proof are not gonna be constructive. You're not gonna be able to necessarily say specific things about them. But if you're just claiming to make an existence claim, that's totally fine. Whereas if you have a constructive attitude about ma- the nature of mathematics, and you think that mathematical claims maybe are only warranted when you can provide an explicit procedure for producing the mathematical objects that you're dealing with then you're probably gonna wanna deny the axiom of choice and maybe much more. - Can we maybe speak to the axioms that underlie ZFC? So cone of perplexity, ZFC, or Zermelo-Fraenkel set theory with the Axiom of Choice, as we mentioned, is the standard foundation for most modern mathematics. It consists of the following main axioms: Axiom of Extensionality, Axiom of Empty Set, Axiom of Pairing, Axiom of Union, Axiom of Power Set, Axiom of Infinity, Axiom of Separation, Axiom of Replacement, Axiom of Regularity, and Axiom of Choice. Some of these are quite basic, but it would be nice to kinda give people a sense- ...of what it means to be an axiom. Like, what kind of basic facts we can lay on the table on which we can build some beautiful mathematics. - Yeah, so the history of it is really quite fascinating. So, Zermelo introduced most of these axioms, I mean, as part of what's now called Zermelo set theory, to formalize his proof from the Axiom of Choice to the Well-Order Principle, which was an extremely controversial result. So in 1904, he gave the proof without the theory, and then he was challenged to provide the theory. And so in 1908, he produced the Zermelo set theory and gave the proof that in that theory, you can prove that every set admits a well ordering. And so the axioms on the list, these things like extensionality, express the most fundamental principles of the understanding of sets that he wanted to be talking about. So for example, extensionality says if two sets have the same members, then they're equal. So it's this idea that the sets consist of the collection of their members, and that's it. There's nothing else that's going on in the set. So it's just if two sets have the same members, then they are the same set. So it's maybe the most primitive axiom in some respect. - Well, there's also, just to give a flavor, there exists a set with no elements, called the empty set. For any two sets, there's a set that contains exactly those two sets as elements. For any set, there's a set that contains exactly the elements of the elements of that set, so the union set. And then there's the power set. For any set, there's a set whose elements are exactly the subsets of the original set, the power set. In the axiom of infinity, there exists an infinite set, typically a set that contains the empty set and is closed under the operation of adding one more element. Back to our hotel example. - And there's more, but this is kind of fascinating. Just put yourself in the mindset of people at the beginning of this, of trying to formalize set theory. It's fascinating that humans can do that. - I read some historical accounts by historians about that time period, specifically about Zermelo's axioms and his proof of the well-order theorem. And the historians were saying never before in the history of mathematics has a mathematical theorem been argued about so publicly and so vociferously as that theorem of Zermelo's. And it's fascinating also because the axiom of choice was widely regarded as a kind of, you know, basic principle at first, but then when, but people were very suspicious of the well-order theorem because no one could imagine a well ordering, say, of the real numbers. And so this was a case when Zermelo seemed to be, from principles that seemed quite reasonable, proving this obvious untruth. And so people were, mathematicians were objecting. But then Zermelo and others actually looked into the mathematical papers and so on of some of the people who had been objecting so vociferously, and found, in many cases, that they were implicitly using the axiom of choice in their own arguments, even though they would argue publicly against it. Because it's so natural to use it because it's such an obvious principle in a way. I mean, it's easy to just use it by accident if you're not critical enough and you don't even realize that you're using the axiom of choice. That's true now, even. People like to pay attention to when the axiom of choice is used or not used in mathematical arguments, up until this day. It used to be more important. In the early 20th century it was very important because people didn't know if it was a consistent theory or not, and there were these antinomies arising. and so there was a worry about consistency of the axioms. but then, of course, eventually, with the result of, of Godel and Cohen and so on, they... this consistency question specifically about the axiom of choice sort of falls away. We know that the axiom of choice itself choice itself will never be the source of inconsistency in set theory. If there's inconsistency with the axiom of choice, then it's, it's already inconsistent without the axiom of choice. So it's not the cause of inconsistency. And so in that... from that point of view, the need to pay attention to whether you're using it or not from a consistency point of view is somehow less important. But still there's this reason to pay attention to it on the grounds of these constructivist ideas that I had mentioned earlier. - And we should say, in set theory, consistency means that it is impossible to derive a contradiction from the axioms of the theory. It means that there are no contradictions. That's a... - A consistent axiomatic system is that there are no contradictions. - A consistent theory is one for which you cannot prove a contradiction from that theory. - Maybe a quick pause, a quick break, a quick bathroom break. You mentioned to me offline we were talking about Russell's paradox and that there's a- a nice, another kind of anthropomorphizable proof of uncountability. I was wondering if you can lay that out. - Oh yeah, sure. Absolutely. - Both Russell's paradox and the proof. - Right. So 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. It's a kind of distilling the abstract diagonalization idea without being 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, towards 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. Another set, I'm going to 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 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. 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 particular individual, you know? And- ...but that... let's call that person, it should be a name starting with D, so Diana. 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 set of individuals that are not in their set. 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. 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'd like to talk about it this way. For any collection of people, you can form more committees from them than there are people, even if you have infinetely many people. 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 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. With no members and never meets and so on. Or is the empty committee meeting all the time? I'm not sure. - Yeah. That's... wow, that's a profound question. And does a committee with just one member meet also as a- - Yeah, maybe it's always in session. I don't know. So the claim is that there are more committees than people. Okay. Suppose not. Well, then we could make an association between the people and the committees. So we would have 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. 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 own committee. 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 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. You know, apples and oranges and grapes, whatever. And a fruit salad consists of some collection of those fruits. So there's the banana, pear, grape salad and so on. There are 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. 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 of all the fruits that are not in the salad that's named after them. And that's a perfectly good salad. It might be the kind of diet salad, if it was the empty salad, or it might be the universal salad which had all fruits in it, if all the fruits were in it. Or it might have just some and not all. So that diagonal salad would have to be named after some fruit. So let's suppose it's named after durian, meaning that it was associated with durian in the one-to-one correspondence. And then we ask, well, is durian in the salad that it's named after? And if it is, then it shouldn't be. And if it isn't, then it should be. And so it's again the same contradiction. So all of those arguments are just the same as Cantor's proof that the power set of any set is bigger than the set. And this is exactly the same logic that comes up in Russell's paradox, because Russell is arguing that the class of all sets can't be a set, because if it were, then we could form the the set of all sets that are not elements of themselves. So basically, what Russell is proving is that there are more collections of sets than elements. Because we can form the diagonal class, you know, the class of all sets that are not elements of themselves. If that were a set, then it would be an element of itself if and only if it was not an element of itself. It's exactly the same logic in all four of those arguments. Yeah. So there can't be a class of all sets, because if there were, then there would have to be a class of all sets that aren't elements of themselves. But that set would be an element of itself if and only if it's not an element of itself, which is a contradiction. So this is the essence of the Russell paradox. I don't call it the Russell paradox. Actually, when I teach it, I call it Russell's theorem. There's no universal set. And it's not really confusing anymore. At the time, it was very confusing, but now we've absorbed this nature of set theory into our fundamental understanding of how sets are, and it's not confusing anymore. I mean, the history is fascinating though about the Russell paradox, because before that time, Frege was working on his monumental work undertaking, implementing the philosophy of logicism, which is the attempt to reduce all of mathematics to logic. So Frege wanted to give an account of all of mathematics in terms of logical notions, and he was writing this monumental work and had formulated his basic principles. And those principles happened to imply that for any property whatsoever, you could form the set of objects with that property. This is known as the general comprehension principle. And he was appealing to the principles that support that axiom, throughout his work. I mean, it wasn't just an incidental thing. He was really using this principle. And Russell wrote him a letter when he observed the work in progress, that there was this problem, because if you accept the principle that for any property whatsoever, you can make a set of objects with that property, then you could form the set of all sets that are not members of themselves. That's just an instance of the general comprehension principle. And the set of all sets that aren't elements of themselves can't be a set, because if it were, then it would be an element of itself if and only if it's not a member of itself, and that's a contradiction. And so Russell wrote this letter to Frege, and it was just at the moment when Frege was finishing his work. It was already at the publishers and, you know, in press basically. But it's completely devastating. I mean, it must have been such a horrible situation for Frege to be placed in because he's finished this monumental work, you know, years of his life dedicated to this, and Russell finds this basically one-line proof of a contradiction in the fundamental principles of the thesis that completely destroys the whole system. And Frege had put in the appendix of his work a response to Russell's letter in which he explained what happened, and he wrote very gracefully, "Hardly anything more unwelcome can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished. This is the position into which I was put by a letter from Mr. Bertrand Russell as the printing of this volume was nearing completion." And then he goes on to explain the matter, it concerns his basic law five, and so on, and... - It's heartbreaking. I mean, there's nothing more traumatic to a person who dreams of constructing mathematics all from logic. to get a very clean, simple contradiction. I mean, that's just... - You devote your life to this work, and then it's shown to be contradictory, and that must have been heartbreaking. - What do you think about the Frege project, the philosophy of logic, the dream of the power of logic- - ... to construct a mathematical universe? - So, of course, the project of logicism did not die with Frege, and it was continued, and, you know, there's a whole movement, the neologicists and so on, in contemporary times even. But my view of the matter is that, really, we should view the main goals of logicism are basically completely fulfilled in the rise of set-theoretic foundationalism. I mean, When you view ZFC as the foundation of mathematics, and in my view, the principles of ZFC are fundamentally illogical in character including the axiom of choice, as I mentioned, as a principle of logic. This is a highly disputed point of view, though, cause a lot of people take even the axiom of infinity as inherently mathematical and not logical and so on. But I think if you adopt the view that the principles of ZFC have to do with the principles of abstract, you know, set formation, which is fundamentally logical in character, then it's complete success for logicism. So the fact that set theory is able to serve as a foundation means that mathematics can be founded on logic. - 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 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 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 wanna give that up, despite the danger of these paradoxes, these contradictions, basically, is how some people viewed them. And so, - this minefield of paradoxes. Yeah. - 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 going to have this strong theory, this set theory that we want to be proving our theorems in but I I mean, on the one hand, we want it to be as strong as possible. We would like it to answer all the questions." There's another famous quote of Hilbert in his retirement address where, he proclaims, "Wir müssen wissen, wir werden wissen." So, "We must know, 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 want to solve and he is saying, "We're going to do it. We're going to solve all these problems." So we want to propose this strong theory and one has the sense that he had in mind set theory in which all the questions are going to be answered. Okay? But secondly, we want to combine that with, in a very weak arithmetic, purely finitistic theory, we want to prove that the reasoning process of the strong theory is safe. Okay? So in order to make sense of that point of view, you basically have to invent the philosophy of formalism, where we can look at what is a proof, what is the nature of mathematical reasoning. And on Hilbert's way of thinking about this, a proof is basically itself a finitistic kind of object. It's a sequence of... If you think about the nature of what a proof is, 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 this is 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. - So when you think of proof as, 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. - Yeah, that's helpful. - That's wild. - The main thing about formalism is that 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 that's a very sort of uncertain realm maybe and the source of the paradoxes and so on in some people's minds. But the reasoning process itself consists of writing down sequences of symbols on your page and, you know, undertaking or, an argument with them which is following these finitary rules. And 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. And then Hilbert wanted to prove in this purely finitary theory that if we follow the rules of that game, we're never going to get a contradiction. So those were the two aims of the Hilbert program, is to found the strong infinitary theory, probably set theory, which is going to answer all the questions. And then secondly, prove in the finitary theory that the strong theory is safe. In other words, consistent, yeah? - What does the word "finitary" in finitary theory mean? - Yeah. Well, this is, of course, philosophically contentious, and people have different ideas about what exactly it should mean. So there's hundreds of papers on exactly that question. But 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 going to have a theory, you know, finite strings of symbols. 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. 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. 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. 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. 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 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? - So according 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 a 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 very particular kind of arithmetic that is finitary. - You know, in my... I view it as finitary, but this is a contentious view. Not everyone agrees with that. That's what I was trying to hint at. - Okay. I got it. All right. - Peano arithmetic is one of the hugely successful theories of the natural numbers and elementary number theory. Essentially, all of classical number theory, so whatever kind of theorems you want to be proving about the prime numbers or factorization or any kind of finitary reasoning about finite combinatorial objects, all of it can be formalized in Peano arithmetic. I mean, that's the basic situation. Of course, one has to qualify those statements in light of the Gödel incompleteness theorem, but for the most part, the classical number theoretic analysis of the finite numbers is almost entirely developable inside Peano arithmetic. So if we go back to the Hilbert program, so Hilbert has these two goals: produce the strong theory which is going to 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 defeats both of those goals decisively, completely. 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? - And if I may, going to Perplexity's 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. - Right. Exactly right. Let's imagine what it would be like if he 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. 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 would 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 or from the machine or the answer to come out no. So the nature of mathematical investigation in Hilbert's world is one of just turning the crank of the theorem enumeration machine, devoid of creative thinking or imagination, it's just getting the answer from this by rote. procedure. So Hilbert, in effect, is telling us, I mean, with his program, that 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 inconsistencies, and so how can we kind of block them? It seems natural, first of all, to have a strong theory that's going to answer all the questions, because the idea of logical independence and pervasiveness that we now know exists just wasn't, you know, there was no known. They didn't know anything like that happening ever. And so 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 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 in a way that 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, would have questions that they stumble with and are unable to answer. Independence 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 Gödel'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 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 takedown of the Hilbert program, which is really quite remarkable, the extent to which his theorem just really answered that whole puzzle. It's quite amazing. I mean, there's another aspect, kind of easy to think about. I mean, 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." 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, 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. - Just for clarification, you used the word theory. Is it, in this context, synonymous with axiomatic system? - Right. So in mathematical logic, "theory" is a technical term. And it means any set of sentences in a formal language. And so if you say axiomatic system, it's basically synonymous to my usage with theory. So a theory means, you know, the consequences of a set of axioms or... People are sometimes unclear on whether they just mean the axioms or the consequences of the axioms, but... - So theory includes both the axioms and the consequences of the axioms, and you use it interchangeably and the context is supposed to help you figure out which of the two you're talking about? The axioms or the consequences? Or maybe to you, they're basically the same? - Yeah, well, they're so closely connected, although all the features aren't the same. So if you have a computable list of axioms for a theory, then you can start enumerating the consequences of the axioms, but you won't be able to computably decide whether a given statement is a consequence or not. You can enumerate the consequences, so you can semi-decide the consequences, but you won't be able to decide yes or no whether a given statement is a consequence or not. So it's the distinction between a problem being computably decidable and a problem being computably enumerable, which, was made clear following the work of Turing and others that came from that. I mean, so that's one difference between the list of axioms of the theory and the theory itself. The axioms could be... You can decide, maybe computably, whether something is an axiom or not, but that doesn't mean that you can decide computably whether or not something is a theorem or not. Usually, you only get to decide the positive instances. If something is a theorem, you will eventually come to recognize that, but if something isn't a theorem, maybe at no point will you be able to say, "No, that's not a theorem." - And that's of course connected to the halting problem. ...and all of these contradictions and paradoxes are all nicely, beautifully interconnected. So can we just linger on Gödel's incompleteness theorem? You mentioned the two components there. You know, there's so many questions to ask, like what is the difference between provability and truth? What is true and what is provable? Maybe that's a good line to draw. - Yeah, this is a really core distinction that it's fascinating to me to go back and read even the early 20th century people before Gödel and Tarski, and they were totally sloppy about this distinction between truth and proof. It wasn't clear at all until Gödel, basically. Although even as late as Bourbaki has the kind of confusion in this foundational work. So, this standard graduate-level textbook 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. 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 reality. I mean, okay, when I talk about reality, I'm not talking about physical reality. I'm talking about mathematical reality. 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 want to 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 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, "Snow is white," 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 it syntactically. So, 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 is true, that just means that snow is white. And that's why it's called the disquotational theory because we remove the quotation marks. from the assertion, right? 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 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, that 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- - Yeah, it has the disquotation. And so this idea can be done for all the logical connectors and quantifiers and everything. You're applying Tarski's idea of disquotation, and it allows you to define by induction 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. 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. 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 arrangement of sentences in the formal language that accord with the logical rules of a proof system. So there are 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 ponens. This is the rule of modus ponens. And, you know, there are a lot of other rules. Some people would call this implication elimination. There are different kinds of proof systems. There are 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. They're truth- preserving arguments. Okay? 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 then the consequence is also true 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 you should be able to recognize whether or whether or not something is a proof or not. So there's a computable aspect 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 don't want a proof system in which someone claims to have a proof, but we can't check that fact, whether it's a proof or not. We want to be able to correctly adjudicate all claims to having a proof. - Yeah. A mathematician comes to mind that said he has a proof, but the margins are too small - to continue. - Exactly. So - So that doesn't count as a proof. - Yeah. 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. - 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? - Right. 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, and Godel proved that this is impossible. You cannot write down a computable list of axioms that is complete in that sense. There will always be statements... If the theory is consistent, there will always be statements that you cannot prove and you cannot refute. So they are independent of that theory. - How traumatic is that, that there are statements that are independent from the theory? - I mean, my view is that this isn't traumatic at all. This is rather completely eye-opening in terms of our understanding of the nature of mathematical reality. I mean, we're not... We understand this profound fact about our situation with regard to mathematical truth. The incompleteness theorem tells us, look, we just can't write down a list of axioms that is going to be consistent and it's going to answer all the questions. It's impossible. And so I don't think of it as trauma. I just think, look, this is the nature of mathematical reality and it's good that we know it, and so now we need to move on from that. And, you know, do what we can in light of that. - Is it fair to say that in general it means if I give you a statement, you can't know if your axiomatic system would be able to prove it? - That's right. In general, you cannot. The provability problem, we can formulate it as a decision problem. Given a theory and given a statement, is that statement a consequence of that theory? Yeah. This is one of the most famous decision problems. In fact, the very first one, because it's equivalent to the Hilbert-Ackermann Entscheidungsproblem, which is also appearing in the title of Turing's 1936 paper that was so important for computability theory. So, it's a formulation of the Entscheidungsproblem. Does a given theory have a given statement as a logical consequence? Which, because of Gödel's completeness theorem, not his incompleteness theorem, but his earlier completeness theorem, Gödel had proved that the…

Transcript truncated. Watch the full video for the complete content.