Integers & Reals have different, infinite sizes! **Cantor Diagonlization**

In the first episode of my new cool math series, we looked at integers, numbers like 1, 2, 3, 4, and rational numbers, numbers like 3 5ths or 5 7ths, and we said that these two infinite sets actually have the same size. And what we meant by that, what we meant by saying that infinite sets have the same size, is to say that there was some function from the integers to the rational numbers where every rational number got hit exactly once. And that this notion of a bijective function is what we meant by saying these two different infinite sets have the same size. So now the question is, what about comparing something like the integers and the real numbers, where the real numbers are those that have things like pi and e and root 2 in them. And what we're going to find out in this video is that in fact those two different infinite sets, the integers and the real numbers, do not have the same size. And the argument we're going to be using is one that is due to Cantor, and it is a very famous diagonalization argument, and I'm going to show it in this particular video. The idea is this, let's not try to compare to all real numbers, let's just look at the real numbers that are between 0 and 1. And if it was the case that the integers and the real numbers had the same size, then we could find some function, we could line up the integers and the rationals, and we could pair them in this bijective way. So what I'm going to do is I'm going to try to list all of the different real numbers. Let's just make an infinite list, it'll be a first, a second, a third, and a fourth, lined up with the first integer, the second integer, the third integer, and the fourth integer. Now I'm going to sort of make up which of these real numbers I want to go first and second, they could be anything. How about the first one could be 0.1, that's a real number in between 0 and 1. I'm actually going to go and write it in terms of its decimal expansion after the 0 point. So this looks like a 1 first, and then all the rest 0, 0.1000. Okay, how about for the next one, I'll do 0.333333, a decimal expansion for a third, it's another real number. Then I can do 0.1415926535897932, which is the first bit of the decimal expansion for pi minus 3, it's just kind of fun, I'm just putting some random ones in there. How about 0.99999, so on, this is a decimal expansion for the number 1. And then I'll fill up with 1 7 2 7 3 7 and 4 7s, which have some cool patterns, you can see how that works. But the point is this, I've just chosen these at random, you can choose whatever ones you wish and any other real number that you might imagine we're going to suppose could occur on this list. Now, what I want to argue is that no matter how you did it, no matter what choices I made, or what choices you made for how we try to line up the real numbers and the integers, no matter how we did this, that we could not get all of the real numbers. So now I want to draw your attention to these so called diagonal entries. It's looking here at this first digit, the 1 10th spot in the first particular row, the first real number we've identified, and then it's going to go down and it's going to go and look at the second digit in the second real number, the third digit in the third real number, the fourth digit in the fourth real number, and so on. It's this diagonal that we have here. What I'm going to do is I'm going to make a new real number that tweaks along this diagonal. So the 1 that we have here, I'm going to go and change that 1 and make it a 2. Then I look at the 3 that we have, that's in the second row in the second location, and the 3, I'm going to add 1 to it and make it a 4. The 1, I'm going to go and add 1 to it, make it a 2. The 9, I'm going to add 1, but instead of making it a 10, I'm going to cycle around and make it a 0. So the 9 is going to become a 0, the 5 is going to become a 6, the 4 is going to become a 5, the 4 is going to become a 5, and the 7 is going to become an 8. And what we have here is a new real number. This real number is not on the list. It's different from the first one, it's different from the second, it's different from the third. So no matter how you went about choosing your list of real numbers, we can always construct this new real number that's different from whatever listing you might have given. And so this tells us that it is not possible to find a function from the integers to the real numbers that has this property that every real number gets listed exactly one time in association with the integers. There's not a bijective function between them. And so what this says in truth is that the integers and the real numbers, that they have a different size, that you cannot align them in this way. Now we have some terminology for this. When you have an infinite set and you can line it up with the integers, where there's a first, second, a third, and so on, we're going to say they're countable because you can align them with the counting numbers and there's a fancy math symbol called aleph-naught for it. And so what we saw in the first cool math series video was that the rationals were countable. They were aleph-naught because you could line them up in this way. You could say that there was a first, a second, a third, and a fourth rational number. And that was the construction we gave. But here in this video we've shown that you cannot do that for the real numbers no matter how you try to line them up. This counter-diagonalization argument destroys the ability to make them countable. And so we say that this set is uncountable. And I want to leave you with just one final thought. We found this set that was countable, like the integers or the rational numbers. We found this set that was aleph-one that was uncountable, for example, the real numbers. But is there a set that's in between these sizes? Is it possible that there could be some set that its size was snuck in between this aleph-zero and this aleph-one? And this, it turns out to be a very deep and challenging question, but I'm going to let you think about it. All right, that is it for our second episode in the cool math series. I'm having a lot of fun making them. I hope that you're enjoying watching them. If this is something you want to see more of, because they're not connected to one of my classrooms, they're just for fun, leave it a like. I really appreciate seeing your responses to this. And stay tuned for the next video.