Cantor's Theorem: Proof & Diagonal Argument | MIT 6.042J

[00:00:00]so it's time to examine uncountable sets and that's what we're going to do in this segment so Canter's question was are all sets the same size and he gives a definitive answer of no uh Canter's theorem which we're about to present will show that in fact there isn't any biggest Infinity for any given Infinity you can find a bigger one in a very simple way um but let's begin by coming up with a the simplest form of Cancer's diagonal argument uh of how do you prove that a set is not countable well remember a set is countable if you can list it possibly with repeats so a is countable if there's a sequence a z A1 A2 such that every element in the set a shows up at some time or other in the list possibly more than once uh and the only things in the list are elements of a uh and we saw as an example that the finite bit strings the finite strings of zeros and ones uh or the finite binary words are a an example of accountable set and like we claimed last time and now we're about to prove that the difference is that if you look at the infinite bit strings the oneway infinite they have a beginning and they go on infinitely to the right the notation being 0 one to the Omega where Omega is an indication of one of the symbols for kind of Infinity uh and this is going to be an example of an uncountable set how are we going to prove that well uh the setup for uh using a diagonal argument is to think about drawing a matrix suppose that I have some way of enumerating the infinite binary sequences the in 0 one to the Omega so there's a sequence s0 there's a sequence S1 there's a sequence S2 let's lay them out as though they were the rows of a matrix so s0 is this infinite binary sequence 0 0 one zero so on um and uh the column labels are simply the coordinate labels for s0 so this is s0 0 S01 and so on um S1 is the next um uh infinite binary sequence in this hypothetical list uh and it starts 0 one one zero and goes on and so on down the line so the row labels are this enumeration of binary sequences uh and the column labels are coordinate labels and this is a matrix that's infinite to the right and infinite down but it definitely has an upper left corner so the trick is to try to find an infinite binary sequence that is not in this list that it differs from every row if I can do that then I've shown that any attempt to enumerate all of the binary sequences in 01 to the Omega any sequence like s0 S1 and S2 of binary sequences is missing something which means you can't really list it well how do you find something that's missing some how do you find a sequence that's not here well it's pretty easy um you look at the first digit and that was a zero so you choose the first digit of the new sequence to be one the opposite of zero you choose the second digit to be the opposite of the coordinate of s the F of uh a digit one of S1 and complement that now here the digit two of S2 is a zero so let's make that a one and the next one on the diagonal is a zero and so on we're going to complement all of the bits along this diagonal so I get a diagonal sequence that's why this argument is called a diagonal argument well let's think about this diagonal sequence it just goes on right down the diagonal of this two-dimensional infinite Matrix what we can say about it is that it differs from every row why is that well it differs from the 15th row at the position or coordinate 15 it differs from the 99th row at coordinate 99 it's not in the matrix it's not a row of any Matrix and that immediately tells you it's over uh any attempt to list all of the elements in 0 one to the Omega is going to Omit a diagonal element it's not possible to list all of them in other words um uh there isn't any surjection from the non- negative integers to 01 to the Omega because I've just shown you how if you give me a surjection of uh anti binary sequences um in effect I'm giving you with n a zero sequence a first sequence a third a second sequence and so on then I know exactly how to find something that's not there there can't be a surjection from n to 01 to the Omega it's just not true um and that's why we can say that 0 one to the Omega is uncountable definition of countable or an equivalent formulation of countable remember is that there's a surjection from the non- negative integers to the set well there isn't any we just proved it okay so uh n is not surge Z1 by the way it's also quite easy to see that there is a subjection from the infinite binary sequence to the non- negative integers um you could map a binary sequence to uh the coordinate of the first one in it um and that Maps every infinite binary sequence to a non- negative integer and hits every non- integer negative integer lots of times uh I hit you know five with a sequence that starts with four zeros and a one the only sequence that doesn't go anywhere is the all zero sequence but by the way if you check the definition of surge it doesn't require that the function be total surge means that there is a uh a function that is a subjection to n uh but there doesn't have to be greater than or equal one Arrow out there just has to be less than or equal to one Arrow so it's a function but of course it's easy enough to make it total the all zero sequence just map it to zero um so now you have uh both zero and uh the sequence that starts with the sequence that any sequence that starts with one will all map to zero okay so uh if we remember our intuition surge is read as greater than or equal to so this tells us that the infinite binary sequences are a larger set at least as larg as set as the non- negative integers and the converse is true the non- negative integers are not as least at least as large as the infinite binary sequences so we can really say that the non- negative integers are strictly smaller than the set of infinite binary sequences now strictly smaller is in quotes because again we don't know exactly what the size of infinite sets is all we're doing really are talking about properties objections bje surjections injections okay so let's make an explicit definition I'm going to say that a strict B means that there is no surjection from A to B so if we read a surjection b intuitively as a greater than equal to B this is saying it's not true that a is greater than equal to b or in ordinary language and thinking about sets if it's not true that you're greater than or equal to B you must be strictly less than b so that's the motivation for the word strict but remember we're talking about infinite sets and we can't go around assuming too many properties of strict until we've prove them one non-trivial property by the way is I've defined strict that it's not true that there's a subjection from A to B uh B but I'm not insisting that there must be a surjection from B to a um which would be the second companion part that is a is not greater than equal to B and B is greater than equal to a turns out technically you can prove that if there isn't any surjection from A to B there will be a surjection from B to a but that's using a set theoretic argument that's not so obvious and we don't need it so this is the definition of strict a strict b means you cannot get a surjection from A to B and we're intuitively reading it as a is strictly smaller than b and we what we've just shown then is that the non- negative integers strict uh 0 one to the Omega the infinite binary sequences okay now cantis theorem is a wonderful uh generalization of this it's a powerful generalization but the proof is pretty much the same although it sometimes looks a little different as it's written up and what cantis theorem says is just it's it's just beautifully elegant and simple it simp it says simply that the power set is strictly bigger than the set a strict power set of a for every set a even if a is finite because remember if a is finite say a has n elements then the power set of a has two to the N elements and you can check that even for n equal zero n is less than or equal to 2 to the N is less than 2 to the n uh 0 is less than two to the 0 which is one um uh two is less than 2^ 2ar which is four and so on so even for finite sets we have a strict power set of a but the cool thing is that it works even for infinite sets let's take a look it's a diagonal argument again but now I mustn't assume that a is countable I'm not going to assume that I can really list the elements of a but we'll think about it as though we could let's think about this Matrix again so suppose a is this set of elements a b s TDE e I'm scrambling up the alphabet on purpose because I don't want you to get the idea that we're assuming that a is countable that you can list all the elements of a I'm not assuming that but I'm just writing out a sample of elements of a and let's suppose that I was trying to get a surjection from a to the power set of a so suppose I have a function f that Maps each of the successive elements of a to some subset of a so F of a is is part of the power set it's a subset of capital A F of B is a subset of capital A and so on and suppose I had a set up like this I'm going to draw a matrix that looks like the diagonal matrix and we're going to extract the diagonal set and discover that that diagonal set is not one of the fs it's not F of anything which means that f is not going to be a surjection so let's look at it again so here's this Matrix where I'm labeling The Columns of the matrix by the elements of a uh no particular order here but I in order to draw Matrix I have to write them down in some order and likewise the first row is going to be F of this element a well what is an F of a f of a is going to be a set of elements so let's just write the elements in F of a Down Under the corresponding column label so here's an example where F of a it has an A in it and no B but it has an s in it and a t in it no C uh no D it has an e like F of B has an A and A B and no s or t but it's got a C and so so I filled in this matrix by taking F of an element in a which is supposed to be a subset of a and writing out all of the elements in that subset um uh under the corresponding uh letter or corresponding element that of the subset so a b goes under a b if it's in F of C and S goes under an s if it's in F of C nothing goes under a t if T is not an F of C that's what we're seeing here so I'm laying out as though I was using zeros and ones for an infinite binary sequence I'm laying out each of the sets that uh that are in the range of f um along this row and now with this set up I can define a new set which is not going to be an F how do I get that well um what I'm going to do is not in my new set I'm not going to have any of the elements that appear on the diagonal so if a is a member of f of a that means that a appears in this coordinate it's not going to be in my set if B is in F of B meaning that b appears in uh that b appears in the F ofb row under the column B it's not going to be in my Set uh on the other hand uh s is not an F of s because there's no s there so I'm G to put an S there in in mag magenta and likewise I'm going to stick elements in or out the opposite of whether they appear on the diagonal and this is going to give me a set D um which is going to be my diagonal set okay um so if we write this out so what we're saying is suppose that I have a function f from a to the power set of a uh then what I'm going to do is Define a subset of a that's not in the range of f namely set B um which is the set of those elements in a such that little a is not in F of a namely if uh if an element appeared on the diagonal because an element um uh uh with column label a was in the row F of a then I left it out of my set and if it was not in uh in that location in The Matrix I put it in my set so I'm keeping all the elements that aren't in on the diagonal that's my diagonal set D and what I know about it is that D is not in the range of f because it differs from every possible row of the Matrix um if the row was labeled with uh with f of a as F of a then it differs in the column A F of a from that row and therefore my set D is not uh a row of this Matrix and that means that it's not equal to F of anything so I've just found that there's no F Arrow into d d is not in the range of F that means that if I had such an F from a to the power set of a it's not a subjection because D is always left out so f is not a subjection and since you know f is any function from a to the power set of a none of them are subjections and that means there's no subjection from a to the power set of a in other words a strict power set of a there's no Sur now uh a special case of this of course is that the non- negative integers are uh a strictly smaller than the power set of n because that's just an instance of of canas theorem where we're applying uh uh a being the set of non- negative integers so there's no subjection from the non- negative integers to the subsets of non- negative integers uh again that means that the power set of n is an example of an uncountable set because um the definition of countable is that there would be a surjection from n to power set of n we're saying there isn't any so it's not countable or not countable is is usually phrased as uncountable so the power set of n is maybe our uh second example of an uncountable set the first one being the infinite sequences of binary numbers now as a matter of fact um there's a just as we had a general way to prove countability um you can show that a set is countable if there's a surjection from a set you know is countable onto the target then the target's countable take the contrapositive of that Lemma and you can say that if a set uh a is uncountable and there's a surjection from C to a then C has to be uncountable that's just a contrapositive of the previous one if C was countable then a would be countable so if a is uncountable C must be uncountable so this gives us again a nice General way to prove uncountability of sets once I have a couple in my repertoire um well uh means that we could have deduced that 01 to the Omega that the infinite binary sequences were uncountable because we know that there's a bje between uh the infinite binary sequences and the power set of n we we describe that bje without knowing anything about any other properties of the infinite binary sequences in the power set of n whether they were countable or not but now that caner theorem tells us that the power set of n is uncountable and there's a bje the previous Lemma says in particular there's a surjection from 01 to the Omega uh to the power set of n which means 01 to the Omega is uncountable so and what I'm illustrating then is that the proof that we used directly on by a diagonal argument to figure out that 01 to the Omega um was uncountable it's really a special case of the more General diagonal argument that we use to prove Canter's theorem and we get that 01 to the Omega is uncountable as a consequence of Canter's theorem about the power set of n um and uh so we've got two different ways then to prove that the infinite binary sequences are uncountable another example of an uncountable set it's the real numbers uh and they're a cute example remember we saw that the rational numbers were countable the real numbers are uncountable well how do I prove that I'm just going to show you a surjection from the real numbers onto the infinite binary sequences um how am I going to do that well it's a kind of stupid trick but it works um uh I'm using both positive and negative reals so let's look at some uh real number and look at its binary representation assume for the moment that it's um uh positive so let's look at say the binary representation of some number like three and a thir so that means that if we're thinking of these as the as binary places this is the zeroth place the two's place the fourth place this is the half's place the quarter's place the eighth's place then the uh binary representation of 3 and A3 would be three and then this infinite uh repeating not decimal but B but bple or binary expansion 01 0 one 01 and we will examine how I know that that's a third but take it for granted that that's what you get is the repeated fraction you could figure that out by just doing a division of one by three in binary anyway um there is just as there's a decimal expansion of every uh real number there's a binary expansion just using base 2 so here's the binary expansion of 3 and A3 so what I'm going to do is I'm going to map 3 and A3 to this binary sequence I'm going to ignore the decimal place a binary it's not a decimal place it's a Bimal place or binary uh position and I'm just going to take this to the mapping the sequence one one Z1 01 01 okay um and I claim that this is a surjection because you're going to hit um every possible binary sequence in this way well almost let's take a close look um uh there's a problem with mapping um to things that start with zero because let's examine that a half is.100 so I would map it to that and uh and it will and but there's an ambiguity because a half is also equal to 0.011 one11 just as um 999999 9 is equal to 1.0 in decimal you get the same infinite carry issue here in binary so uh numbers that end in all ones have another way to represent the very same number by a sequence that ends in all zeros so how am I going to hit if I'm using up a half to hit this one what's left to hit that one well how about using minus a half it's there and that's part of R so I'm just going to map the negative numbers to the version of the expansion that uh starts with zero and has an infinite number of ones and the positive one that that ends with an infinite number of zeros and otherwise I'm going to map plus and minus numbers to the same place so this is going to give me the needed surjection from R to the infinite binary sequences and by our previous Lemma that implies sure enough that the real numbers are uncountable