▶︎ 0:00 We've been talking about the countably infinite. A set is countable if it can be placed into one-to-one correspondence with a set of natural numbers. One way to understand it is that a set is countable when it fits in Hilbert's Hotel, because the room assignment number gives you the one-to-one correspondence with the set of natural numbers. Every finite set, of course, is countable, but also we have the countably infinite sets, which can be placed into one-to-one correspondence with the entirety of the natural numbers.
▶︎ 0:27 In a previous lecture, we saw many instances of countable sets. The natural numbers themselves, of course, are countable, but the integers are countable, as are the rational numbers, those are also countable. We saw how the union of two countably infinite sets is still countable. In fact, the union of countably many countable sets is still countable. This is like when Hilbert's bus pulls up to Hilbert's Hotel, we can put all of the previous hotel occupants together with the bus passengers into the hotel together and everyone has their own room.
▶︎ 0:58 And also, when Hilbert's train pulls up with infinitely many train cars, each car holding infinitely many passengers, we can fit them all into Hilbert's Hotel. We saw that the number of words, of finite words in a countable alphabet, the set of finite sequences of symbols from that alphabet, still forms a countable set. Well, maybe one thinks that every set is countable, perhaps it's not unreasonable to expect maybe that there is only one size of infinity, and it's the countable infinity. And so maybe this word countable just means infinite.
▶︎ 1:35 But in fact, Cantor discovered that this is not true, and what he proved is that the set of real numbers, the set of points on the number line is an uncountable infinity. And so when Cantor's cruise ship pulls up to Hilbert's Hotel, which has a passenger with a ticket having a serial number which is a real number and one passenger for every real number, then we cannot put the passengers of Cantor's cruise ship into Hilbert's Hotel. The set of real numbers is an uncountable infinity.
▶︎ 2:04 It's really a profound achievement, because what it shows for the first time is that there are different sizes of infinity. Cantor proves that there are different sizes of infinity with this argument, and that's what I'd like to show you today. So what he's saying is that the infinity of the natural numbers is a strictly smaller infinity than the infinity of the real numbers.
▶︎ 2:28 Cantor's ideas were controversial in his day, and actually in his era, they met with some stubborn rejection, but eventually they came to be accepted completely by all of mathematics. And Hilbert famously said, "Let no one cast us from the paradise that Cantor has created for us." Cantor's ideas were so robust and so fulfilling as a foundation of mathematics that Hilbert recognized how important this achievement was.
▶︎ 2:55 And so let's get into the argument, and I wanna tell you that the real numbers form an uncountable infinity. So the central claim is that the reals are an uncountable infinity, and what that means is that you cannot make a one-to-one correspondence between the real numbers and the set of natural numbers. If we wanna show that having such a correspondence is impossible, then we can do so by using proof by contradiction. What we're gonna do for the first step of the proof is suppose toward contradiction that the real numbers are a countable set.
▶︎ 3:30 If the real numbers were a countable set, then we could make such a correspondence. We could fit them into Hilbert's Hotel, or in other words, we could make a list of all the real numbers. We would have a list R1, R2, R3, R4, and so on, using an index for each, say positive integer here. So each of these would be a real number, and we're supposing towards contradiction that we have put every real number on this list.
▶︎ 3:59 And now what we're gonna do is think about this situation. We have this list of numbers, this list of real numbers, and what we're gonna do is define another number. I'm gonna call it Z. And Z is gonna be specified by its digits. The number Z that I'm gonna define in terms of this list is gonna have the form zero point, and then it's gonna have a digit D1, D2, D3, D4, and so on. So these will be the decimal digits of the number that I'm defining by reference to this list.
▶︎ 4:33 And the thing that I'm gonna do when I'm defining this number Z is I'm going to make sure that the digit D1 is different from the first digit after the decimal point in the real number R1. And I'm gonna make sure that the digit D2 is different from the second digit after the decimal point in the real number R2, and so on. D3 will be different from the third digit of the third number on the list. D4 is going to be different from the fourth digit of the fourth number on the list and so on.
▶︎ 5:09 So maybe I can be a little bit more definite. I can say, let's always use the digit one, unless the corresponding digit in the number on the list is one, in which case I'll use seven, say, for example. There's many such ways to make it more definite, but the most important thing is that I want the Nth digit of this number Z to be different from the Nth digit of the Nth number on the list.
▶︎ 5:38 But why do I care? Why am I fussing so much about these digits and so on? The reason I care about that and the reason why that's an extremely good idea that Cantor had was the following fact. Precisely because we made D1 different from the first digit of R1, we know therefore that whatever happens after that, Z will not be the same number as R1. We already made it different in a certain way, and that's enough for it to be a different number.
▶︎ 6:08 Precisely because D2 is different from the second digit of R2, it follows that Z is not the same number as R2. And therefore, whatever else we do, we've already ensured by choosing D2 in that way to make sure that Z is not equal to R2. And similarly, by the choice of D3, we make sure that Z is different from R3 and by the choice of D4, Z is different from R4 and so on.
▶︎ 6:32 And so what we can conclude now if we think about it, is that the number Z is not R1, and it's not R2, and it's not R3, and so on. So the number Z is not on the list, but that's a contradiction because we had supposed that every real number is on this list.
▶︎ 6:50 So therefore, let's just sum it all up. We suppose toward contradiction that the set of real numbers is countable. That means that we can find a one-to-one correspondence between the real numbers and the natural numbers, and therefore we can put all the real numbers on a list. We can enumerate them, R1, R2, R3 and so on, and this is a list that supposedly contains under our assumption every real number.
▶︎ 7:14 And now, using that list, I define a number Z. And the number Z will consist of zero point and then a bunch of digits, decimal digits, and I make sure that the Nth digit is different from the Nth digit of the Nth number. So D1 is different from the first digit of R1, D2 is different from the second digit of R2, D3 is different from the third digit of R3 and so on. That will ensure that Z is not equal to R1 because they differ in the first digit. It's not equal to R2 because they differ in the second digit. It's not equal to R3 because they differ in the third digit, and so forth. It's not equal to any of those numbers.
▶︎ 7:49 That's a contradiction because we had supposed every number's on this list, and therefore the real numbers cannot be countable. So they are uncountable. The reals are an uncountable infinity.
▶︎ 8:00 Now, I want to talk about a few little subtle points about this argument actually, because there's a couple of issues that come up. So first of all, in the argument I was referring to the nth digit of r sub n, but actually there's this annoying thing, which is that real numbers don't always have a unique decimal representation, and so we're not actually entitled to refer to the third digit of a real number because maybe it has two different representations, and so that digit might be different depending on which representation you use.
▶︎ 8:32 So for example, there was this equation in another lecture that I mentioned, what I call the most controversial equation in middle school. And this is the equation, 1.000 and so on repeating is the same thing, the same real number as 0.999 repeating. These two decimal representations are the same real number. They represent the same real number, the number one. The number one can be written this way, 1.000 forever, but it can also be written 0.999 and so on. And so the number one has these two different decimal representations.
▶︎ 9:10 And so if I say, "Well, I have the number one, what's its third digit after the decimal place?" And you might want to say, "Well, it's zero, of course." Or you might want to say, "Well, it's nine, of course." So the point is that sometimes it happens that real numbers have more than one representation, and that's a kind of slight problem for the diagonal argument that we've described here. Because maybe I chose a digit that was different from one representation of the real number up here, but not different from the other representation, and so I haven't maybe actually ensured that it's different.
▶︎ 9:42 This kind of phenomenon can occur in other situations. For example, 2.35299999 is the same thing, if I just change all these nines to zeros and increase this digit by one, it would be the same as 2.353000 and so on. So in fact this eventually nines or eventually zero situation is the only time when real numbers have more than one representation, and so in particular, every real number has either one or two representations. And the only way it can have two representations is if it's ending in nines or zeros in those representations.
▶︎ 10:25 So there's only two possible representations that I have to make sure I'm different from, but I can still do that in my diagonal argument. For example, I can just make sure that I choose d1 to be different from the first digit after the decimal point in both of the representations if r1 happens to have two representations, and I make sure to choose d2 different from both of the second digits in the representations of r2 and so on. And in that way, I'll still ensure that z is a different real number because it has a digit that doesn't occur in any of the representations of that real number.
▶︎ 11:00 Another way to have solved that problem instead of the way I just described is, for example, if we do in fact always use ones and sevens for our digits in z, then z will have a unique representation because it's not going to be in this eventually nine or eventually zero case, because the real number z will always be ones and sevens, 0.11771771 and so on. And so therefore, z will have a unique representation, and so therefore it will be different from any rn that has more than one representation precisely because z has only one. So if rn has more than one, then they're not equal. So we don't need to worry about the case.
▶︎ 11:42 So this is this annoying subtle thing, and it's very easily handled in a variety of ways as I just described. Let me explain this
▶︎ 11:51 Argument again, I think it's really important. In fact, when I teach my infinity class at the University of Notre Dame, then I always describe the argument in many, many different ways. So I want to give you an example of how we would construct this z by making everything more concrete.
▶︎ 12:10 Let's suppose, for example, that we're given a very specific list of numbers. So maybe, let's see, what do I have here? So maybe r1 is the number of pi, and r2 is the number e, and r3 is the number, I don't know, square root of 2, and r4 is, what do I have on my list here? Log 2. So I could write out these digits, 3.14159265 and so on. And what is this? 2.718281828 and so on. And this is 1.414, what is it now? Oh my gosh, let's see. What is the square root of 2? I've got to look it up here. 41421356. And this is 0.69, what is it there? 3147.
▶︎ 13:07 When we assume that the real numbers are countable, we assume towards contradiction that the real numbers are countable and therefore they can be put on a list. Maybe that list of numbers would start with these numbers. We can't assume that it does, so this is just illustrating the argument. But for example, maybe this is the list of numbers that we have, and now I want to build the number z that arises from this list of numbers.
▶︎ 13:32 And if you recall, when we were defining the number z, we specified the digits, and we picked the first digit to be different from the first digit of the first number, which is a 1 here. And if we use this 1, 7 rule, then for example, we say we should always use a 1 unless the corresponding digit of rn is a 1, in which case we use a 7. So therefore the z that we would build for this sequence of numbers would start 0.7. And then the second digit of r2 in this case is also a 1 in this case, so we're going to start with two 7s here, because we want this digit to be different from the second digit of the second number. And then the third digit is going to be different from the third digit of the third number, which is this digit here. It's a 4, so we can use a 1. It's different. And then we go make it different from the fifth digit of the, I'm sorry, from the fourth digit of the fourth number, so this one, so we should use a 7 and so on.
▶︎ 14:36 What we've done here is we've specified each digit to be different from the corresponding nth digit of the nth number on the list. The nth digit is different from the nth number on the list. So this z, this number z that we built, because of this first 7, we can see immediately that it's different from pi. Of course, we already knew it was different from pi, because we started with a 0 and pi started with a 3. But this choice of the digit, regardless of what r1 was, we made it different by changing the first digit. And we made z different from r2 by making the second digit different and so on. So we can see that z is not equal to rn for any n. And that's a contradiction.
▶︎ 15:29 So therefore, the assumption that the reals are countable must have been wrong. When you do a proof by contradiction, you're trying to prove something. In our case, we're trying to prove that reals are uncountable. So we suppose that that's not true. In other words, we suppose towards contradiction that they were countable, and we make an argument, we make this argument, we get this number z, and the number z both must be on the list because the list had all the real numbers, but it can't be on the list because it's different from every number on the list. That's a contradiction, and therefore, our assumption that the reals were countable in the first place must have been incorrect. So we get to deduce now that the reals are uncountable, and therefore there are more than one size of infinity.
▶︎ 16:10 I want to call attention to a certain aspect of this argument, namely the nature of these digits that we're looking at occur on this diagonal. Yes, the nth digit of the nth number is going to be on this diagonal, and therefore Cantor's argument is known as the diagonal argument. It's a diagonal construction precisely because during the course of the construction, we're doing something at stage N here, and we're looking at the nth member of the nth real number on the list, and those digits occur on this diagonal. So this is sometimes called the diagonal real, and we're proving Cantor's theorem by the method of diagonalization.
▶︎ 16:54 I want to mention another thing about this argument, and that is sometimes when people give the argument, they go like this. They say, "Well, suppose that the reals were countable so we can make a list of all the real numbers," and then they say, "We're going to define a new real number z," and they define z in just the way that I did, by the diagonal method. But I don't like this, I don't like this word "new," because we're not defining a new real number. It's just a real number. We're defining this number by reference to the list. It's not a new real number. It already existed before. It's not like we're creating a new real number by reference to the list. Rather, we're just making the argument that if someone gives us a list of numbers, then we can produce a number by reference to it that's not on the list. We're not creating this number. Rather, it already existed. We're just describing this number.
▶︎ 17:49 Given in terms of consulting the digits of the real numbers on the list, is not actually Cantor's original argument. In 1874, he published his result that the reals are an uncountable infinity, and he used a slightly different argument, which I want to describe now. So the argument starts the same as before. We suppose towards contradiction that the real numbers, the set of real numbers, is a countable set. So that means that we can put the real numbers on a list. So I'm going to go ahead and do that. I have a list R1, R2, R3, R4, and so on, and this is a list of real numbers, and I've supposed towards contradiction that every real number appears on this list.
▶︎ 18:47 Now, what I'm going to do, what Cantor did, is I'm going to specify a certain nested sequence of closed intervals. So maybe to get the first sequence, I look at where R1 is on the number line, and I pick an interval A1, B1 that excludes R1. So maybe I'll do this in colors here. So the green interval is going from A1 to B1. So I pick this non-trivial closed interval so that R1 is excluded from it. It's not inside the interval. It's outside the interval.
▶︎ 19:29 And then I look where R2 is. Maybe if R2 was already excluded, I don't necessarily need to worry very much. The more problematic case is when R2 is not yet excluded. And in that case, what Cantor does is, well, we can shrink the interval so as to exclude R2. No matter where R2 is, I can make a smaller interval, A2, B2, that excludes R2. And then I look where R3 is. And maybe R3 is already excluded, in which case I don't really have to worry very much, but maybe it hasn't been excluded yet. Maybe it's inside, and then at that moment, I want to shrink to a still smaller interval, A3, B3, and so R3 is not in the interval A3, B3.
▶︎ 20:23 So at each step, at the end step, I make sure that RN is not in AN BN. So I have these, the As are going up and the Bs are coming down, so ultimately I have A1 less than A2 less than A3 and so on, and B1 is bigger than B2 bigger than B3 and so on. And at the end step, I've made sure that the number RN is not in that interval. But now it's a basic fact that was known to Cantor and proved around the time, that any sequence, any nested sequence of closed intervals, of closed bounded intervals, will have a point inside. So there will be some real number Z that's inside all of the intervals. In fact, we can specify it exactly in this case, because the supremum of the As, there will be a least number that's larger than all the As. That will have to be inside. The sup on N of A sub-N will be inside all of the intervals.
▶︎ 21:36 Okay, so let me explain it again. We suppose towards contradiction that the set of real numbers is a countable set. So that means we can put the real numbers on a list. All of them. So we have a list of real numbers, R sub-1, R sub-2, R sub-3, and so on. Now, given that list, we're going to build a nested sequence of closed intervals. And we do it in such a way that R1 is not in the first interval, and R2 is excluded by the second interval, and R3 is excluded by the third interval, and so on. So at stage N, the Nth number on the list is excluded by the Nth interval. And now it's a basic fact, if we just take the supremum of the left-end points of those intervals, that will be a real number that is inside all of the intervals.
▶︎ 22:29 Okay, so what? Why do we care? Well, the point is that the number Z is in all of the intervals. It was never excluded. But R1 was excluded, and R2 was excluded, and R3 was excluded, and so on. So therefore, Z is not any of those numbers, because the numbers on the list were all excluded, but Z was not excluded. So therefore, Z can't be any of the numbers on the list, and that's a contradiction, because we had supposed that the list had all the real numbers on it, but it doesn't have the number Z on it, because Z is a number that's different from everything on the list. So the overall structure of the argument is the same as the argument we gave by the digit diagonalization method, and the...
▶︎ 23:15 Sometimes it happens, you can find people arguing online about when someone presents Cantor's argument using the digit diagonalization that I had first given, you can find people with very strong opinions about, "Well, that's not how Cantor first did it, because he used this nested interval argument," the one I just described. But to my way of thinking, those disputes about the two forms of the argument are actually not very important, and the reason is that there's a way of looking at the nested interval argument that makes it appear exactly the same as the digit diagonalization argument. These are just two superficially different presentations of the same underlying idea. And so I want to convince you of that by pointing out that specifying a digit, successive digits in a real number is the same thing as defining a nested sequence of intervals, and actually by that means we can see that these two presentations of the argument have the same underlying idea.
▶︎ 24:15 Let's do that. Let's think about, what does it look like when we specify the digits of a real number? Let's think about the number line here. Here's the whole number line. Here's one, two, three. Let me make it a little bigger. I'm sorry. I want to make it, expand it so I can draw a better picture. Let's zoom in, say, between 3 and 4. There's 4. So 5 is out here and 2 is over here. The line keeps going.
▶︎ 24:48 And let's think about the interval from 3 to 4. If I take this whole interval from 3 to 4, I claim that those are precisely the numbers that start with an integer part three point something. Yes. The green interval from three to four. The closed interval from three to four are exactly the real numbers that have a representation starting with three. Maybe the 3.1 is here, and 3.5 and 3.9 and so on, and three itself is 3.000, and so on.
▶︎ 25:27 And maybe someone objects, "Hey, hey Joel, what about the number four? Because you said it's a closed interval, which includes the endpoint, and four doesn't start with a three in its first place because four is 4.000 forever." Except, remember, four does have a representation starting with three, because four is the same thing as 3.99999 repeating. So the numbers that start with a three in the integer place and then have digits afterwards are exactly the closed interval from three to four.
▶︎ 25:57 Now let's go inside this interval, and let's look at the numbers that have a one in the first place after the decimal point. That's going to start from 3.1. Let's see, this is 0.5, 0.1 is about here, I guess. So if I have the numbers, I guess, let's see, something like this. This is 3.1 up to 3.2. Those are exactly the numbers, the numbers in the closed interval from 3.1 to 3.2 are exactly the numbers that start 3.1 something. Maybe I have 3.15 in the middle and 3.12 over here and 3.19 here. 3.2 also starts 3.1 because you can make 3.19999 repeating, yeah? That's the same as 3.2. So to specify the next digit is exactly to get this closed interval inside, yes?
▶︎ 26:53 And now I can take it one more step. Let's go red. So for example, the interval between 3.14 and 3.15, the two endpoints here in the red are exactly the, is exactly the interval. I've drawn it a little bit not to scale in order so that we can see it, but what I intend is that it's the closed interval that goes from 3.14 to 3.15. So this would be the digits, the numbers whose decimal representation starts with the digits 3.14. For example, 3.145 is in the middle, and 3.147 is towards the right end, and 3.141 is in the left. And so, we get both endpoints again because 3.15 is exactly 3.149999 repeating.
▶︎ 27:44 So in this way, what I'm trying to explain is that, by specifying successive digits of a real number in the way that we did in Cantor's diagonal argument, what we're really doing is specifying a nested sequence of closed intervals. And the full real number that we get by specifying all the digits is exactly the number that is inside all of those, all of those closed intervals. And so by this means, we see that the original digit diagonalization argument and the nested interval argument have the same underlying idea, which is at stage n you make sure that the number you're specifying is different from the nth number on the list, and therefore, you've produced a number that's not on the list, and that's a contradiction. So therefore, the real numbers make a strictly larger infinity.
▶︎ 28:38 Now, there's a certain sociological situation regarding Cantor's theorem, because first of all, because it's such a profound result, that there are different sizes of infinity, many people take issue with it and they're not willing to accept and so on. And so there's this phenomenon of crank mathematicians who are unwilling to accept the conclusion of Cantor's argument, and they write many, many articles. And actually, this phenomenon of crank mathematicians goes back. It has an extremely long history. Bolzano wrote a whole treatise making fun of crank mathematicians in his day. This was before Cantor's results, all about the circle squarers and the angle trisectors and so on.
▶︎ 29:24 These are theorems that are now known to be impossible to solve from classical geometry, and the cranks of his day attempted, without hope, to solve these classical problems, so he was often making fun of them. I get emails all the time from people claiming that Cantor's proof is wrong, and that all of mathematics is wrong, and that the authors of these emails are unrecognized geniuses and so on. And they send me various arguments criticizing Cantor's argument. But in every single case that I've checked, I don't often have the confidence to check all of them. It's too much work to check all the crank arguments, except when I do check them, then invariably there's mistakes and errors and misunderstandings.
▶︎ 30:05 But let me just share with you a few of the kind of ideas that people sometimes provide. For example, sometimes people say, "Well, look, there's no problem with the diagonal real not being on the list, because we can add it to the list, and that would be a list that did have that number Z on it." So in other words, in Cantor's diagonal argument, we have the numbers R1, R2, R3 and so on, which we had supposed was all the real numbers, and we produce this diagonal real number Z, whose nth digit is different from the nth digit of the nth number. And we had deduced the contradiction because Z was not equal to any of the numbers on the list, even though all numbers were supposed to be on that list, and the proposal on offer in these messages is to take that real number Z and put it on the list. We could just make it R0, for example.
▶︎ 30:59 But that proposal is completely without merit, because the claim isn't that there's no possible list that the number Z could be on. Of course we can make a new list that has the number Z on it. The claim rather is that it's impossible to have a list, a countable list of real numbers that already includes all real numbers, and so the argument was, for any given list, we can produce a number that's not on that list. That's the contradiction. The fact that you can make another list that does have that number is irrelevant.
▶︎ 31:33 Of course, once you add that number to the list, that's a new list, and there will be a number that we can produce by diagonalization using that new list, that won't be on it, and so on. And if we add that number, there will be another number not on that list and so on, and we can keep repeating this. It's just impossible to ever complete this task. You cannot have a list of real numbers that includes every real number, because for any list of numbers, you can perform Cantor's diagonalization method and produce a real number that's not on the list.
▶︎ 32:04 Let me mention how Cantor's result relates to the topic of potential infinity and actual infinity that we discussed in a previous lecture. It's my view that really Cantor's achievement in his theorem that there are uncountable infinities is part of the cause of the sea change that occurred in mathematics, by which mathematicians generally all switched from the potentialist philosophy of infinity to the actualist philosophy of infinity.
▶︎ 32:32 It's maybe not so clear how to have a potentialist concept of countable and uncountable versus an actualist concept of countable and uncountable. Maybe it is possible to have a potentialist account, because what you want to say is somehow that the potentialist understanding of the natural numbers is already an understanding of a countable infinity, but the real numbers can't be achieved in that enumeration way where, say, in countably many steps, you always have some real numbers but only finitely many at a time and they're potentially infinite in the sense that you can have always some more. But if you think that somehow the steps that you get the real numbers coming to you is a countable number of steps, then you will never, if you look at the future path that you're gonna follow out getting more and more real numbers, you won't actually. It can't be the case that you get all of them, and really Cantor's ideas explain exactly what's going on in that process.
▶︎ 33:38 There's no countable sequence of finite sets of real numbers that encompasses every real number, and that's a sense in which the uncountable infinity of the real numbers can't be achieved in a simple potentialist outlook. There are other approaches to potentialism that could make sense of the real numbers. For example, if you think of, just take as the potentialist system of the real numbers all finite sets of real numbers. That's a directed potentialist system, so it will validate S4.2, to use the technical modal logic that we discussed in that previous lecture.
▶︎ 34:18 So there are ways of talking about the infinity of the real numbers in a potentialist point of view, but the most straightforward way of understanding Cantor's result is as a result in actual infinity, and it's not possible to put the set of real numbers into one-to-one correspondence with the natural numbers, and that's the sense in which the real numbers are an uncountable infinity.
▶︎ 34:40 We can view developments in mathematics in part as a kind of gradual and continual enlargement of our number concept as mathematics develops. So maybe one starts with, say, the whole numbers. So those would be the numbers one, two, three, four, and so on, but without zero. The introduction of zero actually was a profound development in mathematics, and it came much later than you might think. The acceptance of zero as a legitimate number concept was a very important step. And so one moves then to the natural numbers, including the number zero.
▶︎ 35:17 But then, of course, one wants also to have negative numbers, so that would be the move to the integers, where we have zero, one, two, three, and so on, but also -1, -2, -3, and so on. And this forms a mathematical structure known as a group. We have an additive group. It's actually a ring. We can add and multiply. We have additive inverses by adding the negations. But now, of course, one wants to divide arbitrary numbers, and so that's the move precisely to the rational numbers, where we have now fractions we can divide by any non-zero quantity, and that's a very rich number system.
▶︎ 35:55 It's integral to the philosophy of the Pythagoreans in ancient times, who aimed to strive to understand so much of their reality by the concept of ratio, and so the fact that the rational numbers were such a robust number system was built in to their quasi-religious number mysticism philosophy. But the discovery then that the square root of two is irrational. It's a fundamental geometric quantity. If you take a one-by-one square, then the diagonal of the unit square has length square root of two, and it is not rational. It is not part of this number system, and one needs to expand the number system in order to accommodate such a kind of number, square root of two. So that was quite disturbing for them, but of course, it leads to the concept of eventually of the real numbers.
▶︎ 36:50 I'm going to leave a little space here because actually what I want to put in here are these kinds of numbers, like the square root of two, are called algebraic numbers because they satisfy. The square root of two, for example, x equals the square root of two, is exactly a solution of x squared minus two equals zero. It's one of the two solutions, plus or minus square root of two, are the solutions of this equation. So a number is algebraic when it's the solution of a polynomial equation over the integers of a non-trivial equation. So for example, the cube root of five is also algebraic because it satisfies x cubed equals 5 or x cubed minus 5 equals 0.
▶︎ 37:34 So other things, for example, if I take, say, the square root of the cube root of 5 plus 6, then if I build such a kind of number by taking roots and powers and so on, then I can very easily figure out what is the equation that it solves. For example, this number, if I square it, I know that it will be equal to the cube root of 5 plus 6, and therefore, if I subtract 6 from x squared, that will be equal to the cube root of 5, and therefore, if I cube this, that will be equal to 5, and therefore, if I subtract 5 from this, I'll get 0. So this is a number that solves this polynomial equation and therefore, this number is algebraic. So one can do this kind of trick with any kind of expression that you build by roots and powers in that way, although it's actually a deep fact that not every algebraic number appears, not every algebraic number can be represented by radicals in that manner.
▶︎ 38:40 Maybe you think that every real number is algebraic. I'm going to put the algebraic numbers here. Those are the algebraic real numbers. And maybe it's a mystery whether every real number is algebraic. Does every real number satisfy a polynomial equation over the integers, is the question. And the answer is no, and this was proved by Liouville in 1844. He introduced a specific real number that is not algebraic.
▶︎ 39:10 In 1844, Liouville wrote down a specific real number, it's now called the Liouville constant, and he proved that this number is not algebraic. It's a transcendental real number. So the Liouville constant is the number 0.110. Let's see, it has a 1 in the n factorial place, so it has a 1 in the 1s place, that's 0 factorial and 1, no, let's see, 1 factorial and 2 factorial, the second place, 3 factorial is 6, so 1, 2, 3, 4, 5, 6, and so on, and then there's a lot of zeros, and then a 1 in the 5 factorial place, and then it has a lot of zeros until the next one in the 6 factorial place way out there and so on. So this kind of number is called a lacunic number because it has these lakes of zeros between the 1s.
▶︎ 40:00 The feature that's important about the Liouville constant is that the claim is that it's not algebraic, and one can begin to see why that would be true about this number, because if you imagine squaring this number, if this is x and we square x, then if I go way out and I have one of these isolated zeros with the huge lakes on each side, then that number 1 is going to be multiplied by other digits in the Liouville constant when I'm squaring it. And so you can see what happens is that those isolated 1s get moved around in the multiplication, but they remain isolated. And similarly, when you multiply x or a power of x by a constant, then the isolated digits of the Liouville constant basically just get moved around, but they remain isolated. And so therefore, there's no way to add up these different values in such a way that they all cancel. You're never going to get 0 when you combine powers of x and integer multiples of x. And that's a way of understanding how it could be that the Liouville constant is transcendental.
▶︎ 41:12 A real number is transcendental if it's not algebraic. So the Liouville constant is a transcendental number, and this was the first known example of a transcendental number. I view it as a much more recent development of the same nature as that tremendous Pythagorean discovery of the irrationality of the square root of 2. Just as the Pythagoreans needed to expand their number concept from the rationals to include irrational numbers, it's because of Liouville that we expand our number concept from the algebraic numbers to include the transcendental numbers. It's just as important, and just as philosophically troubling for our capacity for understanding these numbers. We have an idea, and somehow the result is always proving that there's something beyond, and we need to have a larger concept in order to grasp those new realms.
▶︎ 42:10 Let me turn now to Cantor's proof of the existence of transcendental numbers. Cantor offered an alternative proof for the existence of transcendental numbers. Cantor argued like this. What he said is, "Look, let us consider the algebraic numbers. Every algebraic number is the solution of a polynomial over the integers. But a polynomial over the integers, I can think of it as specified by a finite list of numbers, the coefficients of the polynomial."
▶︎ 42:43 For example, say I have a polynomial x cubed minus 5x squared plus 6x minus 7. This is a polynomial and I can think of it as just specified by the list of coefficients, namely 1, -5, 6, -7. Or if maybe there's terms missing, I just put a 0 in the list. So every polynomial over the integers is specified by a finite list of integers, and every algebraic number is determined from such a polynomial. Of course, such a polynomial might have more than one solution. A cubic has at most three solutions in the reals. An Nth-degree polynomial has at most N solutions in the real.
▶︎ 43:31 So I can specify an algebraic number by specifying the polynomial and specifying the place of the solution that I want to talk about amongst the roots. For example, I might say, "I have this polynomial, and I want to talk about the first solution in order." There's at most three. Or I might want to talk about this polynomial or the third solution if there are three. I'd have to think about whether there are three. I think there are. But the point is that every algebraic number can be specified by a finite list of integers together with one more integer. So altogether, a finite list of integers.
▶︎ 44:10 But a finite list of integers is a word in the alphabet of the integers. If I think about the integers as a countable alphabet, then the collection of words in that alphabet is the collection of finite sequences from that alphabet. And we already proved in the previous lecture, and Cantor had already proved, that the set of finite sequences over a countable set is still a countable set. And therefore, there are only countably many polynomials over the integers. And there are only countably many polynomials over the integers together with this sort of root specification of the algebraic number amongst those roots. So therefore, because every algebraic number is specified by a finite list of integers, there are only countably many algebraic numbers.
▶︎ 45:05 Let's think about what that means. Cantor argues there are only countably many algebraic numbers. We can put all the polynomials on a list, and each polynomial has finitely many algebraic numbers that correspond to it. But therefore, there must be transcendental numbers because there's uncountably many real numbers. So we could argue just like this. There must be transcendental numbers because there are only countably many algebraic numbers, but there are uncountably many real numbers.
▶︎ 45:39 So therefore, some of the real numbers must be transcendental. They cannot all be algebraic because then there would be only countably many real numbers. But Cantor proved that the real numbers are an uncountable set. That's one way to prove it. We're going to give another argument soon, but I want to think about the nature of this argument. The argument on the table is there must be transcendental numbers because there's only countably many algebraic numbers, but there are uncountably many real numbers. So therefore, some of the real numbers must be non-algebraic, which is to say they must be transcendental.
▶︎ 46:12 So in fact, the argument shows there must be uncountably many transcendental numbers, because if there were only countably many transcendental numbers, then we would have the countably many algebraic numbers and the countably many transcendental numbers, and then altogether the real numbers would be the union of two countable sets, which would be countable. But we've shown that the real numbers are an uncountable set. So therefore, Cantor really has showed not only that there are some transcendental numbers, but he's shown that almost every number is transcendental, because only countably many of them are algebraic, and all the rest form an uncountable infinity of transcendental numbers.
▶︎ 46:47 Now, there's a certain feature of this argument, and that is the question of whether Cantor's argument, if we compare it with Liouville's, how do we think about this comparison? Liouville gave us a specific number, the Liouville constant, and he proved that that number is transcendental. And the question is, does Cantor's argument give us a specific real number that is transcendental, or is it just a kind of pure existence proof where we know that there are some transcendental numbers, but maybe we don't know of any specific number that it's transcendental?
▶︎ 47:21 And a lot of times people come to what in my view is an incorrect conclusion about this, and they say positively that Cantor's proof of the existence of transcendental numbers is not constructive in that sense. But I think this is wrong. I think if we think about the argument in a slightly different way, we'll realize that actually Cantor does give us a constructive proof of the existence of transcendental numbers. And furthermore, if we unwind all the details, we will get specific numbers that are provided by Cantor's argument, that are transcendental.
▶︎ 47:55 Let me discuss this. Remember that Cantor proves that the set of finite sequences over a countable set of letters, the set of words in a countable alphabet, or the set of finite sequences from a countable set is a countable set, and that proof is constructive. It gives us a specific way of enumerating the finite sequences of integers. But therefore, using that, we can produce a specific list, a constructive list of all the algebraic numbers. Because every algebraic number, remember, is determined from the polynomial of which it's the root and its place among those roots, those finitely many roots. So therefore, we have a concrete list of all the algebraic numbers.
▶︎ 48:43 But now if we combine that fact with the fact that the diagonalization construction that Cantor provides is in fact constructive, the digit diagonalization method gives you a specific number that's not on the list. Therefore, if we take the specific list of the algebraic numbers and we perform Cantor diagonalization, we get a specific real number that is not on that list. And therefore, it's a specific number that's transcendental. It's a different way of thinking about what the achievement is that Cantor had made.
▶︎ 49:21 On the one hand, one can look at the diagonal argument as proving that the reals are uncountable. It's proof by contradiction, because if they were countable, then we could produce this number that was on the list but can't be on the list. But another way of understanding the argument is that what he's really proved is that for every countable list of real numbers, there is a number that's not on that list. That's what the diagonalization method produces. And so applying that more constructive formulation of the Cantor argument, which is, in fact, how he presented it in his 1874 paper, for every list of real numbers, there's a real number that's not on the list. And furthermore, we can specify that real number exactly because it is specified, for example, by the diagonalization procedure. So therefore, because we can put the algebraic numbers on a list in a constructive way, we can therefore produce a real number that's not on that list.
▶︎ 50:19 Many years ago, I saw, I've lost track of the article, but I saw in one of these math monthly journals or something like that, an article with the title, and it was something like, "0.11717," something or other, "is transcendental." I'm not getting it exactly, but the point of this essay, which I just thought was fantastic, it dove into the details of the specific enumeration that's provided by the Cantor enumeration of the algebraic numbers and performed the diagonalization procedure in just the way that he described. And the first few digits are the digits in the title of that article. I wish I could give you the citation. I'm sorry. I've lost track of it over the decades.
▶︎ 51:07 But what it does is show you that actually there's an analog of the Liouville constant for Cantor. We could call that number the Cantor constant, or maybe it should also have Dedekind's name on it, actually, because I should mention that it has recently come to light that in the letter exchange between Dedekind and Cantor leading up to Cantor's 1874 paper, many of the important ideas, including the specific one about showing that the algebraic numbers are countable, were anticipated by Dedekind in those letters. And so historians are looking at that and determining what proportion of credit should go to Cantor and to Dedekind. It seems clear that Dedekind had some very important insights into that particular part of the argument which Cantor had borrowed in his 1874 article, unfortunately without mentioning Dedekind, but he obviously should have in light of these letters.
▶︎ 52:03 So I'd like to consider next some variations of Cantor's argument and some special cases, and we'll get into further aspects of Cantor's amazing achievement on the uncountable infinity.
▶︎ 52:16 Let's consider what's now called Cantor space or the space of infinite binary sequences. These are the sequences, for example, maybe we have the sequences of zeros and ones. So we have this, say, the all one sequence. It just is ones forever, or the all zero sequence is a different one. Or maybe we have the alternating sequence, one, zero, one, zero, one, zero, and so on, or we could, of course, alternate in another way, or maybe we have somehow some more complicated patterns like this, and so on. All of these are infinite binary sequences. These are elements in Cantor space.
▶︎ 52:56 Now, I'm not interpreting such a sequence as a real number. This is a different kind of space. It's just sequences. And so the claim is that the Cantor space is uncountable. That's the claim. So we're going to prove the analog of the uncountability result of Cantor for the space of binary sequences. This space is commonly denoted by two to the n. So two being zero, indicating that we have zeros and ones, and n indicating the length of the sequences. So the claim is that Cantor space two to the n is an uncountable set. It is an uncountable infinity.
▶︎ 53:39 Let's give that argument now. The structure of the argument is identical to the structure of Cantor's original argument with the real numbers. But actually, it's slightly easier to prove that this space is uncountable than it is to prove that the reals are uncountable. So let me show you how it goes. We're going to show, let me just make the claim. Two to the n is uncountable is the claim.
▶︎ 54:15 We start just the same. We suppose towards contradiction that the space is countable. So that means that it's equinumerous with the natural numbers, and that means that we can make a list of all of the elements in Cantor space. So I make a list of all of the binary sequences, S1, S2, S3, and so on. And we suppose that every binary sequence appears on this list.
▶︎ 54:43 And now, given that list, we define a new sequence. We define a sequence by reference to that list. So I'm going to define a certain binary sequence, I'm going to call it Z, and Z is going to have an infinite list of bits. There's going to be B1, B2, B3, and so on. And all I have to do is make sure that B1 is different, it's either 0 or 1, and I look at the first symbol of S1. And I let b1 be the opposite of it. And for b2, I make it different from the second bit of s2, and for b3, I make it different from the third bit of s3, and so on. But to make it different, well, there's only two bits because everything is either a zero or a one, and so it means I'm just flipping the bits. So bn is different from, it's the opposite, the nth bit of sn.
▶︎ 55:48 And therefore, this sequence z, which is a perfectly good binary sequence, is not s1 because it starts with a different bit, and it's not s2 because the second bit is different, and it's not s3 because the third bit is different, and so on. So therefore, this binary sequence is not on the list, and that's a contradiction. So we get the same contradiction, but this argument here is a little bit simpler than the diagonalization of the real numbers because there's absolutely no issue about non-unique representations and so on because the binary sequences do have unique representation. The sequence consists of its sequence of zeros and ones that appear in it, and it's not equal to any other such kind of sequence. So it's a little bit easier because it avoids that subtle issue in the real number case.
▶︎ 56:36 Let me do the argument again. The claim is that Cantor space, the space of infinite binary sequences, is an uncountable set. So to prove that, we suppose towards contradiction that it's a countable set. So that would mean that Cantor space, the space of infinite binary sequences, would be in one-to-one correspondence with the natural numbers. That means that we can make a list of those infinite binary sequences, s1, s2, s3, and so on, in such a way that every binary sequence appears on the list.
▶︎ 57:08 And now I define from that list a certain binary sequence that I'm calling z, and it consists of a certain sequence of digits, of bits. Each bit is either zero or one, and I just make sure that the nth bit is the opposite of the nth bit of s sub n. So the nth bit of z is different from the nth bit of s sub n. And therefore, z is a different sequence than all of the sequences that appear on the list. It's different from s1 in the first bit, different from s2 in the second bit, and so forth. So z does not appear on the list, and that's a contradiction, and therefore, the assumption that Cantor space was countable must be wrong, and therefore, Cantor space is an uncountable set. So let me explain how this result on Cantor
▶︎ 57:53 This space relates to another uncountability result that we can provide, and that is the power set of the natural numbers. The power set of a set is the collection of all subsets of the set. So I could write it like this. It's the set of all sets A such that A is a subset of the natural numbers. So we would have the whole set of natural numbers as well as the empty set, the set of even numbers, the set of odd numbers, composites, primes, whatever you like. They're all in there, in the power set of the natural numbers.
▶︎ 58:27 And now the point is that there's a kind of identity between Cantor space, the space of infinite binary sequences, and the power set of the natural numbers. Actually, we can make a one-to-one correspondence between these two sets. Because for any given set like that, if it's a subset of the natural numbers, then I can make a sequence from A. For example, let's have s of A. What I do is I have a sequence of zeros and ones, where I put a one, it indicates that the corresponding number is in A. So the nth bit being one indicates that n is in A. So this zero means that the number zero is not in A, and this one means that the number one is in A, and this one means that the number two is in A, three is not in A, four is in A, and so on.
▶︎ 59:31 This is called the characteristic sequence of the given set A. So for any set A, I can just write down its in-out pattern for the natural numbers, either zero is in or out, one is in or out, two is in or out, and so on. And so for any set of numbers, I can produce the corresponding pattern of membership, and that's a binary sequence. But furthermore, for any binary sequence, I can just take the set of indices where the ones occur, and that's going to give me a set of natural numbers, and that's a one-to-one correspondence between Cantor space, the space of infinite binary sequences, and the power set of the natural numbers.
▶︎ 1:00:11 And so what this argument really shows, therefore, because we proved this is an uncountable set, it follows that this also is an uncountable set because these two sets have the same size, because there's a one-to-one correspondence between them. So therefore, what we've proven is that the power set of natural numbers has the same size, I'm sorry, the power set of natural numbers is an uncountable set because of this argument.
▶︎ 1:00:38 So in fact, we can show that Cantor space and also the power set of the natural numbers has the same size as the set of real numbers. So let me give that argument. The power set of natural numbers, we already argued that it is equinumerous with the Cantor space, but I want to argue that it's also equinumerous with the set of real numbers. So one way, for example, we can easily see that the Cantor space, the space of binary sequences, is less or equal the reals in size, because if I have an infinite binary sequence, I can just think of it as a real number, I just put zero point and then whatever the bits were in the sequence, I can just interpret that as a decimal representation of a real number. And that will be a one-to-one correspondence between Cantor space and a set of real numbers, which shows that there's at least as many real numbers as there are members of the Cantor space.
▶︎ 1:01:50 But then conversely, given any real number, I can think about the set of rational numbers that are below it, that's called the Dedekind cut of that real number. And so if I associate every real number with the set of smaller rational numbers, that's a one-to-one map, it's a one-to-one association between the real numbers and sets of rational numbers. Not all sets of rational numbers, but some of them, so I only get less or equal here. But the point is that because, precisely because the set of rational numbers is equinumerous with the natural numbers, this is equinumerous with the power set of the natural numbers, and so I have the same thing on all sides. So therefore, all of these sets have exactly the same size, they are all equinumerous with one another.
▶︎ 1:02:40 And notice that I'm using here the Cantor-Schroeder-Bernstein theorem about comparison of size, which we discussed in another lecture. Namely, I didn't show directly that the reals have the same size as Cantor space. Rather, I showed that the Cantor space is less or equal to reals in size, which is less or equal the power set of the natural numbers, which is equinumerous with the Cantor space. So I have injections both ways, and it's precisely the Cantor-Schroeder-Bernstein theorem that tells us that when you have two sets and each of them is at least as large as the other, in the sense that we have one-to-one correspondence from each one to a subset of the other, then we can turn that into a one-to-one correspondence of the sets altogether so that they are equinumerous.
▶︎ 1:03:33 What I'd like to do now is generalize this result. We proved that the power set of the natural numbers is an uncountable set. Cantor also proved a vast generalization of this idea. Namely, what he proved is that for any set X, it is strictly smaller than the power set of X. The power set of X is the set of all subsets of X. So the claim is that if you have any set whatsoever, if you want a bigger set, a bigger infinity, just take the power set and that will be a bigger infinity.
▶︎ 1:04:11 Let's give that proof. It's very similar actually to the argument that we just gave for Cantor space except a little bit more abstract. So let's do the argument. Of course we know that there are at least as many subsets of X as there are elements. This claim can be seen as the claim for any set X, of course, the number of elements of X is just the size of X, and this is the number of subsets of X. So what we're claiming is that any given set has more subsets than elements. Of course, it always has at least as many subsets as elements, because if I have an element A here, then I can make the singleton A, the subset that has only that individual as an element, that's a perfectly good subset of X, and that's a one-to-one correspondence.
▶︎ 1:05:02 Different individuals will have different singletons. So there are always at least as many subsets as elements. The claim is saying that it's a strictly bigger infinity. Now, of course, it's not good to just say, "Well, look, I've got all the singleton sets, but I also have some other sets." If X has more than one element, then it has the doubleton sets, or the whole set, and the empty set, and so on. So there's always additional sets besides just the singletons.
▶︎ 1:05:29 And one might be tempted at first to say, "Therefore, it's strictly larger," but that's wrong by Galileo's paradox. You're not entitled to say that one set is bigger than another just because that other set is equinumerous with a proper subset of it. To be bigger means that you cannot find a one-to-one correspondence between them. It should be at least as big, but there's no one-to-one correspondence between them. That's what it means to be strictly larger, not just that there is a one-to-one correspondence of X with some of the sets and such that there are other sets left over, that would be committing the fallacy involved in Galileo's paradox.
▶︎ 1:06:11 To prove the theorem, we suppose that X is equinumerous with the power set of X. We suppose towards contradiction that we can have a one-to-one correspondence between elements of X and subsets of X. So that would mean that for every individual we associated with a certain subset of X, in a one-to-one way, in such a manner that every subset is realized as X sub A for some individual A in X. So we're supposing towards contradiction that we have just as many subsets as elements, so that would mean that we have a way of naming the subsets after the elements in such a way that every subset is named after an element and it's a one-to-one correspondence.
▶︎ 1:07:03 Now, I let D, for diagonal, I let the diagonal set be the set of elements in X, such that A is not a member of X sub A. Maybe some individuals are in the subset of X that's attached to them. It can't always be true, because the empty set is one of the sets and it has to be X of A for some A, but A can't be in the empty set. So sometimes the individual is not in the set that's attached to it, and sometimes it is. For example, one of the subsets is the universal set that has all the individuals in it. And so in particular for that set, A is in X of A. So sometimes it's true that A is in X of A, and sometimes it's not true.
▶︎ 1:07:51 So I'm just going to take the individuals that are not in the set that they are associated with. That's a perfectly good set, it might have some but not all elements of X, and let's think about this set. This is a subset of X, but just notice because of this membership requirement we have, that an individual A is in D if and only if A is not in X of A. That's the membership requirement to get in. We take exactly the individuals that have that property. So A is in D if and only if A is not in X of A.
▶︎ 1:08:35 But it follows precisely because of that, that D is not equal to X of A. It can't be equal to X of A because they have a different answer about whether little a is a member of it or not, because a is in D if and only if it isn't in XA. So that's a disagreement on that one point, which is enough to make them different sets. I called it the diagonal set because this property of whether a is a member of X of A, it's very similar to this diagonal argument of Cantor in the diagonal argument with the real numbers because we were looking at the Nth real number and asking whether the Nth bit of it, the Nth digit of it. So it's this double end aspect. Here we're asking whether X of A disagrees with D at A. So this A, A is a kind of abstraction of this diagonal idea.
▶︎ 1:09:29 So what have we done? We're trying to show there's more subsets than elements. We suppose towards contradiction that we have just as many subsets as elements. That means that we have a one-to-one correspondence between the subsets of X and the elements of X, which means we have a naming scheme. Every subset of X can be thought of as attached to an element A. So we have this, for each individual A, we have a subset X of A, in such a way that all the subsets arise.
▶︎ 1:10:03 Then given that naming scheme of subsets, we define a certain subset D, the diagonal subset consisting of the individuals that are not in their set. And then we observe that little a is in that set if and only if it's not in its set. That's the definition of the diagonal set. But now it follows from this equivalence that D is not X of A for any A. So D is a subset that isn't attached to any individual. Contradiction.
▶︎ 1:10:36 So therefore, our supposition that we could find such a one-to-one correspondence between subsets and elements must be wrong, which is to say the power set of X is a strictly bigger set than X. So what good is that? Well, it's actually quite remarkable now.
▶︎ 1:10:54 We can make some deductions from this general fact. We saw if we started with the natural numbers, we can make a bigger infinity by taking the power set of the natural numbers, and this in fact was equinumerous with the Cantor space of binary sequences and also equinumerous with the set of real numbers. But now this is a perfectly good set, and it has a power set, the set of sets of natural numbers, so it's strictly less than the power set of the power set of the natural numbers. We said for any set its power set is a bigger infinity, so this is a bigger infinity than this one. So now we have three infinities. This is the countable infinity, this was the size continuum, an uncountable infinity, and this is an even bigger uncountable infinity. Yes?
▶︎ 1:11:55 But of course we can do it again. We can look at the power set cubed of the natural numbers, if I think of this as P squared. I just apply the power set one more time and I can keep iterating to get more and more infinities. So now we see that there are infinitely many different uncountable infinities. There's this one, and this is bigger and bigger and bigger and so on, and we can make it as big as we want that way.
▶︎ 1:12:19 So I might ask, "Well, how many uncountable infinities are there?" Or, "How many different infinities are there?" And you might look at this and say, "Well, there's infinitely many," but of course, which infinitely many? That's the question, because actually so far it's not very impressive because we only have countably many infinities on this list. If we have only iterated the power set operation, then we have the first one and the next one and the third one and so on, and that's only countably many different infinities. But maybe we want to show that the number of infinities is more than any given one of them. Yes.
▶︎ 1:13:03 And in fact one can show that, so how can I make an infinite set that's bigger than all of these infinities? Well, it's quite easy. I could just take the union for every natural number N of the N fold iteration of the power set. In other words, I just union all these sets up and that's different in size from any given one of them because it's at least as large as each one of them. And since the next one is bigger than the previous, the union of all of them is strictly bigger than any one of them because it's at least as big as the next one.
▶︎ 1:13:36 So therefore, I can continue this list transfinitely. I can find another set that's beyond all of the things on this sequence, and then its power set is strictly bigger. And the power set of that is strictly bigger, and so on. And I can keep going, and that's still only countably many, but in fact, I can keep iterating this process. If at any stage I found myself at some limit ordinal of sets, then I can just take the union of all the sets I've produced so far, and that's going to be a set which is bigger than anything on the sequence up to that point. And so I can continue the sequence forever in the ordinals. And so therefore, the number of different infinities is bigger than any one of them.
▶︎ 1:14:20 There's some interesting foundational features of this argument that I've just given. Namely, if you think about the Zermelo axiomatization of set theory that he provided first in 1904, but then more refined in 1908, Zermelo set theory doesn't actually prove the claim that I made. It's not quite strong enough to prove that there are uncountably many different infinities. It's consistent, it's known to be consistent with Zermelo set theory that there are only countably many infinities. But if you look at the slightly improved version of the axioms which were added shortly after that time, Zermelo-Fraenkel set theory adds the replacement axiom. And that's really what I'm using here, is the replacement axiom.
▶︎ 1:15:04 Because for each one of these sets, I have this sequence of sets that I can define, and to know that I can take them all together and union them up is exactly using the replacement axiom of Zermelo-Fraenkel set theory. So in ZFC, we can show that there are more infinities than any given one of them, whereas in Zermelo set theory, it's a little bit too weak to prove that claim, and it's consistent that there are only countably many different infinities. So I'd like to turn now to describe some
▶︎ 1:15:41 allegorical accounts of the Cantorian logic on countable infinity, so let me give some of those arguments now. This is the anthropomorphic way of understanding the argument that I find helpful. And in fact, as a sort of general advice to students, I often recommend that students try to imagine that the mathematical objects they're trying to understand are people, people maybe if there's some tension that they're fighting or maybe cooperating or they're playing a game or something. When you anthropomorphize your mathematical arguments, then oftentimes you can gain some insight into the nature of those things.
▶︎ 1:16:22 So let's try to do that with Cantor's argument. The first claim I'm going to make is that for any set of people, maybe there's infinitely many people, there are more committees than people. That's the claim. What is a committee? Well, a committee is just a set of people. There's the universal committee that everyone is on. That's the worst committee, and the best committee is the empty committee. So no one is on that committee.
▶︎ 1:16:51 But then also, there's the one person committee, so I'm on my committee. I guess it's a question of how often is that committee in session? Is it always in session? I'm always with myself, so maybe the one person committee is always in session. But that's a mark against the committee, I guess, if it's always in session. But then there's the two person committees, three person committees, and so on. What I'm claiming is that there are more committees, more possible committees, than there are people. The logic of the space of logically possible committees is not equinumerous with the number of people.
▶︎ 1:17:26 So let's give the proof. Of course, there's at least as many committees as people, because for every person, there's the one person committee consisting of them, and that's a one-to-one correspondence with the people and some of the committees. Now, the fact that there might be more committees than just the one person committees, there definitely are more committees than just the one person committees, because there's also the empty committee, we mentioned. That doesn't show that there's more committees than people. It's because that would be committing the Galileo paradox situation. Rather, we have to show that it's not possible to place the committees into one-to-one correspondence with the people.
▶︎ 1:18:05 So let's suppose, toward contradiction, that we could assign every committee to a person in such a way that made a one-to-one correspondence between the committees and the people. So in a sense, we're naming the committees after people. I'm going to name every committee after a person in a one-to-one manner. I'm not saying that the person is on the committee that's named after them or that they're not on, although it must be the case because it must sometimes be the case. For example, the universal committee is going to be named after someone, and that person is on the universal committee, because everyone is on the universal committee. And the empty committee is named after someone, and that person can't be on the empty committee because no one is on the empty committee.
▶︎ 1:18:44 So sometimes it happens that the person is on the committee that's named after them, and sometimes it happens that the person is not on the committee that's named after them. Let's consider the collection of people that are not on the committee that's named after them. I'm going to call this the diagonal committee. The diagonal committee consists of all people who are not on their committee. The diagonal committee is a perfectly good committee, and so it must be named after someone, so let's say that person's name is Danielle.
▶︎ 1:19:14 And now I ask, "Well, is Danielle on her committee? Is she in the diagonal committee?" Danielle would be in the diagonal committee if and only if she's not on her committee, which is the diagonal committee. So therefore, what we seem to see is that Danielle is on her committee if and only if she's not on her committee. If she is on it, then she shouldn't be. And if she isn't on it, then she should be because the diagonal committee consisted of all people that are not on the committee that's named after them. And this diagonal committee was named after Danielle. So she's on it if and only if she's not on it. Contradiction.
▶︎ 1:19:51 That logic is identical to the logic that we gave for proving that the power set of a set is strictly larger than the set. There can't be a one-to-one correspondence between subsets of the set or committees, and individuals in the set or people in the set.
▶︎ 1:20:05 Let me give another version of this argument. This was suggested by one of my Oxford students. I claim there are more fruit salads than fruits. Suppose you have a collection of fruits. Maybe infinitely many different fruits. Then, what's a fruit salad? Well, we make a fruit salad by specifying the fruits that are in the fruit salad. So there's this strawberry salad and so on. And the salad consisting of strawberries and the salad consisting of apples, grapes and pears, and so forth. There's also the empty salad. That's good for dieting. And there's the universal salad that has all fruits in it.
▶︎ 1:20:41 I'm looking at the collection of logically possible fruit salads that you could make using the fruits that are available. And the claim is that there's more fruit salads than there are fruits. How can we prove that? Well, we suppose towards contradiction that the number of possible fruit salads is the same as the number of fruits. We know there's at least as many fruit salads as fruits, because for each fruit there's the fruit salad consisting of just that fruit. But then there's also the empty fruit salad and so on, the universal fruit salad. So there's more than just those singleton fruit salads.
▶︎ 1:21:13 If they were the same, then there would be a one-to-one correspondence between the fruit salads and the fruits. So therefore, that would provide a kind of naming scheme for the fruit salads. We could name every fruit salad after a fruit. I'm not saying the fruit is in the fruit salad that's named after it, although sometimes that must be true, because there's the fruit salad that has all fruits in it, and in particular, that fruit salad would have the fruit that it's named after in it. But there's also the empty fruit salad, which can't have any fruit in it. And so in particular, that one doesn't have the fruit that it's named after as an ingredient.
▶︎ 1:21:49 So of course, now I'm going to make the diagonal fruit salad, which consists of all the fruits that are not in the fruit salad that's named after it. And then that's a perfectly good fruit salad. It contains some but not all fruits. So it must be named after one of the fruits, because we suppose that every fruit salad is named after a fruit. So let me suppose, for example, that this fruit salad is named after, say, durian. Durian, the diagonal salad is named after durian.
▶︎ 1:22:20 And then I ask, is durian in the diagonal salad or not? Well, then if it is in the diagonal salad, then it should not be in the salad that's named after it, which is the diagonal salad, and so it shouldn't be in the diagonal salad. So if it is in the salad, it shouldn't be. If it is in the diagonal salad, then it shouldn't be. But if it isn't in the diagonal salad, then it isn't in the salad that's named after it, and so it should be. And that's a contradiction.
▶︎ 1:22:45 So therefore, there can't be an equinumerosity relation between the fruit salads and the fruits, and therefore, there are always more fruit salads, more possible fruit salads than fruits, more committees than people, more subsets than elements. These are all identical arguments. It's just a different way of understanding.
▶︎ 1:23:05 Let me discuss a certain issue that Bertrand Russell had arrived at in the beginning of the 20th century, the Russell Paradox. It's concerned with a certain principle in set theory, namely the general comprehension principle. The general comprehension principle is the following principle. For any property phi, we can form the set consisting of all objects that have that property. This is the general comprehension principle. If you have a property, you can make the set of all instances of things that have the property.
▶︎ 1:24:06 For example, the set of all elephants is a set, because being an elephant is a property, one of the properties I'm talking about. The set of all even numbers is a set. The set of all prime numbers, the set of all functions from the reals to the integers. For any property, you can make the set of all things with that property. That's what the general comprehension principle says.
▶︎ 1:24:27 Now, the historically fascinating situation is that, at the end of the 19th century, Gottlob Frege was working on this monumental treatise that was undertaking his program of logicism, which aimed to reduce all of mathematics to logic. This monumental work. And so he wanted to identify the most fundamental logical principles that would be sufficient to develop all of mathematics on top of it, reducing all mathematical claims at bottom to logic. And it was built into his system that the general comprehension principle would be correct. He didn't state it explicitly, but it was built into his system that it was true. So for any property, Frege could form a term that represented the set of all instances of that term.
▶︎ 1:25:17 And Bertrand Russell, around that time, was able to look at this work, and he noticed a certain problem with the general comprehension principle. What he observed was the following. The general comprehension principle is false. It is wrong. It is a logical error. It is a kind of a fallacious principle which is logically contradictory, and Bertrand Russell found a very easy refutation of it. So let me give that argument now.
▶︎ 1:26:03 Russell says the following. If we suppose the general comprehension principle is correct, then we can make the following sets. R is the set of all sets X, such that X is not a member of itself. So the Russell set is the set of all sets X that are not self-membered. Now being non-self-membered is a perfectly ordinary property, actually. Because the set of all elephants is not self-membered because it isn't an elephant. It's not a member of itself. The set of elephants is not an elephant, so therefore, it's not a member of itself.
▶︎ 1:26:42 The set of people in this room is not a person at all. It's a set of people, so therefore it's not a member of itself. So most sets have the property that they're not self-membered. It's a quite banal property of being non-self-membered. So Russell says, "Being non-self-membered is a perfectly good property," and so we can make the set of all instances of it, the set of all X, such that X is not a member of X.
▶︎ 1:27:03 And now we simply observe. Look, R we said is a set, and so R is going to be one of those sets if and only if it satisfies the membership requirement, which is that R is not a member of R. So R is a member of R if and only if it isn't a member of R. That's a contradiction. And that argument shows that the general comprehension principle is contradictory. It's a one-line proof, basically. Well, two lines here. If the general comprehension principle were correct, R would be a set, but it can't be a set because we get this contradiction.
▶︎ 1:27:40 And if you think about Russell's argument, you might realize that it's a diagonal argument, this X not being related to X. It's exactly what Cantor was doing in his diagonal thing, the Nth digit is different from the Nth number, and also in the power set argument, the individuals A that are not in their set. But that's exactly what we're doing here. And Russell mentions Cantor in his letter to Frege. He wrote a letter to Frege and said, "By the way, there seems to be a problem with your system because..." and he gave the Russell argument, what's known now as the Russell Argument. The general comprehension principle is a logical fallacy.
▶︎ 1:28:18 And, of course, Frege had, for years, poured himself into this work, this monumental treatise. And Russell's argument completely undercuts the system that he had developed, and it wasn't a minor thing because Frege was using general comprehension. It was woven into everything that Frege was doing. He was, in effect, using that principle over and over again throughout the work, and so this refutation of the system is so devastating that it must have been heartbreaking for Frege.
▶︎ 1:28:59 But to his credit, the work was in press, but he was able to add an epilogue, in which he wrote, "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 was the position into which I was put by a letter from Mr. Bertrand Russell, as the printing of this volume was nearing completion." So Frege acknowledged the seriousness of Russell's objection, and it is taken widely as a refutation now of the general comprehension principle.
▶︎ 1:29:31 To my way of thinking, the general comprehension principle is simply a logical fallacy. It's similar to denying the antecedent, or any of the other logical fallacies that you might have encountered. It has a one-line refutation that Russell provides in his argument, and so we should just think of the general comprehension principle as a naive mistake. It's just wrong, and we should move on to the modified forms of it that are acceptable.
▶︎ 1:30:00 For example, the axiom of separation is one of the axioms appearing in the Zermelo-Fraenkel axiomatization of set theory. And the axiom of separation, it's similar to general comprehension, but it says if you have a set and you have a property, then the set of individuals in that set with the property forms a set. That's almost the same as general comprehension, except what it says is that you have to already have the set, and then you're using the property to pick out a subset of it. And with that modification, it seems totally acceptable, and the Russell argument no longer applies.
▶︎ 1:30:35 Let me continue with a few more allegorical accounts of Cantor's argument, or versions of Russell's argument. One should think of the Russell argument and the various Cantor arguments we've discussed. They're all using the same underlying logic. Let's imagine a town, and there's a barber in this town, and he lives in the town, and the barber shaves all the men in town who don't shave themselves. Let me assume the barber is a man. The barber shaves all men in town who don't shave themselves.
▶︎ 1:31:11 Of course, some people shave themselves. The barber doesn't need to shave them. He shaves the men who don't shave themselves. And now the question to ask is, does the barber shave himself or not? Because I said, "The barber shaves all and only those in town who do not shave themselves." Well, if the barber didn't shave himself, then he should, because that's what we said. He shaves all and only those who don't shave themselves.
▶︎ 1:31:39 So if the barber doesn't shave himself, then he should be shaving himself. But if he does shave himself, then he shouldn't, because he shaves all and only those who don't. So it's contradictory. There can't be such a town and such a barber because it's a contradictory situation, in the same way that the Russell set is contradictory. You can't have a set of all sets that are not self-membered because that set would be a member of itself if and only if it wasn't, in exactly the same way that the barber who shaves all and only those who don't shave themselves can neither shave himself nor not shave himself, because in either case, we get a contradiction.
▶︎ 1:32:12 There's also another kind of example, the barista who happily serves up coffee to all and only those who don't make coffee for themselves. Some people don't make coffee for themselves. They get it from the barista. And some people do make coffee for themselves, and then they don't need to get coffee from the barista. But then the question, of course, is does the barista make coffee for herself or not? So if she does, then she shouldn't, because she makes coffee for all and only those who don't make coffee for themselves. But if she doesn't, then she should. It's exactly the same logic.
▶︎ 1:32:47 And so I hope you enjoyed these examples and this exploration of uncountable infinity. It's such a pleasure, and I hope you enjoyed it. Thank you.