Russell's paradox devastated Frege's logicist project—the principle that for any property you can form the set of objects with that property leads to a contradiction—and Hilbert's program responded by proposing to prove the consistency of strong set-theoretic mathematics using weak finitistic reasoning.

(00:00: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. (00:00:12) He is the number one highest rated user on MathOverflow, which I think is a legendary accomplishment. (00:00:19) MathOverflow, by the way, is like StackOverflow, but for research mathematicians. (00:00:24) He is also the author of several books, including Proof and the Art of Mathematics and Lectures on the Philosophy of Mathematics. (00:00:35) And he has a great blog, infinitelymore.xyz. (00:00:41) 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, (00:00:54) truth, and the mathematical paradoxes that challenged some of the greatest minds of the 20th century. (00:01:02) 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. (00:01:22) Through all of it, (00:01:23) a recurring thought comes to me. (00:01:26) How damn lucky I am to be alive and to get to experience so much love from folks across the world. (00:01:34) 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. (00:01:47) I got a little bit of hate and a whole lot of love (00:01:52) and I wouldn't have it any other way. (00:01:55) I'm grateful for all of it. (00:01:57) And now a quick few second mention of a sponsor. (00:02:01) Check them out in the description or lexfriedman.com slash sponsors. (00:02:06) It is in fact the best way to support this podcast. (00:02:10) We got Perplexity for curiosity-driven knowledge exploration, Fin for customer service AI agents, Miro for brainstorming ideas with your team, Code Rabbit for code review, Chevron for reliable energy that powers data centers, Shopify for selling stuff online, Element for electrolytes, and Masterclass for learning. (00:02:32) Choose wisely, my friends. (00:02:35) We have a bunch of sponsors this time because it's the end of the year and I haven't been publishing (00:02:40) podcasts have been laying low, as I mentioned in the introduction. (00:02:46) And I'm just really grateful for the patience and the support of the sponsors. (00:02:51) The companies and the humans behind those companies have been really amazing over the years. (00:02:58) So I don't think I would be able to do many of the crazy and the difficult things I'm doing with this podcast without the support of the sponsors. (00:03:08) So please go check out their stuff. (00:03:10) Please go support them. (00:03:11) Please buy whatever they're selling. (00:03:13) Really, it helps A lot. (00:03:15) It is the best way to support the podcast. (00:03:18) I'll do the full ad reads now. (00:03:19) I try to make them interesting, but if you skip, please still do check out the sponsors. (00:03:24) I enjoy their stuff. (00:03:25) Maybe you will too. (00:03:26) To get in touch with me for whatever reason, go to lexfriedman.com slash contact. (00:03:33) In case I don't get a chance to say this, happy New Year. (00:03:37) Let's make this 2026 a fun one. (00:03:41) All right, let's go. (00:03:43) This episode is brought to you by Finn, the number one AI agent for customer service. (00:03:49) 65% average resolution rate. (00:03:52) Trusted by over 6,000 customers, including some incredible companies, incredible technology companies, incredible AI companies. (00:04:01) When an AI company trusts you to do the customer service, you know you're legit. (00:04:06) built to handle complex multi-step queries like returns, exchanges, and disputes. (00:04:12) I really do think a big part of what makes a product or a company incredible is the customer service. (00:04:20) And getting that right, where you can handle, you can help take care. (00:04:29) of the needs of the customer and the complicated problems. (00:04:32) Sometimes it's hand-holding, never talking down to them, trying not to do too basic of a solution to a very unique particular kind of problem because each customer problem, yes, might look like a common problem, but it has unique certain characteristics to it that if you pay attention to them and you take care of them, (00:04:56) You can really make a person happy. (00:04:59) And a company that makes a large number of people happy is going to be a great company. (00:05:06) Anyway, go to fin.ai/lex to learn more about transforming your customer service and scaling your support team. (00:05:13) That's fin.ai/lex. (00:05:17) This episode is also brought to you by Miro, an online collaborative platform. (00:05:22) They have this innovation workspace that blends AI and human creativity to turn ideas into real things, into results. (00:05:33) One of the things I love the most, recently getting back into the research environment, working on a lot of fun robotics projects with a lot of brilliant mechanical engineers, software engineers, machine learning people, robotics people, (00:05:50) is just the conversations we have. (00:05:54) Sometimes the aimless exploration of ideas, sometimes banter, sometimes humor, sometimes real rigor over mathematical models of a particular phenomena, whether it's the controllers, whether it's the perception of the robots, whether it's the different stages of the ML process, whether it's the different layers of the stack, (00:06:19) of the robotics platforms from the theory to the software to the hardware and just talking through it, tossing ideas back and forth, talking shit back and forth. (00:06:33) It's such a fun thing to do. (00:06:36) It makes it fun. (00:06:37) And I think Miro is striving to do that in the cyberspace. (00:06:43) Yeah, saves time. (00:06:44) Yeah, it's user-friendly, but it also tries to make the whole ideation, team brainstorming, teamwork fun. (00:06:54) Help your teams develop great ideas into results with Miro. (00:06:58) Go to miro.com to find out how. (00:07:00) That's M-I-R-O.com. (00:07:04) This episode is also brought to you by Code Rabbit, a platform that provides AI-powered code reviews directly within your terminal. (00:07:13) As more and more code is generated, developers end up spending more and more time reading and reviewing code. (00:07:20) And if you're trying to ship code, production code, code you can rely on, there's this whole process of reviewing it. (00:07:30) And that's what CodeRabbit specializes in, used by... (00:07:34) over 100,000 open source projects. (00:07:37) It's a very specific application of AI to handle this very specific part, but a crucial part of the software engineering process. (00:07:45) If you want to ship a thing, you want to make sure the thing runs. (00:07:49) And to make sure that it runs, you have to understand the code deeply. (00:07:53) It supports basically all programming languages. (00:07:57) To try it out, you want to install the Code Rabbit CLI today at coderabbit.ai/lex. (00:08:05) That's coderabbit.ai/lex. (00:08:10) This episode is also brought to you by Chevron, an energy company that delivers affordable, reliable energy to U.S. (00:08:17) data centers. (00:08:19) Demand for electricity is growing. (00:08:23) That's an understatement of the century. (00:08:25) Due to AI compute requirements, the clusters are growing, the super clusters. (00:08:32) It's just incredible what the various companies are doing. (00:08:36) The size and the power draw required to achieve that compute size is insane. (00:08:43) Chevron provides multi-gigawatts of delivered power with the flexibility to scale further. (00:08:51) I've been doing a lot of reading. (00:08:53) and historical periods before the Industrial Revolution, talking about the Roman Empire, the Viking Age, ancient Greece, and so on. (00:09:03) All of it was before this engine that is human civilization, the mechanized human civilization, the electrified human civilization was born. (00:09:15) And it's so interesting to think how that changed everything. (00:09:21) Just the speed of everything keeps increasing. (00:09:24) The intelligence of everything, the collective intelligence of our species keeps increasing, exponentially so. (00:09:31) And this machine, it's almost awakening. (00:09:35) That's how I think of energy. (00:09:37) It's powering the awakening. (00:09:40) What an incredible system life on Earth is. (00:09:44) All of us together, every living organism, collaborating, (00:09:49) leveraging whatever energy we get into creating something incredible. (00:09:55) Anyway, visit chevron.com/power to learn more. (00:10:00) That's chevron.com/power. (00:10:05) This episode is brought to you by Shopify. (00:10:08) I like how I'm getting more and more intense. (00:10:11) A platform designed (00:10:13) for anyone to sell anywhere with a great looking online store. (00:10:17) If you want to understand why Shopify is awesome on the engineering side, you want to go listen to the conversation I had with DHH, who espoused the beauty, the power, the elegance of Ruby on Rails that Shopify was built on. (00:10:35) On another note, I went to NeurIps and hung around (00:10:40) in the booth, I guess you could say, of Shopify Engineering. (00:10:44) It's just a bunch of great engineers talking about the various aspects of what it took to bring Shopify to life. (00:10:50) I think it's Shopify.engineering if you're curious, actually. (00:10:55) If this is your kind of thing, if you want to understand why Shopify as a machine, as a service, is incredible, you go there. (00:11:04) Anyway, that's not the point. (00:11:08) Engineering is just awesome. (00:11:09) So it's always nice to know there's great engineering behind a thing. (00:11:13) And the thing is a way to sell stuff online. (00:11:17) That's shopify.com. (00:11:19) And you can sign up for a $1 per month trial period at shopify.com slash Lex. (00:11:24) That's all lower case. (00:11:26) Go to shopify.com slash Lex to take your business to the next level today. (00:11:32) I'm doing the announcer voice more and more. (00:11:38) and doing so poorly. (00:11:41) This episode is also brought to you by Element, my daily zero sugar and delicious electrolyte mix that I'm currently drinking, that I'm currently enjoying, enjoying a little too much, but really never enough because it's always good for you. (00:11:56) Really good balance of electrolytes. (00:11:58) Sodium, potassium, and magnesium, always the same flavor. (00:12:03) You could say I'm boring because I really don't explore enough. (00:12:07) Last time I tried other flavors, they were all good, but I'm just such a creature of habit. (00:12:11) Watermelon salt. (00:12:13) I fell in love with watermelon salt. (00:12:15) I am in a monogamous relationship with watermelon salt. (00:12:19) I'm sticking by. (00:12:21) My favorite flavor, the flavor of champions, my friends. (00:12:25) I'm going to go train jiu-jitsu a little bit here, and I'm going to get an element with me because I intend to do as many rounds. (00:12:33) I'm going to show up at the beginning (00:12:37) and I'm gonna go to the end and beyond, which means potentially an hour and a half, maybe two hours of training. (00:12:45) One must celebrate the end of the year properly, my friends, and replenish properly after battle with some electrolytes. (00:12:56) Get a free ACON sample pack with any purchase, trytadrinkelement.com/lex. (00:13:02) This episode is also brought to you by Masterclass. (00:13:06) A place you can go to learn from the best people at their respective disciplines. (00:13:13) Over 200 classes. (00:13:15) Phil Ivey on poker. (00:13:16) Aaron Franklin on BBQ and brisket. (00:13:19) By the way, I need you to get me some BBQ. (00:13:22) It's been forever. (00:13:24) If I don't get BBQ at least once a month and pig out irresponsibly at least once a month, I feel less Texan. (00:13:33) And I fell in love with Texas, and I intend to keep it that way. (00:13:39) Carlos Santana on guitar, of course, Europa, one of my favorite instrumental songs. (00:13:44) It's a way to make the guitar cry, make it sing. (00:13:49) Now, it could also be like Tom Morello, also on guitar, also has a masterclass. (00:13:56) Now, he can make (00:13:59) a guitar, the instrument of rebellion. (00:14:04) Now, since we're talking about mathematics here with Joel, we must mention that Terence Tao, the great Terence Tao, also has a masterclass on mathematical thinking. (00:14:15) And finally, Martz Scorsese, a person I absolutely must talk to, figure out a way to talk to him. (00:14:22) But in the meantime, he also has a masterclass on filmmaking. (00:14:27) one of the greatest directors in history, one of the greatest storytellers in history. (00:14:32) I am such a huge fan of everything he has created. (00:14:35) Anyway, you and I can partake in a little bit of the magic that is Martin Scorsese by going to masterclass.com slash Lex to get up to 50% off. (00:14:46) That's masterclass.com slash Lex for up to 50% off. (00:14:53) I urge you to gift someone masterclass for the holidays. (00:14:58) Speaking of which, friends, happy holidays, happy New Year. (00:15:03) I love you all. (00:15:05) This is the Lex Friedman Podcast. (00:15:07) 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. (00:15:19) And now, dear friends, here's Joel David Hamkins. (00:15:40) Some infinities are bigger than others. (00:15:43) This idea from Cantor at the end of the 19th century, I think it's fair to say, broke mathematics before rebuilding it. (00:15:51) And I also read that this was a devastating and transformative discovery for several reasons. (00:15:57) So one, it created a theological crisis because infinity is associated with God. (00:16:02) How could there be multiple infinities? (00:16:04) And also Cantor was deeply religious himself. (00:16:07) Second, there was a kind of mathematical civil war. (00:16:11) The leading German mathematician chronicler called Cantor a corrupter of youth and tried to block his career. (00:16:20) Third, many fascinating paradoxes emerged from this. (00:16:24) like Russell's paradox about the set of all sets that don't contain themselves. (00:16:29) And those threaten to make all of mathematics inconsistent. (00:16:33) And finally, on the psychological side, on 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. (00:16:46) So laying that all out on the table, can you explain the idea of infinity? (00:16:51) that some infinities are larger than others, and why was this so transformative to mathematics? (00:16:58) Well, that's a really great question. (00:17:01) 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 (00:17:18) the impossibility, according to him, of achieving an actual infinity. (00:17:23) 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, thereby understanding the total area in terms of the sum of the areas of the pieces that he put into it. (00:17:41) And it proceeded on this kind of potential, this potentialist understanding of infinity for hundreds of years, thousands of years. (00:17:49) Almost all mathematicians were potentialists only and thought that it was incoherent to speak of an actual infinity at all. (00:17:59) 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. (00:18:14) And that (00:18:16) 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. (00:18:30) I mean, the Galileo paradox is the idea or the observation that if you think about the natural numbers, (00:18:37) I would start with 0, but I think maybe he would start with one, the numbers 1, 2, 3, 4, and so on. (00:18:43) And you think about which of those numbers are perfect squares. (00:18:47) So 0 squared is 0, and 1 squared is 1, and 2 squared is 4, 3 squared is 9, 16, 25, and so on. (00:18:55) And Galileo observed that the perfect squares can be put into a one-to-one correspondence with (00:19:03) all of the numbers. (00:19:04) I mean, we just did it. (00:19:06) I associated every number with its square. (00:19:09) 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. (00:19:22) And yet, there's all the gaps in between the perfect squares, right? (00:19:26) And this suggests that (00:19:30) 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? (00:19:39) 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? (00:19:50) And another example is if you take two line segments of different lengths, (00:19:56) And you can imagine drawing a kind of foliation, a fan of lines that connect them. (00:20:03) So the endpoints are matched from the shorter to the longer segment and the midpoints are matched and so on. (00:20:08) So spreading out the lines as you go. (00:20:10) And so every point on the shorter line would be associated with a unique, distinct point on the longer line in a one-to-one way. (00:20:20) 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. (00:20:29) And so it makes, again, a kind of confusion over ideas about infinity. (00:20:34) 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. (00:20:49) 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. (00:20:59) Now, 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. (00:21:08) And the way we would talk about it now is appeal to what I call the Cantor-Hume principle, or some people just call it Hume's principle, (00:21:16) 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. (00:21:32) 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 any two circles are equinumerous, and so on. (00:21:45) And 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 The Elements. (00:21:58) I mean, many times when he's calculating area and so on, he wants, it's a kind of basic idea that if something is just a part of another thing, then the whole is greater than the part. (00:22:10) And so what Galileo (00:22:13) was troubled by was this tension between what we call the Cantor-Hume principle and Euclid's principle. (00:22:22) And it really wasn't fully resolved, I think, until Cantor. (00:22:25) 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. (00:22:34) And so he exhibited (00:22:37) two different infinite sets and proved that they're not equinumerous. (00:22:41) They can't be put into one-to-one correspondence. (00:22:44) And it's traditional to talk about the uncountability of the real numbers. (00:22:48) So Cantor's big result was that the set of all real numbers is an uncountable set. (00:22:53) So 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. (00:23:02) Yeah, let's talk about the Hilbert's Hotel. (00:23:04) Hilbert's Hotel is a hotel with infinite (00:23:07) definitely many rooms. (00:23:08) each room is a full floor suite. (00:23:10) So there's floor zero. (00:23:12) I always start with 0 because for me, the natural numbers start with 0, although that's maybe a point of contention for some mathematicians. (00:23:19) The other mathematicians are wrong. (00:23:21) Like a bunch of J, I'm a programmer, so starting at 0 is a wonderful place to start. (00:23:24) Exactly. (00:23:26) So there's floor 0, floor 1, floor 2, or room 0, 1, 2, 3, and so on, just like the natural numbers. (00:23:31) So Hilbert's Hotel has a room for every natural number. (00:23:36) And it's completely full. (00:23:37) There's a person occupying room N for every N. (00:23:41) But meanwhile, a new guest comes up to the desk and wants a room. (00:23:45) Can I have a room, please? (00:23:46) And the manager says, hang on a second. (00:23:48) Just give me a moment. (00:23:50) And 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, you know, during the stay. (00:24:02) And so the manager (00:24:04) sent a message up to all the current occupants and told every person, hey, can you move up one room, please? (00:24:12) So the person in room 5 would move to room 6, and the person in room 6 would move to room 7, and so on, and everyone moved at the same time. (00:24:20) 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. (00:24:25) And (00:24:25) But when you move everyone up one room, then the bottom room, room 0, becomes available, of course, and so he can put the new guest in that room. (00:24:34) So even when you have infinitely many things, then the new guest can be accommodated. (00:24:39) And that's a way of showing how the particular infinity of the occupants of Hilbert's Hotel, it violates Euclid's principle. (00:24:48) I mean, it exactly illustrates this idea because (00:24:51) 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? (00:25:03) So to just say one more time, the hotel is full. (00:25:07) The hotel is full. (00:25:09) And then you could still squeeze in one more, and that breaks the... (00:25:15) traditional notion of mathematics and breaks people's brains about when they try to think about infinity, I suppose. (00:25:21) This is a property of infinity. (00:25:22) It's a property of infinity that sometimes when you add up an element to a set, it doesn't get larger. (00:25:29) That's what this example shows. (00:25:33) But one can go on with Hilbert's Hotel, for example. (00:25:36) I mean, maybe the next day, you know, 20 people show up all at once. (00:25:40) We can easily do the same trick again, just move everybody up 20 rooms. (00:25:44) And then we would have 20 empty rooms at the bottom and those new 20 guests could go in. (00:25:50) But on the following weekend, a giant bus pulled up, Hilbert's bus. (00:25:57) And Hilbert's bus has, of course, infinitely many seats. (00:26:00) There's seat 0, seat 1, seat 2, seat 3, and so on. (00:26:04) 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. (00:26:10) And so what is the manager going to do? (00:26:13) And when I talk about Hilbert's Hotel, when I teach Hilbert's Hotel in class, I always demand that the students provide the explanation of how to do it. (00:26:23) So maybe I'll ask you, can you tell me, what is your idea about how to fit them all in the hotel, everyone on the bus and also the current occupants? (00:26:33) You separate the hotel into even and odd rooms, and you squeeze in, then you help a bus people into the odd rooms, and the previous occupants go into the even rooms. (00:26:42) That's exactly right. (00:26:43) So, I mean, that's a very easy way to do it. (00:26:46) If you just tell all the current guests to double their room number, so in room N, you move to room 2 times N. (00:26:53) So they're all going to 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. (00:26:59) And so all the odd rooms become empty that way, and now we can put the bus occupants into the odd-numbered rooms. (00:27:05) And by doing so, you have now shoved in an infinity into another infinity. (00:27:10) That's right. (00:27:11) 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. (00:27:22) And a kind of easy way to understand what that's saying in terms of Hilbert's Hotel is that (00:27:27) A set is countable if it fits into Hilbert's Hotel, because Hilbert's Hotel basically is the set of natural numbers in terms of the room numbers. (00:27:34) So to be equinumerous with a set of natural numbers is just the same thing, is to fit into Hilbert's Hotel. (00:27:40) And so what we've shown is that if you have two countably infinite sets, then their union is also countably infinite. (00:27:49) 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 (00:27:56) only countably infinite. (00:27:57) It didn't get bigger. (00:27:59) And that's a remarkable property for a notion of infinity to have, I suppose. (00:28:05) 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. (00:28:13) 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. (00:28:19) So there's another way to push this a bit harder, and that is when Hilbert's train (00:28:25) arrives. (00:28:26) And Hilbert's train has infinitely many train cars. (00:28:31) And each train car has infinitely many seats. (00:28:36) And so we have an infinity of infinities of the train passengers together with the current occupants of the hotel. (00:28:44) And everybody on the train wants to check in to Hilbert's hotel. (00:28:49) So the manager can again, of course, send a message up to all the rooms. (00:28:54) telling every person to double their room number again. (00:28:58) And so that will occupy all the even-numbered rooms again, but free up again the odd-numbered rooms. (00:29:05) So somehow we want to put the train passengers into the odd-numbered rooms. (00:29:10) And so, well, every train passenger is on some car, let's say car C and seat S. (00:29:18) So somehow we have to take these two coordinates, you know, C, S, (00:29:23) car number and the seat number, and produce from it an odd number in a one-to-one way. (00:29:30) And that's actually not very difficult. (00:29:33) 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. (00:29:44) 3 to the C. (00:29:45) 3 to the car number. (00:29:47) So 3 * 3 * 3, (00:29:49) the number of the car. (00:29:50) 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. (00:29:59) So 3 to the C times 5 to the S. (00:30:03) That's always an odd number because the prime factorization has only threes and fives in it. (00:30:08) There's no two there. (00:30:10) So therefore, it's definitely an odd number. (00:30:13) And it's always different because of the uniqueness of prime factorization. (00:30:18) So every number can be factored uniquely into prime. (00:30:21) So if you have a number of that form, then you can just factor it and that tells you the exponent on three and the exponent on five. (00:30:29) And so exactly which person it was, which car they came from and which seat they came from. (00:30:33) And prime factorization is every single number can be (00:30:38) decomposed into the atoms of mathematics, which is the prime numbers. (00:30:43) You can multiply them together to achieve that number. (00:30:45) And that's prime factorization. (00:30:47) You're showing three and five are both prime numbers, odd. (00:30:53) So through this magical formula, you can deal with this train, infinite number of cars with each car having infinite number of seats. (00:31:04) Exactly right. (00:31:05) We've proved that (00:31:06) 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. (00:31:16) Because the train cars are each countable. (00:31:18) Plus the current hotel, it's sort of like another train car, if you want to think about it that way. (00:31:22) The current occupants of the hotel could have the same number as any of the train cars. (00:31:28) So putting countably many countable sets together to make one big union set is still countable. (00:31:35) It's quite remarkable, I think. (00:31:37) I mean, when I first learned this many, many years ago, I was completely shocked by it and transfixed by it. (00:31:43) 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. (00:31:54) which is a strong instance, a strong violation of Euclid's principle once again, right? (00:32:00) So the new set that we built 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. (00:32:16) Have you been able to sort of internalize a good intuition about countable infinity? (00:32:22) Because that is a pretty weird thing. (00:32:25) 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. (00:32:34) Yeah, that's exactly right. (00:32:35) I mean, I guess, of course, when you work with these notions that the argument of Hilbert's Hortel becomes kind of clear, there's many, many other ways to talk about it too. (00:32:47) For example, (00:32:49) 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. (00:33:01) So there's the, you know, row zero, row one, row two, and so on, column zero, column one, column two, and so on. (00:33:05) And each row and column has a countable infinity of points on it, right? (00:33:13) So those dots, if you think about them as dots, (00:33:17) are really the same as the train cars. (00:33:18) If you think about each column in that integer lattice, it's a countable infinity. (00:33:24) It's like 1 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. (00:33:31) 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. (00:33:41) diagonals winding back and forth. (00:33:44) 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. (00:33:56) 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. (00:34:08) And that gives a correspondence between the grid points and the natural numbers themselves. (00:34:14) So it's a kind of different picture. (00:34:15) I mean, before we use this 3 to this C, 5 times 5 to the S, which is a kind of overly arismatic 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. (00:34:33) And as long as you give each of the infinite collections a chance, (00:34:37) to add one more person to the list, then you're going to accommodate everyone in any of the sets in one list. (00:34:43) Yeah, it's a really nice visual way to think about it. (00:34:45) You just zigzag your way across the grid to make sure everybody's included. (00:34:50) That gives you kind of an algorithm for including everybody. (00:34:53) So can you speak to the uncountable infinities? (00:34:56) So what are the integers and the real numbers and what is the line that Cantor was able to find? (00:35:01) So maybe there's one more step I want to insert before doing that, which is (00:35:07) the rational numbers. (00:35:08) So we did pairs of natural numbers, right? (00:35:13) That's the train car, basically. (00:35:15) 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 (00:35:30) are densely ordered between any two fractions, you can find another fraction, right? (00:35:34) The average of two fractions is another fraction. (00:35:38) And so sometimes people, it seems to be a different character than the integers, which are discretely ordered, right? (00:35:47) From any integer, there's a next one and a previous one and so on, but that's not true in the rational numbers. (00:35:53) And yet, the rational numbers are also still only a countable infinity. (00:35:58) 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. (00:36:11) And so if I tell you 2 natural numbers, then you know what fraction I'm talking about. (00:36:17) I mean, plus the sign issue. (00:36:19) I mean, if it's positive or negative. (00:36:20) But if you just think about the positive fractions, then (00:36:24) you have the numbers of the form p / q, where q is not zero. (00:36:27) So you can still do 3 to the p * 5 to the q. (00:36:32) The same idea works with the rational numbers. (00:36:35) So this is still a countable set. (00:36:38) And you might think, well, every set is going to be countable because there's only one infinity. (00:36:44) I mean, if that's a kind of perspective, maybe that you're (00:36:48) adopting, but it's not true. (00:36:49) And that's the profound achievement that Cantor made is proving that the set of real numbers is not a countable infinity. (00:36:55) It's A strictly larger infinity, and therefore there's more than one concept of infinity, more than one size of infinity. (00:37:03) So let's talk about the real numbers. (00:37:04) What are the real numbers? (00:37:05) Why do they break infinity, the countable infinity? (00:37:09) Looking it up on perplexity, (00:37:12) Real numbers include all the numbers that can be represented on the number line, encompassing both rational and irrational numbers. (00:37:18) We've spoken about rational numbers, and the rational numbers, by the way, by definition, the numbers that can be represented as a fraction of two integers. (00:37:28) That's right. (00:37:28) So with the real numbers, we have the algebraic numbers. (00:37:32) We have, of course, all the rational numbers. (00:37:34) 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. (00:37:40) or the cube root of 5 and so on, numbers that solve an algebraic equation over the integers, those are known as algebraic numbers. (00:37:48) It was an open question for a long time whether that was all of the... (00:37:53) real numbers or whether they would exist numbers that are the transcendental numbers. (00:37:58) The transcendental numbers are real numbers that are not algebraic. (00:38:01) And we won't even go to the surreal numbers about whichever wonderful blog post. (00:38:05) We'll talk about that a little bit later. (00:38:06) Oh, great. (00:38:07) So it was Louisville who first proved that there are transcendental numbers and he exhibited a very specific number that's now known as the Louisville constant. (00:38:17) which is a transcendental number. (00:38:19) Cantor also famously proved that there are many, many transcendental numbers. (00:38:24) In fact, it follows from his argument on the uncountability of the real numbers that there are uncountably many transcendental numbers. (00:38:31) So most real numbers are transcendental. (00:38:35) And again, going to perplexity, transcendental numbers are real or complex numbers. (00:38:39) They're not the root of any non-zero polynomial with integer or rational coefficients. (00:38:44) This means (00:38:45) They cannot be expressed as solutions to algebraic equations with integer coefficients, setting them apart from algebraic numbers. (00:38:52) That's right. (00:38:54) So some of the famous transcendental numbers would include the number pi, you know, the 3.14159265, and so on. (00:39:03) So that's a transcendental number. (00:39:05) Also, Euler's constant, the E, like E to the X, the exponential function. (00:39:10) So you could say that some of the sexiest numbers in mathematics are all transcendental numbers. (00:39:15) Absolutely, that's true. (00:39:17) Although, you know, I don't know, the square root of 2 is pretty. (00:39:19) Square root. (00:39:20) So it depends. (00:39:20) Let's not. (00:39:22) Beauty can be found in all the different kinds of sets. (00:39:25) And if you have a kind of simplicity attitude, then, you know, zero and one are looking pretty good too. (00:39:29) So, and they're definitely not. (00:39:30) Sorry to take that tangent, but what is your favorite number? (00:39:33) Do you have one? (00:39:34) gosh, Is it zero? (00:39:36) Did you know there's a proof that every number is interesting? (00:39:42) You can prove it because... (00:39:44) Yeah, what's that proof look like? (00:39:46) How do you even begin? (00:39:47) I'm going to prove to you that every natural number is interesting. (00:39:51) Okay. (00:39:52) I mean, zero is interesting because it's the additive identity, right? (00:39:55) That's pretty interesting. (00:39:57) And one is the multiplicative identity. (00:39:58) So when you multiply it by any other (00:40:00) a number, you just get that number back, right? (00:40:03) And 2 is, the first prime number that's super interesting, right? (00:40:08) And okay, so one can go on this way and give specific reasons, but I want to prove as a general principle that every number is interesting. (00:40:16) And this is the proof. (00:40:19) Suppose toward contradiction that there were some boring numbers. (00:40:25) Okay. (00:40:27) But if there was an uninteresting number, then there would have to be a smallest uninteresting number. (00:40:34) Yes. (00:40:36) But that's a contradiction because the smallest uninteresting number is a super interesting property to have. (00:40:44) So therefore, there cannot be any boring numbers. (00:40:49) I'm going to have to try to find a hole in that proof. (00:40:52) Because there's a lot of baked in in the word interesting. (00:40:54) But yeah, that's a beautiful, that's beautiful. (00:40:57) That doesn't say anything about the transcendental numbers, about the real numbers. (00:41:00) You use proof from just for natural numbers. (00:41:02) Okay, so should we get back to Cantor's argument? (00:41:05) Sure, you've masterfully avoided the question. (00:41:08) You basically said, I love all numbers. (00:41:10) Yeah, basically. (00:41:11) That's what my. (00:41:12) Back to Cantor's argument. (00:41:14) Let's go. (00:41:14) Okay, so Cantor wants to prove that the (00:41:19) infinity of the real numbers is different and strictly larger than the infinity of the natural numbers. (00:41:25) So the natural numbers are the numbers that start with 0 and add 1 successively, so 0, 1, 2, 3, and so on. (00:41:32) 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. (00:41:44) 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. (00:41:53) And so the claim that we want to prove is that it's strictly larger. (00:41:58) So suppose that it wasn't strictly larger. (00:42:02) So then they would have the same size. (00:42:05) But to have the same size, remember, means, by definition, that there's a one-to-one correspondence between them. (00:42:13) So we suppose that the real numbers can be put into one-to-one correspondence with the natural numbers. (00:42:20) So therefore, for every natural number n, we have a real number, let's call it R sub n. (00:42:26) R sub n is the nth real number on the list. (00:42:28) Basically, our assumption allows us to think of the real numbers as having been placed on a list, R1, R2, and so on. (00:42:36) Okay, and now I'm going to define the number z, and it's going to be (00:42:40) the integer part is going to be a 0, and then I'm going to put a decimal place, and then I'm going to start specifying the digits of this number Z. (00:42:48) D1, D2, D3, and so on. (00:42:51) 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. (00:43:03) Okay, so to specify the nth digit of Z, (00:43:06) I go to the nth number on the list, r sub n, and I look at its nth digit after the decimal point. (00:43:13) And whatever that digit is, I make sure that my digit is different from it. (00:43:18) Okay. (00:43:19) 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 0 or 9. (00:43:29) I'm just always using the other digits and not 0 or 9. (00:43:33) There's a certain technical reason to do that. (00:43:37) But the main thing is that I make the digits of Z different in the nth place from the nth digit of the nth number. (00:43:46) If you had drawn out the numbers on the original list, R1, R2, R3, and so on, and you made it, you know, and they were each filling a whole row, and you thought about the nth digit of the nth number, (00:43:59) It would form a kind of diagonal going down and to the right. (00:44:03) And for that reason, this argument is called a diagonal argument because we're looking at the nth digit of the nth number and those exist on a kind of diagonal going down. (00:44:13) And we've made our number Z so that the nth digit of Z is different from the nth digit of the nth number. (00:44:21) But now it follows that Z is not on the list because (00:44:27) 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. (00:44:37) That's exactly how we built it. (00:44:39) And the 2nd digit of Z is different from the 2nd digit of R2 and so on. (00:44:44) The nth digit of Z is different from the nth digit of R sub n for every n. (00:44:49) So therefore, Z is not equal to any of these numbers R sub n. (00:44:53) And (00:44:55) 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? (00:45:04) And so that's the main contradiction. (00:45:06) And so it's a kind of proof by construction. (00:45:08) Exactly. (00:45:08) 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. (00:45:23) 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. (00:45:33) 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. (00:45:46) For example, the number one, you can write it as 1.0000 forever, but you can also write it (00:45:53) as 0.999 forever. (00:45:56) Those are two different decimal representations of exactly the same number. (00:46:01) You beautifully got rid of the zeros and the nines, therefore we don't need to even consider that, and the proof still works. (00:46:07) Exactly. (00:46:07) Because the only kind of case where that phenomenon occurs is when the number is eventually 0 or eventually 9. (00:46:13) And so since our number Z never had any zeros or nines in it, wasn't one of those numbers. (00:46:19) And so actually, in those cases, we didn't need to do anything special. (00:46:22) to diagonalize, just the mere fact that our number has a unique representation already means that it's not equal to those numbers. (00:46:29) 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. (00:46:47) And (00:46:48) this diagonalization idea has proved to be an extremely fruitful proof method. (00:46:54) And almost every major result in mathematical logic is using in an abstract way the idea of diagonalization. (00:47:02) It was really the start of so many other observations that were made, including (00:47:09) Russell's paradox and the halting problem and the recursion theorem and so many other principles are using diagonalization at their core. (00:47:19) Can we just step back a little bit? (00:47:21) This infinity crisis led to a kind of rebuilding of mathematics. (00:47:27) So it would be nice if you lay out (00:47:30) the things it resulted in. (00:47:32) So one is set theory became the foundation of mathematics. (00:47:35) All mathematics could now be built from sets, giving math its first truly rigorous foundation. (00:47:41) The axiomatization of mathematics, the paradoxes forced mathematicians to develop ZFC and other axiomatic systems, and mathematical logic emerged. (00:47:52) Gerdel, Turing, and others created entire new fields. (00:47:56) So can you explain what set theory is? (00:48:00) and how does it serve as a foundation of modern mathematics and maybe even the foundation of truth? (00:48:05) That's a great question. (00:48:07) Set theory really has two roles that it's serving. (00:48:13) There's kind of two ways that set theory emerges. (00:48:17) On the one hand, set theory is its own subject of mathematics with its own problems and questions and answers and proof methods. (00:48:27) And so, (00:48:28) really, from this point of view, set theory is about the transfounded recursive constructions or well-founded definitions and constructions. (00:48:39) And those ideas have been enormously fruitful and set theorists have looked into them and developed so many ideas coming out of that. (00:48:48) But set theory has also happened to serve (00:48:51) 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. (00:49:01) It's its own subject, but it's also serving as a foundation of mathematics. (00:49:05) So in its foundational role, set theory provides a way to think of a collection of things as one thing. (00:49:11) That's the central idea of set theory. (00:49:14) A set is a collection of things, (00:49:18) but you think of the set itself as one abstract thing. (00:49:21) So when you form the set of real numbers, then that is a set. (00:49:25) It's one thing, it's a set, and it has elements inside of it. (00:49:29) So it's sort of like a bag of objects. (00:49:32) A set is kind of like a bag of objects. (00:49:33) 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. (00:49:43) And axioms are, I guess, facts that we (00:49:48) assume are true based on which we then build the ideas of mathematics. (00:49:52) So there's a bunch of facts, axioms about sets that we can put together. (00:49:58) And if they're sufficiently powerful, we can then build on top of that a lot of really interesting mathematics. (00:50:05) Yeah, I think that's right. (00:50:06) So I mean, the history of how of the current set theory axioms known as the Zermelo-Franco axioms, (00:50:12) came out in the early 20th century with Zermelo's idea. (00:50:16) 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-ordered principle. (00:50:29) So he described his proof, and that was extremely controversial at the time. (00:50:34) And there was no theory, there weren't any axioms there. (00:50:37) Cantor was not working in an axiomatic framework. (00:50:39) He didn't have a list of axioms in the way that we have for set theory now. (00:50:44) And Zermelo didn't either. (00:50:46) And his ideas were challenged so much with regard to the well-ordered theorem that he was pressed to produce the theory in which his argument could be formalized. (00:50:59) And that was the origin of what's known as Zermelo set theory. (00:51:02) In 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 choice is given. (00:51:16) 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. (00:51:30) So this was controversial and this was described before there's even a language for axiomatic systems. (00:51:37) That's right. (00:51:38) So on the one hand, I mean, the axiom choice principle is completely obvious that we want this to be true, that it is true. (00:51:47) I mean, a lot of people take it as a law of logic. (00:51:50) If you have a bunch of sets, then (00:51:53) there's a way of picking an element from each of them. (00:51:57) There's a function. (00:51:58) 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. (00:52:06) It's a completely natural principle. (00:52:09) I mean, it's called the XMO choice, which is a way of sort of anthropomorphizing the mathematical idea. (00:52:15) It's not like the function is choosing something. (00:52:17) I mean, (00:52:18) It's just that if you were to make such choices, there would be a function that consisted of the choices that you made. (00:52:24) And the difficulty is that when you can't specify a rule or a procedure by which you're making choices, then it's difficult to say what the function is that you're asserting exists. (00:52:39) You want to have the view that, well, there is a way of choosing. (00:52:42) I don't have an easy way to say what the function is. (00:52:47) But there definitely is one. (00:52:48) This is the way of thinking about the axiom of choice. (00:52:51) So we're going to say the three letters of ZFC may be a lot in this conversation. (00:52:55) You already mentioned Zamila-Frankel set theory, that's the Z and the F and the C in that is this comes from this axiom of choice. (00:53:04) That's right. (00:53:05) So ZFC sounds like a super technical thing, but it is the set of axioms that's the foundation of modern mathematics. (00:53:12) Yeah, absolutely. (00:53:13) So one should be aware also that there's huge parts of mathematics that don't, that pay attention to whether the axon of choice is being used and they don't want to use the axon of choice or they work out the consequences that are possible without the axon of choice or with weakened forms of Summelo-Frenkel set theory and so on. (00:53:31) And that's quite a, there's quite a vibrant amount of work in that area. (00:53:35) I mean, but going back to the axon of choice for a bit, it's maybe interesting to (00:53:41) to give Russell's description of how to think about the axiom of choice. (00:53:45) So Russell describes this rich person who has an infinite closet. (00:53:53) And in that closet, he has infinitely many pairs of shoes. (00:53:59) And he tells his butler to please go and give me one shoe from each pair. (00:54:06) And the butler can do this easily because he can, for any pair of shoes, he can just always pick the left shoe. (00:54:14) I mean, there's a way of picking that we can describe. (00:54:17) 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. (00:54:28) So we can describe explicit choice functions. (00:54:32) And for those cases, you don't need the axiom of choice to know that there's a choice function. (00:54:37) 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 function. (00:54:46) But the problematic case occurs when you think about the infinite collection of socks that the person has in their closet. (00:54:55) And if we assume that socks are sort of indistinguishable within each pair, you know, they match each other, but they're sort of, you know, indiscernible, then (00:55:02) the butler wouldn't have any kind of rule for which sock in each pair to pick. (00:55:10) And so it's not so clear that he has a way 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. (00:55:29) that defines the choice function or whether there's sort of this arbitrary choosing aspect to it. (00:55:35) That's when you need the axiom of choice to know that there is such a function. (00:55:39) 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 sox has to be defined by a rule. (00:55:51) Why should everything that exists in mathematical reality follow a rule or a procedure (00:55:57) of that sort. (00:55:58) If I have the idea that my mathematical ontology is rich with objects, then I think that there are all kinds of functions and ways of choosing. (00:56:08) Those are all part of the mathematical reality that I want to be talking about. (00:56:12) And so I don't have any problem asserting the axon of choice. (00:56:16) Yes, there is a way of choosing. (00:56:19) But I can't necessarily tell you what it is. (00:56:22) But in a mathematical argument, I can assume that I fix the choice function because I know that there is one. (00:56:28) So it's the philosophical. (00:56:30) 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. (00:56:38) 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 going to be constructive. (00:56:48) You're not going to be able to necessarily say specific things about them. (00:56:53) But if you're just claiming to make an existence claim, that's totally fine. (00:56:56) Whereas if you have a constructive attitude about the nature of mathematics, (00:57:00) 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 going to want to deny the axiom of choice and maybe much more. (00:57:14) Can we maybe speak to the axioms that underlie ESC? (00:57:19) So going to perplexities, ESC, or as a Melo-Frankel said theory with the axiom of choice, as we mentioned, is the standard foundation for most modern mathematics. (00:57:27) It consists of the following main axioms. (00:57:29) Axiom of extensionality, Axiom of anti-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. (00:57:44) Some of these are quite basic, but it would be nice to kind of give people a sense of what it means to be an axiom, like what kind of basic (00:57:56) facts we can lay on the table on which we can build some beautiful mathematics. (00:58:00) Yeah, so the history of it is really quite fascinating. (00:58:02) 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 exponent choice to the well-ordered principle, which was an extremely controversial result. (00:58:15) So in 1904, he gave the proof without the theory, and then it was challenged to provide the theory. (00:58:21) And so in 1908, (00:58:22) He produced the Zermelo set theory and gave the proof that in that theory you can prove that every set admits a well ordering. (00:58:32) 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. (00:58:42) So for example, extensionality says if two sets have the same members, then they're equal. (00:58:48) So it's this idea that (00:58:51) The sets consist of the collection of their members, and that's it. (00:58:54) There's nothing else that's going on in this set. (00:58:57) So it's just, if two sets have the same members, then they are the same set. (00:59:01) So it's maybe the most primitive axiom in some respect. (00:59:07) Well, there's also, just to give a flavor, there exists a set with no elements called the empty set. (00:59:14) For any two sets, there's a set that contains exactly those two sets as elements. (00:59:19) For any set, there's a set that contains exactly the elements of the elements of that set, so the union set. (00:59:25) And then there's the power set. (00:59:26) For any set, there's a set whose elements are exactly the subsets of the original set, the power set. (00:59:33) 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. (00:59:42) Back to our hotel example. (00:59:45) That's right. (00:59:46) And there's more. (00:59:48) It's kind of fascinating. (00:59:49) I used to put yourself in the mindset of people at the beginning of this, of trying to formalize set theory. (00:59:57) It's fascinating that humans can do that. (01:00:00) I read some historical accounts by historians about that time period, specifically about Zermella's axioms and his proof of the well-ordered theorem. (01:00:09) And the historians were saying, (01:00:14) Never before in the history of mathematics has a mathematical theorem been argued about so publicly and so vociferously as that theorem of Sermelos. (01:00:27) And it's fascinating also because the axiom of choice was widely regarded as a kind of basic principle at first, but people were very suspicious of the well-ordered theorem because no one could imagine a well-ordering, say, of the real numbers. (01:00:42) And so this was a case when Zermelo seemed to be, from principles that seemed quite reasonable, proving this obvious untruth. (01:00:51) And so people were, mathematicians were objecting. (01:00:54) 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 (01:01:07) 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. (01:01:19) 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. (01:01:26) That's true now even. (01:01:28) People like to pay attention to when the axiom of choice is used or not used in mathematical arguments, I mean, up until this day. (01:01:35) It used to be more important. (01:01:36) In the early 20th century, it was very important because people didn't know if it was a consistent theory or not. (01:01:41) And there were these antinomies arising. (01:01:43) And so there was a worry about consistency of the axioms. (01:01:47) But then, of course, eventually, with the result of Gerdel and Cohen and so on, this consistency question specifically about the axiom of choice. (01:01:56) sort of falls away, we know that the axiom of choice itself will never be the source of inconsistency in set theory. (01:02:04) If there's inconsistency with the axiom of choice, then it's already inconsistent without the axiom of choice. (01:02:08) So it's not the cause of inconsistency. (01:02:12) And so 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. (01:02:19) But still there's this reason to pay attention to it on the grounds of these constructivist ideas that I had mentioned earlier. (01:02:28) And we should say in set theory, consistency means that it is impossible to derive a contradiction from the axioms of the theory. (01:02:34) So means that there's no contradictions. (01:02:38) That's a consistent axiomatic systems that there's no contradictions. (01:02:42) A consistent theory is one for which you cannot prove a contradiction from that theory. (01:02:46) Maybe a quick pause, quick break, quick bathroom break. (01:02:51) You mentioned to me offline, we were talking about Russell's paradox and that there's a nice, another kind of anthropomorphizable proof of uncountability. (01:03:02) I was wondering if you can lay that out. (01:03:03) Oh yeah, sure, absolutely. (01:03:05) Both Russell's paradox and the proof. (01:03:07) Right. (01:03:08) So let's, so we, (01:03:10) We talked about Cantor's proof that the real numbers, the set of real numbers, is an uncountable infinity. (01:03:16) It's a strictly larger infinity than the natural numbers. (01:03:19) But Cantor actually proved a much more general fact, namely that for any set whatsoever, the power set of that set is a strictly larger set. (01:03:31) So the power set is the set containing all the subsets of the original set. (01:03:36) So if you have a set, (01:03:37) and you look at the collection of all of its subsets, then Cantor proves that this is a bigger set. (01:03:44) They're not equinumerous. (01:03:46) Of course, there's always at least as many subsets as elements because for any element you can make the singleton subset that has only that guy as a member, right? (01:03:56) So there's always at least as many subsets as elements. (01:03:59) But the question is whether it's strictly more or not. (01:04:04) And so Cantor reasoned like this. (01:04:06) It's very simple. (01:04:07) It's a kind of distilling the abstract diagonalization idea without encumbered by the complexity of the real numbers. (01:04:16) So we have a set X, and we're looking at all of its subsets. (01:04:20) That's the power set of X. (01:04:22) Suppose that X and the power set of X have the same size. (01:04:27) Suppose to its contradiction, they have the same size. (01:04:30) So that means we can associate to every individual of X a subset. (01:04:37) And so now let me define a new set. (01:04:40) I mean, another set. (01:04:41) I'm going to define it. (01:04:41) Let's call it D. (01:04:43) And D is the subset of X that contains all the individuals that are not in their set. (01:04:51) Every individual was associated with a subset of X. (01:04:55) And I'm looking at the individuals that are not in their set. (01:05:00) Maybe nobody's like that. (01:05:01) Maybe there's no element of X that's like that. (01:05:03) Or maybe they're all like that. (01:05:04) Or maybe some of them are and some of them aren't. (01:05:06) It doesn't really matter for the argument. (01:05:09) I defined a subset D consisting of the individuals that are not in the set that's attached to them. (01:05:16) But that's a perfectly good subset. (01:05:17) And so because of the equinumerosity, it would have to be attached to a particular individual. (01:05:25) But let's call that person (01:05:28) it should be a name starting with D, so Diana. (01:05:33) And now we ask, is Diana an element of D or not? (01:05:38) But if Diana is an element of D, then she is in her set. (01:05:43) So she shouldn't be, because the set D was the set of individuals that are not in their set. (01:05:50) So if Diana is in D, then she shouldn't be. (01:05:53) But if she isn't in D, then she wouldn't be in her set, and so she should be in D. (01:05:58) That's a contradiction. (01:06:00) So therefore, the number of subsets is always greater than the number of elements for any set. (01:06:08) And the anthropomorphizing idea is the following. (01:06:12) I'd like to talk about it this way. (01:06:14) For any collection of people, you can form more committees from them than there are people. (01:06:23) even if you have infinitely many people. (01:06:26) Suppose you have an infinite set of people. (01:06:29) And what's a committee? (01:06:30) Well, a committee is just a list of who's on the committee, basically, the members of the committee. (01:06:34) 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. (01:06:43) The best committee is the empty committee with no members and never meets and so on. (01:06:49) Or is the empty committee meeting all the time? (01:06:51) I'm not sure. (01:06:52) Yeah, wow, that's a profound question. (01:06:54) And does a committee with just one member meet also? (01:06:58) Yeah, maybe it's always in session. (01:07:00) I don't know. (01:07:00) Yeah. (01:07:01) So the claim is that there's more committees than people. (01:07:07) Okay, suppose not. (01:07:09) Well, then we could make an association between the people and the committees. (01:07:12) So we would have a kind of, every committee could be named after a person in a one-to-one way. (01:07:19) 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. (01:07:27) 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. (01:07:39) Okay, maybe that's everyone, maybe it's no one, maybe it's half the people, it doesn't matter. (01:07:44) That's a committee, it's a set of people. (01:07:48) And so it has to be named after someone. (01:07:51) Let's call that person Daniela. (01:07:54) So now we ask, is Daniela on the committee that's named after her? (01:08:00) Well, if she is, then she shouldn't be because it was the committee of people who aren't on their own committee. (01:08:08) And if she isn't, then she should be. (01:08:10) So again, it's a contradiction. (01:08:12) So when I was teaching in Oxford, one of my students (01:08:17) came up with the following different anthropomorphization of Kant's argument. (01:08:23) Let's consider all possible fruit salads. (01:08:27) We have a given collection of fruits, you know, apples and oranges and grapes, whatever. (01:08:32) And a fruit salad consists of some collection of those fruits. (01:08:35) So there's the banana, pear, grape salad, and so on. (01:08:38) There's a lot of different kinds of salad. (01:08:40) Every set of fruits makes a salad, a fruit salad. (01:08:44) Okay. (01:08:45) 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. (01:09:01) So if not, then you can put a one-to-one correspondence between the fruits and the fruit salads. (01:09:06) So you could name every fruit salad after a fruit. (01:09:10) Might not be, that fruit might not be in that salad. (01:09:12) It doesn't matter. (01:09:13) We're just, it's a naming, a one-to-one correspondence. (01:09:16) 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. (01:09:26) And that's a perfectly good salad. (01:09:30) 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. (01:09:40) So that diagonal salad would have to be named after some fruit. (01:09:44) So let's suppose it's named after durian, meaning that it was associated with durian in the one-to-one correspondence. (01:09:50) And then we ask, well, is durian (01:09:54) in the salad that it's named after. (01:09:56) And if it is, then it shouldn't be. (01:09:59) And if it isn't, then it should be. (01:10:00) And so it's, again, the same contradiction. (01:10:02) 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. (01:10:11) 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. (01:10:23) Because if it were, then we could form the set of all sets that are not elements of themselves. (01:10:32) So basically, what Russell is proving is that there are more collections of sets than elements. (01:10:40) Because we can form the diagonal class, the class of all sets that are not elements of themselves. (01:10:46) If that were a set, (01:10:48) then it would be an element of itself if and only if it was not an element of itself. (01:10:53) It's exactly the same logic in all four of those arguments. (01:10:57) 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. (01:11:04) But that set would be an element of itself if and only if it's not an element of itself, which is a contradiction. (01:11:10) So this is the essence of the Russell paradox. (01:11:13) I don't call it the Russell paradox. (01:11:15) Actually, when I teach it, I call it Russell's theorem. (01:11:17) There's no universal set. (01:11:20) And it's not really confusing anymore. (01:11:22) At the time, it was very confusing. (01:11:24) But now we've absorbed this nature of set theory into our fundamental understanding of how sets are, and it's not confusing anymore. (01:11:35) I mean, the history is fascinating, though, about the Russell paradox, because (01:11:40) 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. (01:11:53) So Frege wanted to give an account of all of mathematics in terms of logical notions. (01:11:59) And he was writing this monumental work and had formulated his basic principles. (01:12:05) And those principles happened to imply that (01:12:10) For any property whatsoever, you could form the set of objects with that property. (01:12:16) This is known as the general comprehension principle. (01:12:21) And he was appealing to the principles that support that axiom throughout his work. (01:12:28) I mean, it was really, it wasn't just an incidental thing. (01:12:31) He was really using this principle. (01:12:34) And Russell wrote him a letter when he observed the work in progress. (01:12:40) that there was this problem, because if you accept the principle that for any property whatsoever, you can make the set of objects with that property, then you could form the set of all sets that are not members of themselves. (01:12:51) That's just an instance of the general comprehension principle. (01:12:57) But 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. (01:13:09) And so Russell wrote this letter to Frege. (01:13:11) And it was just at the moment when Frege was finishing his work, it was already at the publishers and in press, basically. (01:13:19) But it's completely devastating. (01:13:21) I mean, it must have been such a horrible situation for Frege to be placed in because he's finished this monumental work, years of his life dedicated to this. (01:13:35) And Russell finds this (01:13:38) It's basically one line proof of a contradiction in the fundamental principles of the thesis that completely destroys the whole system. (01:13:49) And Frege had put in the appendix of his work a response to Russell's letter in which he explained what happened. (01:13:57) And he wrote very gracefully, hardly anything more unwelcome can befall a scientific rider than to have one of the foundations of his edifice shaken after the work is finished. (01:14:07) This is the position into which I was put by a letter from Mr. (01:14:09) Bertrand Russell as the printing of this volume was nearing completion. (01:14:13) And then he goes on to explain the matter, concerns his basic law file and so on. (01:14:17) It's heartbreaking. (01:14:17) 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. (01:14:30) 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. (01:14:39) What do you think about the Frege project, the philosophy of logic, the dream of the power of logic to construct the mathematical universe? (01:14:47) Of course, the project of logicism did not die with Frege, and it was continued. (01:14:53) And, you know, there's a whole movement, the neologicists and so on in contemporary times even, (01:14:58) 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. (01:15:11) I mean, when you view ZFC as the foundation of mathematics, and in my view, the principles of ZFC are fundamentally logical in character, including the axiom of choice, as I mentioned, as a principle of logic, (01:15:27) This is a highly disputed point of view, though, because a lot of people take even the axiom of infinity as mathematical, inherently mathematical and not logical and so on. (01:15:37) But I think if you adopt the view that the principles of ZFC have to do with the principles of abstract set formation, which is fundamentally logical in character, (01:15:49) then it's complete success for logicism. (01:15:51) So the fact that set theory is able to serve as a foundation means that mathematics can be founded on logic. (01:15:58) I think this is a good moment to talk about Gerdel's incompleteness theorems. (01:16:03) So can you explain them and what they teach us about the nature of mathematical truth? (01:16:10) Absolutely. (01:16:10) It's one of the most profound developments in mathematical logic. (01:16:14) I mean, the incompleteness theorems is when (01:16:17) mathematical logic, in my view, first became sophisticated. (01:16:22) It's a kind of birth of the subject of mathematical logic. (01:16:27) But to understand the theorems, you really have to start a little bit earlier with Hilbert's program. (01:16:33) Because at the 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 Borrelli-Forte paradox and so on. (01:16:43) And Hilbert was (01:16:45) famously supportive of set theory. (01:16:48) I mean, there's this quote of him saying, no one shall cast us from the paradise that Cantor has created for us. (01:16:57) 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. (01:17:10) And he didn't want to give that up. (01:17:12) Despite the danger of these (01:17:16) paradoxes, these contradictions basically is how some people viewed them. (01:17:20) And so. (01:17:21) This minefield of paradoxes. (01:17:23) Right, a minefield, that's a really good way of describing the situation. (01:17:26) And so Hilbert said, well, look, we have to fix this problem. (01:17:31) We want to use the set theory foundations, but we want to do it in a way that is trustworthy and reliable. (01:17:37) We can't allow that the foundations of mathematics are in question. (01:17:42) This is a kind of attitude I think that underlies. (01:17:45) was Hilbert and the Hilbert program. (01:17:48) 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. (01:17:58) But I mean, on the one hand, we want it to be as strong as possible. (01:18:03) We would like it to answer all the questions. (01:18:06) There's another famous quote of Hilbert in his retirement address where (01:18:11) He proclaims, 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. (01:18:29) We have all these problems we want to solve, and he is saying, we're going to do it. (01:18:32) We're going to solve all these problems. (01:18:34) So we want to propose this strong theory, and one has the sense that he had in mind set theory. (01:18:41) in which all the questions are going to be answered. (01:18:44) 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. (01:19:00) 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 the proof, (01:19:10) What is the nature of mathematical reasoning? (01:19:13) And on Hilbert's way of thinking about this, a proof is basically itself a finitistic kind of object. (01:19:22) 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. (01:19:35) And this is a formalist way of understanding the nature of proof. (01:19:39) So we think about a proof in a kind of syntactic, formal way. (01:19:43) Even though the contents of those statements might be referring to infinite, uncountable objects, the statements themselves are not infinite, uncountable objects. (01:19:53) The statements themselves are just finite sequences of symbols. (01:19:56) So we kind of think of proof as, maybe it's hard to say, almost like an outsider.