▶︎ 0:00 Hi, I'm Joel David Hamkins, and I'd like to tell you about the Parable of Hilbert's Hotel. I'm a New Yorker, and I noticed one day this giant hotel going up across the street. And it had infinitely many rooms in it. Actually, it was quite an elegant hotel. Each suite was a full-floor suite, so it had room zero in the bottom and room one, room two, room three, and so on.
▶︎ 0:23 There was no top room. It just kept going, like the natural numbers. And the thing about this hotel is that it was completely full of guests, actually. In every single room, there was a guest occupying that room.
▶︎ 0:37 But meanwhile, a new guest came up, wanting to check in to the hotel, but it was completely full, so there's no room available. And he went to the manager, and the manager pondered the request a bit and said, "Hang on. Just give me a second." The manager was able to accommodate the guest, even though the hotel is completely full. And the way that the manager did this was by sending a certain message to all of the current guests.
▶︎ 1:05 You see, when they had checked in, they had to sign the form, and there's this fine print and so on that the manager might ask them to change rooms at a certain point during their stay, and they were obligated to do that. And so what the manager told them to do was the guest in room N should move to room N plus one. So everyone moved up one room. So the person in room zero moved to room one, and the person in room one moved, at the same time, to room two. And the person in room two moved to room three, and so on.
▶︎ 1:35 So everyone shifted up a room, and there's no top room or anything, because these continue without bound through the natural numbers. So everyone got a new luxurious room, private room. We don't want to ever double people up in this hotel. So everyone still has their own room, but now, after this transformation, room zero is empty because no one moved into room zero, and so the new guest could be accommodated in room zero.
▶︎ 2:05 Well, the next weekend, I'd noticed that there was a large crowd of a thousand people outside the hotel. And still, all the current rooms were occupied, but now we had a thousand people. They all arrived at once, and they wanted to check into the hotel. And the manager said, "Just a second."
▶︎ 2:25 And so he was able to accommodate those 1,000 people simply by issuing the instruction to all of the current occupants of the hotel that the person in room N should move to room N plus 1,000. So if everyone shifts up 1,000 rooms, then they still have their own private room. Yes? Because that's a one-to-one function from the natural numbers to the natural numbers shifting up, and it vacates all of the first thousand rooms. And so those rooms become available for the new guests, and they can check in to the hotel. So in this way, even though the hotel was completely full, and a thousand new guests came, the manager was able to accommodate everyone into the hotel anyways.
▶︎ 3:10 The next weekend, I noticed this certain thing. Let me draw my picture here, I think. It was Hilbert's bus had arrived. And Hilbert's bus is very big bus, and it has infinitely many seats in it. So there's seat zero, seat one, seat two, seat three, seat four, and so on. And the bus was completely full. There was a person in every single seat of the bus.
▶︎ 3:50 And all of those people on Hilbert's bus wanted to check in to Hilbert's Hotel, but the hotel was full. So how can the manager accommodate everyone on Hilbert's bus by checking in? He needs to make room. We can't do this trick anymore of shifting up by the number of new guests, because we would have to shift up infinitely in order to accommodate all infinitely many. Before, we were able to accommodate a thousand people by shifting up by a thousand, but it doesn't make sense to shift up by infinitely because every room number is a finite number. And so if we add infinitely to one of the numbers, there is no such room. It doesn't make sense to talk about infinity plus two as a room in the hotel. There is no such room.
▶︎ 4:33 So how can I accommodate the passengers on Hilbert's bus, even though the hotel is full? That's the kind of puzzle that I encourage you to think about. Maybe you want to stop the video and think about how you would solve it. But meanwhile, I'll tell you how I like to solve it. One thing that the manager can do is to instruct the person in room N to go to room 2N. So everyone should double their room number.
▶︎ 5:02 So the person in room zero, they stay in room zero. Person in room one goes to room two, the person in room two goes to room four, the person in room three goes to room six, and so on. So if you notice that the old guests, the current guests of the hotel are going to be occupying the even-numbered rooms after we do this transformation. So we move the current guests to the even-numbered rooms, and therefore all of the odd-numbered rooms are empty.
▶︎ 5:29 And so the manager has to say where the person in seat S goes to, which room should the person on the bus in seat S, which room should they check into? And what they can do is check into, we want it to be an odd room, so we should just use the next available odd number. So we can use 2S plus one. That's an odd number. Starting with zero, we put the first guest in room one, and the next guest from seat one goes into room three, and the person in seat two goes into room five, and so on.
▶︎ 6:03 And in that way, we put the bus passengers into the odd-numbered rooms, and the current guests, the previous guests, are in the even-numbered rooms, and everyone is accommodated in the hotel. We didn't double up any passengers because none of the bus passengers are occupying the same room as a previous guest because the bus passengers are all in the odd-numbered rooms and the previous guests are all in the even-numbered rooms. And every individual seat number gets mapped to its own private odd number here, and similarly, this is a one-to-one function. And so therefore everyone, the old guests of the hotel and also the bus passengers get their own private suite in Hilbert's Hotel. That's fine.
▶︎ 6:51 The next weekend, a certain event occurred, namely, let me draw it here. If you can guess, maybe you can guess. Of course, it's Hilbert's train arrived. And the thing about Hilbert's train is that it has many, many train cars. So there's car zero, and car one, and car two, and car three, and so on. Infinitely many train cars.
▶︎ 7:28 But furthermore, each train car is like Hilbert's bus and it has infinitely many passengers on it. So there's seat zero, seat one, seat two, seat three, seat four, and so on. And also on this car there's infinitely many passengers. Seat zero, seat one, seat two, seat three, and so on. So every train car has infinitely many passengers. And furthermore, we have infinitely many train cars and they all want to check in to Hilbert's Hotel.
▶︎ 7:56 In a sense, each train car is like an entire copy of Hilbert's Hotel, because there's just as many passengers in each car as there are guests at the hotel currently. So we have basically infinitely many Hilbert's Hotels and I want to cram them all in to one Hilbert's Hotel. So the manager says, "Well, hang on. I can accommodate you. Just give me a second."
▶︎ 8:21 And so what did he do? Maybe you want to think about how you're going to do it. I can get us started. We have to say the manager has to direct the current guest in room N, which room should they go to? And also, the manager should say the person in car C, seat S, which room should they go to?
▶︎ 8:48 Well, one thing that we can do that we already did with the Hilbert's bus situation is that we can easily free up infinitely many rooms in the hotel by freeing up the odd-numbered rooms. So for example, we could direct the current guest in room N to go to room 2N. So that's an even number. We double everyone's room number again. That frees up all the odd-numbered rooms, they're now empty.
▶︎ 9:11 And so I have to put the train passenger in train car C and seat S into an odd-numbered room. But I want to make sure to do it in a way that's not doubling anyone up, because of course the whole policy of this hotel is that everyone gets their own private full floor suite. So if you want to think about it on your own, then please do. But maybe if you've joined us again, I can tell you one way to answer it.
▶︎ 9:39 There's actually infinitely many different ways to answer this question. But there's one easy way, and that is the manager can direct the passenger in train car C, seat S to go to room 3 to the C times 5 to the S. So this is one sort of slick way to solve the problem.
▶︎ 10:01 First of all, I can notice that this is definitely an odd number because three and five are odd numbers, and so their powers are odd numbers and the product of two odd numbers is still an odd number. I don't have any two in the prime factorization of this number, so therefore it's an odd number. So I've put every train passenger into an odd-numbered room, which is available, but now the question is, have I doubled anyone up? So have I put two different train passengers into the same odd room number?
▶︎ 10:33 And the answer is no. Precisely because of the uniqueness of the prime factorization. So whatever room number value this is, it has a unique factorization as product of primes. And those products of primes will have a certain number of threes in it and a certain number of fives in it. And so therefore, if you tell me the room number, the value here, then I can tell you which train car they came from and which seat they were in because that's exactly the exponents of three and the exponent of five in the prime factorization of that room number.
▶︎ 11:05 So it's precisely because of the uniqueness of the prime factorization that this is a one-to-one map from pairs of numbers into individual numbers. And so in this way, even though we had infinitely many train cars each with infinitely many passengers, we can fit them all into the Hilbert's Hotel without doubling up any train passengers or interfering with the previous guests. It's quite amazing.
▶︎ 11:35 The next weekend, let's erase this here, there was a huge crowd of runners. They were there for the big race, the half marathon race. I'm not going to draw them all here, but they were all densely ordered amongst themselves because they all had numbers on their jersey, the running number for the race. And every number was a fraction P over Q. So there was runner one half, and runner one half, and three quarters, and five seventy-seconds, and so on. All the positive fractions were appearing on a racing bib.
▶︎ 12:20 These runners all wanted to check into the hotel. They're running the half marathon, not the full marathon, because they really like fractions. So, can the manager accommodate all of the positive rational numbers into Hilbert's Hotel? The question is, how can we put all of these runners into the hotel? I encourage you to think about it on your own, but maybe if you've rejoined us now, you might realize that actually the half-marathon situation with these fractions, P over Q, is actually very similar to the Hilbert's train case, which also had two numbers. Because here every runner has two integers, P and Q, the numerator and the denominator. And similarly, in the Hilbert's train case, we had the car number and the seat number.
▶︎ 13:09 And so actually, this situation can be handled in much the same way that we handled the train car case. So we can put the current guest from room N into room 2N, yes, and then we put runner P over Q into room, well, we need to put that runner into an odd-numbered room, and we have these two numbers, the numerator and the denominator, but again, we can just use the prime factorization trick. So we could use, say, 3^P times 5^Q, and then because of the uniqueness of the prime factorization, if you tell me the room number that a runner landed in, I can tell you what their fraction was, because their numerator will just be the exponent of 3 and their denominator will be the exponent of 5 in the prime factorization of that number, of that room number. Therefore, we never put two different runners into the same room, because we can recover the fraction from the room number itself using the exponents.
▶︎ 14:09 It's an interesting problem to think about. If we did this room assignment, then, in fact, we haven't used all of the rooms. There are some empty rooms remaining. For example, the room 13 is empty, because it's not even, so it's not one of these, and it's not of this form, because 13 is a prime number. And so maybe you want to think about, what's the first room that's empty after we do this transformation?
▶︎ 14:36 Room zero is even. All the even rooms are occupied. Room one, does it occur here? Well, it does occur if P is zero, then maybe if we allowed, if there was a runner zero, but actually I said positive rationals, didn't I, earlier, I said all the positive rationals occur. And so there isn't, and so P equals 0 never happens, and so there's nobody in room one. Similarly, well two is occupied, three is occupied if we do 3^1 times, no, actually three is not occupied either, if we have positive, because Q, first of all, has to always be positive. And so one can, in this way, analyze exactly which rooms are occupied and which are not, depending on whether they can be written in this form or not.
▶︎ 15:22 What Hilbert's Hotel is about is the concept of countability. A set is said to be countable basically if it fits in Hilbert's Hotel. A set is countable when it can be placed into one-to-one correspondence with a set of natural numbers. But placing a set into one-to-one correspondence with a set of natural numbers is exactly a room assignment function for that set. You tell each individual from the set, gets assigned a number, and that's their room number. Therefore, I think it's correct to say a set is countable if it fits into Hilbert's Hotel.
▶︎ 16:00 This includes all of the finite sets, because obviously any finite number of people fits into Hilbert's Hotel. We want to include finite sets amongst the countable sets. Sometimes people say countable, but they really mean countably infinite. Some countable sets are finite. The finite sets count as countable. They fall under the definition of being countable. But then the infinite sets are said to be countably infinite.
▶︎ 16:27 A set is countably infinite if it's infinite and yet still fits into Hilbert's Hotel. The train car passengers is a countably infinite set. The Hilbert's bus passengers is a countably infinite set. The runners, the set of fractions, is a countably infinite set, because all of those sets fit into Hilbert's Hotel.
▶︎ 16:46 There's another way to think about a set being countable. Namely, if you have a non-empty countable set, then you can enumerate the set. If A is countable and non-empty, then I can enumerate the elements of it in a sequence like this, A4 and so on. If it's a finite set, I could enumerate like that with repetition. If it's an infinite set, then I could enumerate it like that without repetition. But in any case, every non-empty countable set can be enumerated on a list indexed by the natural numbers. That's a quite robust way of thinking about the concept of countability.
▶︎ 17:39 Let's think about the nature of countable sets. What kind of closure properties do countable sets exhibit? If I have a countable set and I add one more element to it, then I claim it's still a countable set. But this is just the basic Hilbert's Hotel situation, because we had a countable set of the current occupants of the hotel, and we had one more guest, and yet we were still able to fit all of those people together into Hilbert's Hotel by shifting up and putting the new guests into the bottom. So therefore, if you have a countable set and you add a new element, then the resulting set is still countable.
▶︎ 18:17 That's easy to see also with this enumeration idea, because if I have a list of numbers exhibiting that this set is countable and non-empty, and if I have one more element, say little b, then I can enumerate the new resulting set. I could just put b in front, and that would be an enumeration. I would have to adjust all the indices if I wanted to number these elements. But the point is that if I have a countably infinite set or a countable set with repetition and I add one point, then I can put that set also on a list just by adding the new element to the front.
▶︎ 18:51 There's another closure property that the countable sets fulfill, and that is, if you have two countable sets, then their union is still a countable set. And this is just exactly the Hilbert's bus situation, because we had the first countable set of the occupants of the hotel, and the second countable set was the bus passengers, and yet the union of all those people still fit into Hilbert's Hotel. And so what that shows is that if you have two countable sets, then their union is still a countable set, and we can exhibit that with this enumeration concept just as well.
▶︎ 19:26 So if I have one countable set and I put it on the list, A0, A1, A2, A3, and so on, and if I have another countable set, B0, B1, B2, B3, and so on. So I've got these two enumeration lists showing that the two sets are countable. Then I want to put the sets all together into one list that shows that the union set is countable, but I can do that simply by interleaving. So I can take the first element from the first one and then the first one of the second one, so A0, B0, A1, B1, A2, B2, and so on, A3, B3. So I've taken all of these points, all of these individuals from those two separate lists, and I made one list by interleaving the two sequences together, and that shows that the union of two countable sets is also a countable set.
▶︎ 20:21 That's exactly the same thing that we did when accommodating the Hilbert's bus. Because if we think of the As as the current hotel occupants and the Bs as the bus passengers, then what we did was we put the current hotel guests into the even-numbered rooms just as they appear here, every other one. And we put the bus passengers into the odd-numbered rooms, every other one starting after that, in between those other ones. So this interleaving idea is exactly what we did when we solved the Hilbert's bus problem.
▶︎ 20:54 The union of two countable sets is countable. It follows from that, for example, that the integers, meaning the natural numbers together with the negatives, is a countably infinite set. I can see that, so if I have the integers, they're usually denoted by the double struck Z symbol. It has 0, 1, 2, 3, and so on, all the positive natural numbers, but also the negatives, -1, -2, -3, and so on.
▶︎ 21:27 It doesn't have the right form to be a list in this sense, because I said a set is countable if you can put it on a list that's indexed by the natural numbers, but this list is infinite on both sides. But the point is that I don't really need to do it like that, because I can do this interleaving trick. I can take the natural numbers themselves, that's a countably infinite set, and I can take the set of negatives, so I might call it Z minus, the set of negative integers. But that's also a countable set, a countably infinite set, because I could take this part of the list and just turn it around, and then it's being enumerated like the natural numbers.
▶︎ 22:07 And so I've got two countably infinite sets, and their union is therefore countably infinite. Or I could just show you the list that interleaves them. I could take zero and then one, -1, two, -2, three, -3, and so on. This is an enumeration of all of the integers, not in the usual integer order, but in this other order, and that's fine. It shows that the set of integers is a countable set. All right, let's keep going.
▶︎ 22:40 What would be the analog of the Hilbert's train situation? With the idea of aiming towards that, let me consider a slightly different version. Let's think about pairs of natural numbers. If I think about the natural number lattice, we have zero, one, two, three, four, and so on. And for the rows, zero, one, two, three, four, and so on. I'm talking about N cross N. These are the natural number lattice. The grid points in this lattice is what I'm focused on.
▶︎ 23:34 For example, this point here is the point 3, 1 because the X value is 3 and the Y value is 1. And this point up here is 1, 3, because the X value is 1 and the Y value is 3. Every grid point here in this lattice is corresponding to a pair of natural numbers, N, M. Now, I want to know, how many grid points are there in the natural number lattice? In other words, how many pairs of natural numbers are there?
▶︎ 24:06 There's a variety of ways to solve this problem. I could just go directly and use the Hilbert's train solution that we had before. I could assign each pair to the numbers, say, 3 to the N times 5 to the M. And that would be a one-to-one correspondence of the pairs of natural numbers with individual natural numbers, and it's a one-to-one correspondence precisely, again, because of the uniqueness of the prime factorization.
▶︎ 24:35 There's another way to do it, however. Let's talk about a more geometric way. I have these grid points here, and what I'm going to do is describe a certain way of enumerating the grid points. I'm going to start at the origin here, and I'm going to follow a certain windy path. I go like this, and then I double back this way. You notice how I'm going through all of the grid points on the way, in this diagonal manner.
▶︎ 25:08 I have this windy path that's going on the diagonals, successive diagonals. And the point is that I'm going to hit every grid point eventually if I just go back and forth on those diagonals. No matter what grid point you have, I'm going to reach it at some point, and I can simply enumerate the grid points as they appear on this path. This would be corresponding with zero, and then one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, and so on. I associate each grid point with the number of earlier points on the path, so its place on the path.
▶︎ 25:45 This would be the zeroth point, and the first point, the second, and so on. This is a way of assigning to every grid point a natural number. It's similar to this kind of solution. What that shows is that the number of pairs of numbers is the same as the number of numbers, so they're both countably infinite. So, there are countably many pairs of natural numbers.
▶︎ 26:12 There's a slight improvement to this windy path argument that Georg Cantor came up with, and so let's talk about that briefly. I guess I want to draw a different version of this. Here's the natural number lattice again. I'm talking about the grid points that arise from natural numbers, so it's these intersections of this grid that I'm talking about, so zero, one, two, three, four, and so on. Zero, one, two, three, four, and so on.
▶︎ 26:54 And now, for this Cantor method, instead of going up and down on those diagonals, I'm always going to go up. I start with this point, and then I go like this, and then I follow the next diagonal up, and then I follow the next diagonal up, and so on. At every point, maybe I arrive at a certain point by having traversed the earlier diagonals going up, but I don't go back down. I skip over to the next diagonal and follow it going up. And if I do that, and I associate the first point with zero and then one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, and so on, this point would get attached to the number twelve, and so on.
▶︎ 27:41 As you go on, every point in the lattice is going to get a natural number that's attached to it depending on this scheme, and that will be a one-to-one correspondence between pairs of numbers and natural numbers. But the interesting thing about this way of doing it is that actually we can write down a certain formula, a polynomial equation, that exactly exhibits the bijection, the one-to-one correspondence between the natural numbers, the pairs of natural numbers, and the natural numbers. This is the genius of Cantor's argument. If I have two natural numbers, X and Y, maybe it shows up in a certain point here, X and Y, and I think about how many points were preceding this point. If you think about this diagonal here, it has one point on it, and this diagonal has two points on it, and this diagonal has three points on it, so the number of points on earlier diagonals is one plus two plus and so on up to X.
▶︎ 28:46 I'm sorry, not up to X. Up to X plus Y. Because on this diagonal, X plus Y is one, and so the earlier one is adding up to one. On this one, X plus Y is two. This is X plus Y equal three, and so on. So the number of points on earlier completed diagonals is this sum, one plus two plus three plus four and so on, all the way up to X plus Y, which is the previous diagonal, and then how many points precede this point on the unfinished diagonal? Well, it's just going to be the value of Y, because when Y is zero, there's nothing before it, and when Y is one, there's one point before it. When Y is two, there's two points before, so we should just add one more Y here.
▶︎ 29:33 But now the thing is that this formula here, adding up all the numbers, one plus two plus three and so on, up to this number, X plus Y, this is a triangular number. And there's a famous formula that we can write down for the value of that sum, which is just X plus Y times X plus Y plus one, over two. So therefore, I'm mapping every grid point XY to the number of earlier points on the path that's described here, and it's exactly given by this formula, so I'm going to map that point to the quantity X plus Y times X plus Y plus one over two plus Y. And this is polynomial in both X and Y, and it is a one-to-one correspondence between pairs of numbers and natural numbers.
▶︎ 30:25 Our previous solution using the three to the X, five to the Y, that wasn't actually a one-to-one correspondence between these sets, because many numbers were missed on the other side. And furthermore, that formula isn't a polynomial, it's exponential in both X and Y, whereas this is a polynomial expression in X and Y. We could multiply this out, we're going to get X squared and an XY term and so on, Y squared. So it's a nicer formula. This is called the Cantor pairing function. A pairing function is a function that takes pairs of objects and gives you back individual objects in a way that is a one-to-one correspondence, so that's exactly what we've done here.
▶︎ 31:11 Let's return to the question of the rational numbers. What I claim is that the set of rational numbers is countable. Of course, we know that already because we already put the half marathon runners into Hilbert's Hotel, and to be countable means to fit into Hilbert's Hotel, or to be equinumerous with a set of natural numbers.
▶︎ 31:31 But let's think about it more directly. And the way we can think about it directly is every rational number, every positive rational number is determined from two natural numbers, P over Q. So we have the fraction written as P over Q, but it comes essentially from a grid point in this upper quadrant of the natural number lattice. Every positive rational number can be thought of as landing on this lattice somewhere, and we already showed that the whole of the lattice points is a countable set because it's equinumerous with N.
▶︎ 32:05 And so therefore, the set of fractions, the set of positive rational numbers is also a countable set. There's another thing to realize here about what we've done, and that is,
▶︎ 32:20 So far we've observed these closure properties of the countable sets. Namely, if you have a countable set, even a countably infinite set, and you add one more point to it, it's still a countable set. We also observed that if you have two countable sets and you take their union, you put all those individuals together, then that makes a countable set. But what I claim now is that if you have countably many, countably infinitely many countable sets, then their union is still a countable set.
▶︎ 32:49 So let me write that out here. Suppose that we have A0, A sub-0, A sub-1, A sub-2, and so on, and they're all countable. So I have infinitely many countable sets. Then what I claim is that the union of those sets, if I take all the individuals all together and put them all into one set, the union is a countable set. Maybe it's a bit surprising to think that you could take infinitely many countable sets and put them all together and it's still just countably infinite, but in fact that's totally right.
▶︎ 33:40 And if you think about it a little more, you might realize, "Well, actually this is just what we did with Hilbert's train," right? We had the separate train cars, and we put them all together into Hilbert's Hotel. So the union of the train car passengers is a countable set because that's exactly what we did with Hilbert's train.
▶︎ 33:58 Or we could think about it in terms of this lattice, the natural number lattice that I've drawn now a number of times here. So here's zero, one, two, three, four, and so on. Zero, one, two, three, four, and so on. If I think about these columns, this column has infinitely many grid points on it. So let's take A0, which is a countable set, and put A0 into that first column.
▶︎ 34:28 And I'm going to put A1 into this column on index one, and A2 into the index two column, and so on. So I can put these sets, A sub-N onto the Nth column. So each set gets its own private column, but now we prove that the number of grid points altogether is still just a countable set. We have three or four different proofs of that now. And so therefore, the union of the individuals is still just a countable set.
▶︎ 34:55 There's a very subtle point that I want to make about this union claim, because what I said is that if you have countably many countable sets, then the union is a countable set. And that's true by the argument that you gave, but I actually snuck something in there because I made an appeal at a certain point, without mentioning it, to the axiom of choice, yeah? Which we're going to talk about in another lecture. But in fact we know that you need the axiom of choice to prove that the countable union of countable sets is countable.
▶︎ 35:32 And the choices that were made, maybe it was subtle because it seemed like, well, where's the choice? I know the grid points are countable because I have a formula, that Cantor pairing function is a formula that is a bijection between the pairs and the numbers, and so that doesn't need any axiom of choice. I'm not making any choices there. Each of these sets is countable, and so each of these sets can be laid off onto the columns, and so it doesn't seem like there's any use of the axiom of choice, in the ability for any one set here to put it onto a column.
▶︎ 36:05 But maybe if you think a little bit more subtly about exactly that feature, there's actually a lot of different ways to put a given countably infinite set to lay off the elements onto a given column. So what I needed to do was, for each one of these sets, I needed to pick a particular way of laying it onto that column, and that's using the axiom of choice, because amongst all the, if one of these is, say, countably infinite, then, in fact, there's an enormous possible number of ways of putting that set onto that column, and I should pick just one.
▶︎ 36:42 So for each n, I'm picking a particular way of seeing that it's countable and putting it onto the nth column. And so, that's an appeal to the axiom of countable choice, because for each n I'm picking a way of putting it onto the nth column. And then once I have all those choices made, only then do I get to invoke Cantor's argument about the winding path, or the pairing function, to see that the union is countable. And in fact, we can prove that this subtle point is necessary because it's consistent, in fact, with the axioms of set theory without the axiom of choice that the union of countable sets is not necessarily always countable.
▶︎ 37:26 Let me consider a slightly revised version. Here, we proved that the natural numbers, that the pairs of natural numbers, forms a countable set. We can revise that slightly like this. What I claim is that if A and B are countable, then A cross B is countable. So A cross B means the set of pairs, AB, where A is in A and B is in B. The Cartesian product of two sets is the set of pairs.
▶︎ 38:12 We could maybe just forget all the parentheses and so on. We could just write it as, with juxtaposition here, where I just write an element of A next to an element of B, that's what I mean by A cross B, if I think about it like that. I've got two objects, the first one is in A and the second one is in B. So in a sense, A cross B is like the two letter words whose first letter is from A, and whose second letter is from B. If I think of the elements of A and B as letters in an alphabet, maybe an infinite alphabet.
▶︎ 38:46 So the claim is that if A and B are countable, then the set of two letter words, the cross product, is also countable. The Cartesian product, I mean. But this is easy to see, because if A and B are countable, then they're each equinumerous with a set of natural numbers, and so therefore this is equinumerous with a subset of the natural numbers across the natural numbers. And so this is an immediate consequence of the previous observations that we made about the natural number lattice. But now I want to do something interesting with this word idea.
▶︎ 39:24 Suppose I have a countable set, let's say A is a countable set, and I'm gonna think of the elements of A as letters, and I'm gonna make words of any length, not just length two, but all the lengths. So this is usually denoted by A star, so this is the set of all finite words using letters in A. And usually mathematicians when they talk about, so they're using this word "word," it just means any finite sequence from A, so it's not like the word in the English language is something. We have our alphabet with 26 letters, and the English language has words, but not every sequence of letters counts as a word in English. For example, I could make the sequence of letters, that was Z, Z, Y, Q, P, or something like that, and that wouldn't be a word in English, but it would be a word in this sense.
▶︎ 40:32 And also, in this sense, I also allow the empty word, it's one of the words, that's a sequence of like zero. It has no letters in it. That counts as a word. There's all the one-letter words, and the two-letter words, and the three-letter words, and so forth. They all count as words in this language. And the claim is that A star is countable. So the set of words, the set of finite words in a countable set of letters is a countable set.
▶︎ 41:09 So let's do that argument. So if I think about A, I can identify the individual letters with the words of length one. There's a subtle point there. Are they the same thing? If I have a sequence of length one, is that the same thing as having a letter? Well, I don't know, because we don't talk about the length of a letter, though we might talk about the length of a sequence of length one, because that has length one. And so one might wanna make distinctions between the object that's on a sequence of length one versus the sequence of that length.
▶︎ 41:48 For example, I'm a person, but what about the sequence that has one element that is me? I don't think I'm the same thing as that sequence, because I don't think I'm a sequence at all. I think I'm a person, and not a sequence. But the sequence consisting of me as its only entry is a sequence of length one, and the only entry of that sequence is a person. So maybe we don't wanna identify letters with words of length one, because a word, by definition, is a sequence that has a certain length.
▶︎ 42:17 But clearly we have a one-to-one correspondence between the set of letters and the set of words of length one, and so maybe I wanna think about, say, A to the one, it would be the sequences of length one, those would be the words of length one. So then I could have the two letter words, which I might denote by A squared. That's A cross A. A to the one, the one letter words, is a countable set because there's only countably many letters. A squared, those are the two letter words. That's a countable set because it's the product of two countable sets, and we said that if you have two countable sets, then the set of two letter words you make by using them is a countable set. So, this is a countable set.
▶︎ 43:02 What about the three letter words? A cubed. Well, that's A cross A cross A. But I could think of it like this. I get every three letter word by taking a two letter word and putting a letter on the end. So, this is the product of two countable sets, namely A squared is one countable set, and A is another countable set, and so therefore the set of three letter words is also a countable set. And so on, we can just keep doing this. A to the N is still a countable set, because I get it by just taking a product of A with the previous set, which is still a countable set.
▶︎ 43:41 A star is the set of all finite words, so those are the words that end up in one of these sets. I also have A to the zero, which is just the empty word, which is usually denoted by this variant epsilon symbol. This means the empty sequence, the word that doesn't have any entries in it. Every word is in one of these, because if it's an n letter word, then it's in the nth set. Here's the length zero words, the length one words, length two, length three, and so on. So, the union of all of these sets is precisely the set of all finite words in the language, and that's A star.
▶︎ 44:20 But now it follows from our general fact that if you have countably many countable sets, then the union is a countable set, and that's precisely what we have here. So, A star is the union of these countably many countable sets, and therefore A star is countable. So, there are only countably many words in a countable alphabet. Even if the alphabet has infinitely many letters, it would be a countably infinite alphabet. Still only countably many words.
▶︎ 44:51 Another way to give this proof. So, suppose I have a countable alphabet, this is an alphabet, and it's countable. So, I have letters A zero, A one, A two, A three, and so on. Maybe it's countably infinite. Then, a word in A star is a sequence of such letters. So, I can write it as, say, it's gonna pick out one of these letters, say, A sub K zero, A K1, A K2, A K3, and so on, up to A K N. So, each letter in the word is one of these letters, and it has some index, and this is the zeroth letter of this word, so W.
▶︎ 45:45 If I have a word W in A star for this alphabet, then it's a sequence of letters, and those letters each have an index in that enumeration of A. And now I can think about that word W and send it to a certain natural number. It's sort of like putting the words into Hilbert's hotel. We want to show the words are countable, and so what I want to do is specify a natural number, its room number, if you like, to think about the hotel. I want to assign this word to a number that could be its room number in a one-to-one way so that different words get different rooms.
▶︎ 46:21 And now maybe one thing that you could do is take, use the prime factorization idea that we used before. Namely, you might want to try three to the K0 times five to the K1 times seven to the K2 times 11 to the K3 and so on. And here I would have the Nth prime to the K sub N. So, I'm only using prime numbers here in this factorization, and so that's going to be, you might think, a one-to-one map precisely because of the uniqueness of the prime factorization, but there's a very subtle point that happens right at this moment in this argument, because in fact, it's not a one-to-one map as I defined it here.
▶︎ 47:08 You might say, "Well, it's just like the Hilbert's train argument that you did with three to the C times five to the S," but there's a certain subtle point here, and that is that, because I started the alphabet indexing at zero, it means that some of these Ks might be zero, and in particular, the last one might be zero, in which case I'm raising that prime to power zero, which means it isn't really there. And so therefore, if I take this as my account of what I'm doing, and I have allowed the number zero to occur as an index, then I can't tell if A sub-zero occurred at the end. If there was an index zero letter appearing at the end, I would be multiplying by one, by that prime to the power zero, which is one, and therefore I would get the same number whether it was there or not, and that is a violation of the one-to-one correspondence.
▶︎ 48:09 There's an easy fix for this. One fix is, look, just start your enumeration at one, and that way all of the exponents will be positive, and then we will have uniqueness of prime factorization, because given any number that arises this way, I can look at it and see exactly which letters have appeared in the sequence. So therefore, in that way, I can solve it. Another way to solve it is, even if you want zero to be a letter, you could just multiply by a prime factor here, that's indicating the length, as sort of like a stop character that tells you how long the sequence was, how long the word was.
▶︎ 48:49 So the situation is that we've assigned every word in the alphabet, I mean, in the set of words, we've assigned every word to a particular number, in a one-to-one way, because now, if all the exponents are positive, I can recover that sequence of exponents, and therefore I can recover the sequence of letters that I used to make the word, and so I can recover the word. So it's never the case that two different words are getting mapped to the same number. So this is just a different way, a different kind of argument, that's sort of unraveling the previous argument that I had given about the countable union of countable sets. The upshot is that the set of words, the set of finite words in a countable alphabet, is countable.
▶︎ 49:35 Let me conclude with a little bit of foreshadowing, and that is, I wanna go back to Hilbert's Hotel. If you remember, we had infinitely many rooms in Hilbert's Hotel. There was room zero, room one, room two, room three, and so on. Zero, one, two, three, four, and so on.
▶︎ 50:01 And the next weekend, after all the previous guests had been accommodated from the bus and the train and the marathon, well, this hotel, it happens to be on the water. So, I noticed, I apologize for my picture here. There was an ocean liner, Cantor's Cruise Ship pulls in to the hotel, and Cantor's Cruise Ship is full of guests, full of passengers. Every passenger on Cantor's Cruise Ship has a ticket with a serial number on it. And what are those numbers? Well, they're real numbers.
▶︎ 50:52 So they have passenger, of course, there's all the integer passengers. I think that's the elite first class on the cruise ship. If you have number zero, one, two, three, and so on, those are the best numbers to have. But then there's also people with fractions, one-half, three-fourths, and so on, and maybe the negatives as well. But then there's also zero, one, two, three, and so on, and also fractions, one-half, five-sevenths, and so on.
▶︎ 51:16 But also, we have the algebraic numbers, like square root of two, there's passenger square root of two, and passenger cube root of five, and so on, all of those numbers. But more than that, there's the transcendental numbers, the passengers with number pi and e and so on. Every real number is the serial number of a passenger on Cantor's Cruise Ship, and they all want to check in to Hilbert's Hotel. And the captain goes to the manager and says, "Hey, can you accommodate us?"
▶︎ 51:47 And that is the puzzle that I want you to think about, and we will return to it in the next lecture. So please think about it, and then we'll discuss what Cantor had to say about that. Thank you very much.