so last time we spoke about uh we covered sets and induction this time i want to ask a question about sets um which turns out is is you know actually quite a deep question i mean i didn't come up with it myself this question is at least 150 years old probably so the question that i want to ask is if a and b are sets um or let's phrase it this way at least a little more efficiently when do two sets a and b have the same size okay this is especially interesting if these two sets are not finite meaning there's not five of them there's not eight of them um but there's infinitely many members whatever that means and i'll actually define what that means for example do the natural numbers and the integers have the same size do the natural numbers and the rational numbers have the same size what about the rational numbers and the real numbers even though we haven't defined that yet you can still um keep in mind you know your notion of the real numbers from calculus and so this question is why is it deep because it depends on this word here size and what exactly that means so i'm not so kind of an answer this is due to george cantor he said that two sets so not an answer but a way of defining size a way of saying the two sets have the same size he said two sets have the same size when the of the two sets the elements of the two sets can be paired off okay meaning and i will make this much more precise in a minute or so what what does he mean or what do i mean for example the set a b and c and the set one two and three so this one consi this set consists of three letters a b and c this set consists of three integers one two and three they have the same size because i can essentially pair them off uh a so a and one go together b and two go together and c and three go together meaning each one of each member of this set gets paired off with an element of this set and every element of this set gets paired off with a unique element from this set okay now to make and so this is uh goes under the name of the theory of cardinality or cardinal numbers if you like but we won't go too deeply into it so the way you make or the way one makes this pairing off business more precise is using the language of functions and you've been dealing with functions since you've been um doing calculus so i'm just gonna quickly um reintroduce or review some terminology that goes along with functions that you know will be the precise uh meaning of this pairing off business that i'm writing here so but just uh with an eye towards the future this is why i'm reviewing some of these some of this terminology related to functions so so brief review of some terminology for functions so let me just recall that if a and b are sets then function f a b so a function's usually written as f colon a arrow to b meaning it takes elements from a into elements from b this is a mapping that or if you like an assignment that assigns to each x in a a unique element which we denote f of x and b okay so one single input x gives me a single output um an input does not give me three outputs now this is what one would call a naive definition probably not necessarily completely unambiguous but for us this suffices in the textbook you can look up a function is unambiguously defined or as a subset of the cartesian product of a and b which you would recognize as essentially describing the graph of the function but then you never use that definition of again and you essentially use this definition uh when you think about functions and when you prove properties of functions so this we will just take as our definition and it will be unambiguous uh enough for us so let f be a function from a to b if c is a subset of a we define a set so this is f of capital c so c is not an element of a it's a subset of a this is a subset of b this is let me write it slightly differently here this is a set of all y and b such that there exists an x and c such that y equals to f of x and i could write this a little more efficiently as this is the set of all elements f of x as x ranges over the elements of this subset c and if d is a subset of b we define the sub the set f inverse of d this is the set of guys that get mapped into d so i should say this is the inverse image of d not a the inverse of this function f okay so you know the inverse whatever that means for now um does not necessarily always exist so this inverse image of the set d always exists this is the set of all elements in a such that f of x is in d okay so for example let me uh so one two three four and a b c d and let's suppose 1 goes to a 2 goes to a 3 goes to c 4 goes to d ok then f of the set one two this is where what is the set that gets so this is the subset of so this should be you should think of as b a b and c uh and d and then one two and three this is a so f of the set of one two so one gets mapped to a two gets mapped to a so this is just the set two f of the set uh let's go with one and three one gets mapped to a so this should be a one gets mapped to a and three gets maps gets mapped to c okay and so a couple of inverse images if i look at the inverse image of a this is equal to the set of all guys that map to a this is well one maps to a and two maps to a so this is one two now if i look at the inverse image of a c d what elements get mapped to a c and d well one and two get mapped to a three gets mapped to c four gets mapped to d so everything maps into a c and d so this is just the original set or the set a one two three four okay all right so some more terminology and this is what we will mean by when two sets can be paired off or this makes that more precise let f be a function from a to b we say that f is injective or i'll write one to one should be read one to one if f satisfies the following property f of x one equals f of x two implies x one equals x2 okay so injective or one to one means if i take two different uh inputs i get two different outputs okay that's essentially what this means i mean taking the equivalent so equivalently from a logical standpoint this statement implying this statement is equivalent to the negation of this statement implying the negation of this statement so equivalently this means x not equal to x2 implies f of x1 not equal to f of x2 so maybe this is clear if i were to define f as injective if it satisfies this property um maybe that would have been clear that you know f takes two different elements to two different elements but this condition here is typically easier to verify or at least simpler to state and verify so f is surjective or onto if the image of a is b okay so let me write that statement out a little bit more everything in the set b gets mapped to by something from a so so equivalently this says that uh for all y and b there exists an x and a so that f of x equals y okay f is bijective if f is one to one and onto so it's f is bijective if it's both injective and surjective so for example this map that we just drew over here that sends 1 to a 2 to b i mean 2 to a 3 to c 4 to d this is neither injective nor surjective it's not injective because it takes two different elements to image in b namely a so it takes one and two to a it's not surjective because nothing gets mapped to the element b uh here so so we've seen that's not subjective of course this map if i take again imagine this is one two three a b c d this map here this function here that takes 1 to a 2 to b 3 to c this is actually injective but not surjective and then of course we could change this slightly and one goes to a two goes to b and three goes to b then this is third objective but not injective okay now the map that sends um let's switch sides here a b and c one two three a to one b to two c to three this is a bijection biject div so if i say something's an injection or surjection or bijection that just means it's a map that is injected surjective or bijective respectively okay and now definition so this is really there's not much to this definition but just defining a couple of functions that are related to a given function if f goes from a to b g goes from b to c the composition g of f is the function which goes from a to c is defined by g of f of x equals g of f x 2 if f is bijective so this is the composition of two functions i didn't write the word composition but this is g of f means the composition or is referred to as a composition if f is bijective then we define the inverse function to f b to a by the following if y is in b then f inverse of y and a is the unique element in a such that if i take this element stick it into f i get back y okay so inverse the inverse of a function only exists for bijective functions or at least is only defined for biject's bijective functions you know keep that in mind don't confuse that with the inverse image of sets okay although those two notations look the same you have an inverse f to the minus 1 after the minus 1 if it's a function that is the inverse function however if i'm taking f to the minus 1 of a set that means the inverse image of that set as defined over there okay so bijections meaning bijective functions will be what we mean when we say two sets can be paired off okay it's what we mean when we or at least what cantor's and to answer to that original question was uh when do two sets have the same size so this is the notion of cardinality that i alluded to so two sets we say two sets a and b have the same cardinality if there exists a bijection or a bijective function f from a to b okay and uh so let me just make uh some notation here so this is not really um you know new objects i'm defining or operations this is just some notation so when two sets have the same cardinality uh we write so this is just a shorthand way of writing that two functions have the same cardinality you should not necessarily think this means taking the absolute value of a set okay that that doesn't mean anything all right this is just shorthand notation for saying two sets have the same cardinality if a has the same cardinality as the set one two three up to n we write a equals n okay that's just shorthand for saying that a set has the same cardinality as the natural numbers up to n we write a so if there exists an injective function or i will often say either function or map i did you know you should take those as uh synonymous there exists an inject injective function f if there exists an injective function f from a to b we write this thing again do not read this as taking the absolute value of some set and that absolute value is less than or equal to the absolute value of the other set because that's meaningless we haven't said what that means even this is just shorthand notation and if a if there exists an injection from a to b but they don't have the same cardinality we write this okay so even though this notation of these absolute value things being on the outside of the set makes you think absolute value or shouldn't be interpreted as absolute value it's okay to kind of think as you know a certain ordering being there as one as sort of a having smaller size than b okay we write this because there being a injection from one set to the other kind of means i can pair off elements of a with some elements of b okay maybe i don't get all of the elements of b but i can pair off some of the elements of a with some of the elements of b for example that first map we wrote up there yeah that says that the set one two three uh in size is less than or equal to the size of abcd because we found an injection an injective map from the first set to the second set um this third map would say that uh the size of the set abc is equal to three written here or shorthand written here okay and in fact that first map that we wrote up there again uh is so from first map this says that the set of one two three uh in our shorthand notation absolute value has is less than the size of abcd okay so don't think of these as saying the absolute value it's best to maybe think of this as saying the size of okay all right so if there exists an injective injective map from our function from one set to another then the size of a is less than or equal to the size of b if the size of a is less than or equal to size of b but the size of a and b are not the same we write the size of a is less than the size of b okay so best to think of those um this absolute value looking thing as being shorthand for r for saying the words size of okay now i'm not going to prove this it goes a little bit beyond the scope of this class but let me just say that this uh ordering this inequality these symbols that we're writing does bear some sort of semblance to the ordering of real numbers in that if i have two real numbers one is less than or equal to the other and vice versa so a is less than or equal to b and b is less than or equal to a then a must equal b that is in fact true also for this elementary notion of size of sets and this is i mean you should it shouldn't surprise you for you know finite sets um necessarily if if i have a pairing of a if a is no bigger than uh n and n is no bigger than the size of a then a should have n elements um but it's takes a little bit more to prove for um sets which are not finite so i forgot to write this down we also say that a if the size of a is equal to the size of this finite set 1 through n we say a is finite okay so this theorem that i'm stating here is the cantor schroeder bernstein theorem which states that if the size of a is less than or equal to the size of b and the size of b is less than or equal to the size of a then size of a equals size of b so again if you're thinking of these in the context of real numbers one being less than or equal to the other and vice versa of course that implies that those two real numbers are equal to each other but we're not talking about real numbers again this is just shorthand notation for saying there exists a bijective map from a to b this means there exists a bijective map from a to this set this means there exists an injective map from a into this from a to this set okay so this is not a statement about real numbers this is a statement about cardinality all right okay so you know finite sets are sets that you can count um if you had in fingers now you know we would like to be able to define what it means to be able to count a set so what i mean by count asset meaning if i had infinite time i could go through the set counting them one two three 4 5 6 7 8 9 10 and so on i don't need to go any more okay so but what does that process of counting mean that means for each element of the set that i'm trying to count i can pair it off with a natural number one two three and so on so this is how we define uh countable sets so if a has the same size as the natural numbers meaning there exists a bijection from a to the natural numbers then we say a is countably infinite if a is finite or accountably i also use a lot of shorthand so but it's not clever shorthand so you should just be able to sound what like if you just sound that out you'll you'll get what word i mean countably uh accountably infinite infinite we say a is countable okay so countably infinite means i need all the natural numbers to be able to count off uh the elements of the set a countable means maybe i stop after some point and i've counted all them so a is finite or it's countably infinite otherwise if a set is not countable we say it's uncountable okay so let's uh take a look at a couple of accountable sets that maybe um don't come off as being accountable um set of actually that's a homework problem the set of even integers is countable the set of odd so i said integers a minute ago maybe i should just say natural numbers the set of odd natural numbers is countable so in fact so this is just a side so these are two disjoint subsets that make up the natural numbers the even and odd natural numbers and they both have the same size as the set that they make up so it you know it's almost like saying the cardinality of the natural numbers is twice the cardinality of the natural numbers since it's you would think that the size of n should be the size of this set plus the size of this set since they're destroying and they make up the set um but you know that that's not how cardinality works um you know you don't just add cardinalities to get the cardinalities but so this is kind of a subtle kind of interesting thing about cardinalities and feynman so richard feynman who won the nobel prize in the 60s for his work on qed described this as saying um there are twice as many numbers as numbers um okay so let's uh prove this so what does this mean that this means we have to be able to find a bijective function from this set to this set okay or from this set to this set okay one or the other um and so in fact um maybe i should well i'll say something about uh about that in a minute um well let me let me pause let me pause this just for a minute and let me make a few comments about cardinality which maybe i should have so this you can think of is a little theorem if i have two sets a has the same size as b then b has the same size as a so remember this i mean what i just said in english is not exactly what those symbols mean remember this means there exists a bijection from a to b this means there exists a bijection from b to a so what is the proof of this statement so let's start off with the hypothesis suppose then there exists bijective map bijection bijective function f from a to b okay now if i have a bijection from a to b then what would be a bijection going from b to a that would just be the inverse so this is not the inverse image of sets like we described but the actual inverse which we defined over there is a bijection so b has the same size as a okay um one other statement so if a and b have the same size and b and c have the same size so again a b and c are sets i should have written that at the beginning but from this context you should understand that a b and c are sets then a and c have the same size okay so let's do a proof of that so let's start with the hypothesis meaning a has the same size as b and b has the same size as c so what do these two statements mean in terms of the definition that means there exists bijection from a to b and a bijection from b to c and this statement so let me finish this and then i'll say what i was going to say then there exists bijections f from a to b and g from b to c okay [Applause] so perhaps i should have said a few more words about why this is true so but i'm going to leave this as the exercise just to kind of pause the lecture and do it yourself and what i'll write uh shortly for this case i'll actually prove that the thing i'm going to define is a bijection that should help you so let me draw over here off to the side we have you know again 1 2 3 a b c so think of this as f this is my set a this is my set b and then i have alpha beta gamma and a gets mapped to alpha b gets mapped to beta c gets mapped to gamma so what would be the map going from a down to the set c well perhaps the composition one gets mapped to a which gets mapped to alpha so one gets mapped to alpha two gets mapped to beta 3 gets mapped to gamma how do i build this function out of the things that i know namely this f in g well this function going from a to c is just the composition of these two functions so this is off to the side this is not a part of the proof let h go from a to c be the function g of f x okay so i claim that this function is a bijection so we want to prove okay that it's one to one and onto all right so let's do uh one to one first so suppose so we this is the part where i'm going to put this in parentheses meaning what we're doing now so we're going to prove that h is one to one so that means we have to verify uh the definition that i've erased so remember the definition so let's write it all out we first show h is one to one and what this means according to the definition that i'm now writing over if h of x1 equals h of x2 then x1 equals x2 okay so this is what we want to prove this is the definition of h being one to one so um so let's start if h of x1 equals h of x2 then in terms of how we've defined h which is g of f of x so the composition and this means g of f of x1 equals g of f of x2 okay that's just what h is now this statement here now g we know is a bijection okay we know g is one to one and since g of something equals g of something else and g is one to one this implies that f of x one equals f of x two this is since g is one to one okay so starting with this and the definition of h being the composition we conclude that f of x one has to equal f of x two because g is one to one now since f is also one to one right we are assuming that f and g are bijections since f is one to one this implies x one equals x2 since f is one to one and this is what we wanted to prove right we wanted to start with assuming h of x one equals h of x two and prove x one equals x two which is what we've done so thus we've proven that h is one to one okay now we have to show that it's surjective that it's onto hfa equals c and again i'll write out what this means this means for all y and c or let me call it z there exists an x in a such that h of x equals z okay now we use the fact that f and g were injective to conclude that the composition is injective so it stands to reason that we're going to use the fact that they're both surjective to prove that h is subjective so we need to prove that for all z and c there exists an x and a such that h of x equals z so let z be in c now we need to find some x and a that gets mapped to z we'll use that g and f are both surjective so and what's the picture that kind of goes along with this here's the set c b and a we have some element of z and we know that since g is surjective there's some element in b that gets mapped to z by g okay but now since f going from a to b is surjective there exists some x which maps to y okay and then that's the whole argument that's it all right i drew this picture but now i just need to turn it into english using the properties and assumptions that i have since g is surjective there exists a y and b such that g of y equals z since f is so objective there exists an x in a so that f of x equals y but then if i look at h of x this is equal to g of f of x which is equal to g of y which is equal to z by how we've defined y remember g of y equals z how we found y and how we found x remember f of x equals this y okay and therefore this map h is on 2 and therefore h is a bijection proving this theorem so that should help you in your mini exercise to to prove that the inverse of a bijection is a bijection okay so back to what we're doing to begin with we want to show the set of even natural numbers has the same size as the natural numbers has the same cardinality as the natural numbers and the same for the odd one so i'm just going to do the odd ones again this will be a small exercise for you to do to prove number two the statement for the uh odd ones so i'm going to do the even one and you can do the odd ones you should if you plan on studying more math get used to the instructor professor research paper writer textbook author giving out little exercises to make sure that you're following along and that you can do some minor tasks at some point during the discussion okay so we're going to find uh so we want to show that the natural numbers has the same size as the even natural numbers which is the same as this statement by that first theorem i wrote up there um now we that means we need to find a bijection from the natural numbers to the set of even natural numbers um this should be not too bad i mean so again this is uh off to the side this is not part of the proof what would be the map going from these guys to these guys well i mean there's several you could choose but maybe the simplest is one gets mapped to two two gets mapped to four three gets mapped to six four gets mapped to eight five to ten six to twelve and so on and so on okay now what is that map and now i'll re uh i'll continue the proof let f be the function into the even natural numbers defined by f of n equals 2 times n and so we're in a natural number okay so this is just formally writing the function that takes one to two two to four three to six four to eight and so on and so on um i claim f is uh bijection so i have to show that f is one to one and onto so we first show f is one to one so that means that i have to assume f of n one equals f of n two and conclude that n one equals m two so let me actually write out what this means again for you to say that f is one to one is one to one i e if f of n one equals f of n two then n one equals n2 but this is this is easy to verify for this function that we've written down because if f of n1 equals f of n2 so remember this is what we want to show all right so to show it i start with my assumption and i need to conclude n one equals n two so suppose f of n1 equals f of n2 my assumption my hypothesis i need to conclude n1 equals n2 then this implies by the definition of f 2 times n1 equals 2 times n2 which by algebra of just eliminating the 2's n1 equals n2 which is the conclusion that i want okay so i've proven the statement that if f of n1 equals f of n2 then n1 equals n2 therefore f is one to one so thus f is one to one so now we wanna show f is on to surjective okay i'll write this out again ie for all elements that are in that are an even number there exists an n such that f of n equals m okay now let m be an even integer and so not to confuse this let me write 2 times k this is the same set just using a different dummy variable instead of n in my description of the even natural numbers then and let's do that here as well okay again this is not changing anything this is just changing the letter i'm using to describe the set um which is inconsequential but i don't want you to get the false impression that somehow i'm not doing anything at all okay so suppose i have an even integer then there exists simply by the definition of this set there exists an n natural number so that m equals 2 times n then f of this natural number which is 2 times n equals m and therefore i get something that maps to m therefore f is onto therefore f is a bijection and the two sets have the same cardinality okay all right um so let's where are we at where should i write it's right here maybe i'll leave that up because i don't want to now using this and i'll probably put this in the in the homework i mean one can um also show i should say using this but one can also show that the integers have the same size as the natural numbers um which again is a little bit surprising since the natural numbers are a strict subset of z um so what's the proof uh so i'm gonna draw a picture then i'm gonna write down the function and then i'm gonna leave it as uh actually i'm gonna put in the homework that for you to verify that this function is one to one and onto so let's say there's as many natural numbers as i want to write um and as many integers as i want to write okay so what would be a way of mapping the integers in a one-to-one and onto fashion onto the natural numbers well what we could do first off let's send zero to one just to get zero out of the way and from then on now we just need to find a way to map the positive integers and the negative integers onto the natural numbers bigger than 2. and in some way you know mentally we should feel like we can do this because we kind of did it over there but not not explicitly so um how about we take one to two two to four three to six okay four would then go to eight and we'll take one to three minus two to five they're getting crossed and then minus three would get sent to seven so you see that the positive integers gets mapped to the even natural numbers and the negative uh integers get mapped to the odd natural numbers bigger than one okay so i'm not even going to write the proof this will be um part of the homework now you know it is a bit surprising that there are twice as many numbers as numbers uh not too surprising since you know kind of these subsets if you picture them as i've been doing as subsets of the real line you know they're kind of discreet so you should be able to count them um what is not what is more surprising are is whether or not you can count subsets that in some sense are not discrete for example what about uh the rational numbers so this is a theorem that and let me just look at those positive rational numbers in fact i could take all rational numbers but for the statement of this theorem if i look at those rational numbers with which are positive then this has the same size as the natural numbers you can count the positive rational numbers which is just you know a bit uh a bit crazy to me because you know here at least for let's say the integers once i'm at an integer i can move to a next biggest one and count that one in some way right and so that kind of makes it believable that i can count uh the integers the integers have the same size as the natural numbers even though that at first glance it looks like there's twice as many um but for rational numbers you know between any two rational numbers there's another rational number in between them right you just take uh take the average of those two rational numbers so it's not cl so now this idea of being at a rational number and then sort of moving to the next big one that you can't do that now so now it's it's a little bit up in the air at least whether or not you can count the rational numbers and what i'm saying is that indeed you can and this will be part of the homework i will at least give you an idea of how the proof will go what we will actually be able to write down a map based on a simple fact so let me not write down proof but let me write down remark so we'll actually actually be able to write down a map based on one simple fact which is this fundamental theorem of arithmetic which says that so this is just discussion now you know more stuff will be written in the homework about this but so just try to follow along so the fundamental theorem of arithmetic says that if you have a positive natural number you can write it in a unique way as a product of prime numbers now for rational numbers using that that means you can write every rational number uniquely as a product of prime numbers divided by another product of prime numbers where no two prime numbers uh where the where the prime numbers up top and the prime numbers at the bottom uh none are in common meaning you've uh simplified as much as possible so instead of um you know 15 over 3 no that's not good let's say 15 over 30 you have one half okay so the map that i would take so what i'm saying here is that every rational number can be written as some product so let me not use that notation but some product p r one p n r n q one s one q m s n where p1 p1 p2 and pn these are all primes q1 up to qm they're all primes r1 or n these are all exponents positive natural numbers so rj s k these are natural numbers p 1 p n q 1 to q m are primes and for all j k qj does not equal pk so there's no prime that appears both up here and down here we've already simplified that away okay so then the map so this uh so just so you know you don't think i'm i'm fooling you you know nine halves which is a positive rational number this is three squared over two yeah uh you know 20 i'm not going to do any more that's it you should so the map that we will take from this rational number to a natural number will be this gets mapped to the natural number p1 to r1 pn 2rn times now q one two two s one minus one q m two s n minus one so basically i map it to the integer that has this exp has this expansion in terms of prime numbers where now the exponents of these prime numbers is even depending on these exponents on top and the exponents of this one are odd depending on this exponent on top okay so for example 3 squared over 2 this would get mapped to a three to the fourth times two okay so what we'll do in the homework is show that this map is in fact a bijection so okay so those two theorems you will prove in the homework they won't be too too bad i will leave enough hints so uh dealt with z dealt with q essentially i mean so let me actually write down this is really a corollary of these two theorems here which i haven't proved but you will prove in the homework so it says that the rationals are countable all the rationals not just the positive ones and what's the proof so we know that so i'm going to give you kind of a sketch should i sketch it or should i write it all out i'm running a little bit at a time but so maybe i will just tell you why this is true i mean all the details are essentially here i'm just not going to write it as carefully as i've been writing down the proofs before so let me write this as the proof sketch of course you can write these you can actually use the definitions and write this out but this is a the essential idea so um we have that the size of rational numbers so let me um this has the same size as the rational numbers which are negative okay and this how do we establish this or let me instead of using the same letter let's say r since f of q equals minus q is a bijection from the first set to the second set if i just take a rational number positive one take its minus then i get an element of the second set and this is a bijection okay um okay so thus since this has the same size as the natural numbers and by that theorem we proved over there the size of this set is the same as the natural numbers so it is countable okay then there exists bijections f going from q so the positive rational numbers to the natural numbers and g going from the negative ones to the natural numbers okay so picture here is um well let's not write draw the picture yet okay so i have these two bijections from the positive rationals to the integers this one from um the negative rationals to the natural numbers how do i get a map that goes from all of q now to the natural numbers well let's go in between and go to the integers then i define a function h which goes now from all of q to the integers by h of x equals 0 if x equals 0 equals f of x if x is positive and negative g of x if x is negative okay and h is bijection so everything up into this point um has been completely fine with the exception of me verifying that this map is a bijection and this map is a bijection so that's kind of the only parts that i'm leaving out for you to verify then h is a bijection so q has the same cardinality as integers which we've shown has the same cardinality as the natural numbers and therefore rationals have the same cardinality as the natural numbers so they are accountably infinite so a natural question is [Applause] i mean is there anything bigger than the natural numbers because everything i've written down this has the size of the natural numbers we haven't really defined the real numbers well enough yet to make any sort of claim like that about the real numbers and now is there just any set that is bigger in size than the natural numbers the answer to that you know was unknown and it's pretty um pretty strikingly yes in fact so let me phrase that question does there exist you set a such that a has strictly bigger cardinality than the natural numbers so a is uncountable okay so to answer this question astoundedly yes let me first define for a general object if a is a set we define script p of a this is the power set of a this is a set that consists of all subsets of a so this is the set of all sets b such that b is a subset of a okay so for example uh if a is the empty set the power set so a is empty what are the subsets of the empty set well there's only one subset of the empty set the empty set so and even though the empty set has no members its power set has one member if a equals one then the power set of a the set of all subsets consists of the empty set and the set itself one okay and let's do one more if a is the set 1 2 then the power set of a this is the set which consists of the empty set because this is a subset of the set the set consisting of one because this is a subset of this set or two one two now notice something this set had cardinality uh strictly speaking i should have defined that as being having cardinality zero yet its power set has cardinality one a has size one because it's uh in one to one correspondence with just one and its power set has uh two elements so um has cardinality two i could count them off one two a has size two has two elements and the power set of a has size four it has four different elements that empty set one two one two so what one can prove in general and which will appear on the homework is if a has the same car has size n so it's a finite set of size n meaning it's in one to one correspondence with the numbers one up to n then its power set is also finite and has cardinality two to the n okay and you can prove by induction if you like that two to the n is always bigger than n okay and so a theorem i'll prove next time which will finish our discussion of sets and uh cardinality um and then we'll move on to the real numbers is this theorem due to cantor uh which says that not just for you know finite sets do we have the power set being in some sense strictly bigger than the original set but for any set so this theorem due to cantor is if a is a set then the cardinality of a is strictly smaller than the cardinality of its power set so this definitely answers our question does there exist a set with cardinality bigger than the natural numbers so let me write this as a remark uh in fact maybe i'll state this as another theorem which just follows immediately from this kind of getting used over and over again is that the cardinality of the natural numbers this is less than the cardinality of the power set of the natural numbers which is less than the cardinality of the power set of the power set of the natural numbers right i can now take this as a set and take its power set and i get a new set with bigger size which is less than the power set of the power set where how many do we have now of the power set of natural numbers and so on okay so um and formally this means they're [Applause] there's an infinity of infinitudes there's an infinite an infinite number of infinite sizes okay one getting strictly uh in some sense strictly bigger than the previous size okay and maybe you're wondering uh there's one more question that's kind of sandwiched in between here pun intended is let's look at this first guy does there exist set a such that it has size bigger than natural numbers so it's uncountable but has size strictly smaller than the power set of the natural numbers and this question is called the continuum hypothesis hypothesis because it is independent from one of the uh standard axiomatic treatments of set theory um but we will not touch this question this is beyond the scope of this class but it's an interesting question that's out there that you know people just don't know