Uncountable Sets & Cardinal Numbers in Real Analysis

[00:00:00][Music] [Music] yeah so we will continue our discussion of countable and uncountable sets so let's quickly recall that in the last class we proved a few things about contable sets namely that uh first of all a subset of a accountable set is accountable then uh Union of a accountable family of accountable sets is countable and finite product of countable sets is countable and using that we also saw that some of the familiar sets like the set of all integers is countable okay set of all rational numbers is countable okay so now let us proceed with that uh I'll now introduce one more uh notation uh let us say we have two sets A and B okay then we shall note this let us say this is as a is dominated by B okay a is dominated by b or if this means there exists F from A to B and F is injective injector means as you know one one inject okay if may or may not be on to okay if may or may not be on on two of course if f is on two also then then we know that this means a is numerically equivalent to be okay so what it you can interpret this as number of elements in a is less than or equal to number of elements in B okay that is the rough that is roughly the mining now what can we say about this relation the properties of this relations first of all we can say this following obviously a is dominated by a you can take f as an Iden function okay then second thing we can say is that if let us say if a is dominated by B and let us say B is dominated by C then then a is dominated by C okay that's also clear okay so if f is a function going from A to B which is 1 one and if G is a function going from B to C which is also 1 one just consider G compos with F that will be a function from a to c also be 1 one so that's clear okay right uh third property is this if a is dominated by B and B is also dominated by a then yes somebody said something then what can I say about A and B a is equivalent to right then a is numerically equivalent to B A is numerically equivalent to B okay but this last thing is not obvious okay so what it means is that suppose you have injective function going from A to B and similarly an injective function going from B to a those two functions will not be same okay then there exists a bactive function from A to B okay now that is something that is not obvious at all okay and in fact that is a very well known theorem in set theory it's a very famous theorem it is known as Sher buting theorem shouder buin theorem okay okay and what s Bain theorem say just what I said just now if you if you take two sets A and B and if there is a one one function from A to B and if there is a one one function from B to a okay then there exists a one one and on two function from A to B that is theorem okay uh the proof of this is somewhat lengthy so we shall not discuss that here I mean those of you who are interested you can see a proof of it in Simons book I mentioned s s's book right in the beginning it is it is given there there is one more Source in which you can find a fairly good proof of this uh perhaps many of you have heard of Professor s kumaresan okay quite famous for this mtts program some of you may have attended that also okay so uh he's a professor in University of Hyderabad mathematics Department University of you look at his homepage okay in University of hyad and that homepage contains some popular articles okay and one of those articles is a proof of stb is the okay okay you can find it there or also there is an mtts form page which also contains some popular mathematics articles there also uh you can find this proof okay all right uh now uh let us again go to one another famous theorem in this yeah by the way can you see that these three relationship issues look these three properties of this relation they look something like a this is not an equivalence relation okay but this is something like a partial order okay again not exactly a partial order because in partial order we would have required that if this happens then we should have had a equal to B okay so it is not a equal to B we we we only got a is numerically equivalent to B but what we can say is that if it is a partial order see suppose you look at this equivalence relation among the family of all sets Okay then that equivalence relation will split will partition the family of sets into equivalence classes okay and what are what are the members of equivalence classes those are are the members which are numerically equivalent to each other right so suppose you take the set of all that class all those classes okay then on that class this is a partial order okay because then then the equivalence class containing this what this says is that equivalence class containing a it's same as equivalence class containing B okay all right okay then let's go a little further so far we have not seen any example of an uncountable Set uh to do that uh okay let us again go to a famous theorem it is known as a Canter theorem okay okay and this theorem says the following let a be any set okay a be any set then consider the power set of a okay that is the set of all subsets of a okay then first of all a is dominated by this power set of a we shall use this notation 2 power a okay I mentioned earlier that 2 power a or script P of a these two notations are very commonly used for the set for subsets of a let us use this okay and it is not equivalent okay that second part is more important okay first part is more or less trivial okay what does it mean in terms of function s definition it means there exists a one one function going from a to power set of a okay but there is no bisection okay there is no bisection between these two sets Okay so let's go to the proof okay okay now first of all is it clear to you that this whole thing is Trivial if a is an empty set okay right if a is an empty set it power set will contain just one element and the set itself contains no element okay so there can be no no bisection between the two right and the one one function will be a trivial function so that case let us forget about it okay so if a is empty it is Trivial okay nothing to be Pro okay so assume a is non empty so in the first part we need to show that there exists an injective function from a to its power set okay that is given any element let us say X in a okay we we want to construct a function that is f going from its so suppose we take X in a this x f of x should be some subset of a okay f of x should be some subset of a now can you see that there is a very obvious choice for this take the single containing the element X okay right that's the most obvious function that one can think of okay so Define f of XX single turn X so this is a function from a to its power set that function is 1 one right that's clear okay so f is 1 one this part is provs okay so this part is proved right okay now we'll look at this now here what is it that we have to prove that a is not numerically equal that means there cannot exist any bisection between these two sets okay right so so the way to proceed is fairly straightforward that is assume that there exists a bisection and get a contradiction okay right so suppose suppose G from a to its power of a is a bisection in fact we can show that there cannot exist any onto function from a to its power set of a but that's okay okay all right now we will construct by the way this proof is also given orinal proof is also given by C okay canor is a famous very famous German mathematician who has done several things in analysis and set theory okay you will hear this name again and again by the way Sher and buin these two are also famous German mathematicians okay so suppose this is an onto function I'll think of a set b as follows okay Define B uh it is set of all X in a such that X does not belong to GX okay remember GX is a subset of a okay X is a function from sorry G is a function from a to its power set so every X in a g of X is a subset of a okay right so X so given any x x may or may not belong to GX right so you pick up those X for which X does not belong to GX okay I not say anything about whether this set is empty or not or whether an X exist or not okay whatever is that okay so take all those X for which X does not belong to GX you call that set B okay all right okay all right now this G is a bisection right G is a bisection and this B is a subset of a right so what follows from that there must exist some element in a such that g of that element is this okay okay so we can say that since in fact for this all that we require is G is on to okay since G is on two I will say there exists suppose I call that element small B there exist small b in a such that g of this small B is equal to B okay that's fine okay okay now we ask a question what what can we say about this element B okay does this element B belongs to B of course B is a subset of A and B belongs to a so B has to be either in b or outside B okay all right let us say what happens suppose suppose B belongs to B that means what this implies B does not belong to G of b g of B right B does not belong to G of B but what is g of B okay so look at this what if so what you have seen if B belongs to B then B does not belong to B that's a contradiction okay that's a contradiction okay right okay what is the other possibility suppose suppose B does not belong to B okay suppose B does not belong to B but that will give that b belongs to B because that is how okay on the other hand that is on the other hand if small B does not belong to B which is nothing but G of B then the way in which we have defined B it means so B must belong to B small B must belong to B okay then small B must belong to B okay that means B belongs to small B belongs to B and small B does not belong to B both are leading to contion okay right such a thing cannot happen right B is an element of a and small B is an element of a Big B is a subset of a so small B has to be either inside b or outside B okay and we are here we are seeing that both the statements are leading to a contradiction right and again what is the source of this contradiction this we assumed that there exists a bisection okay so that must be false okay so this is a contradiction okay so this completes the proof okay is this clear okay this is cont original proof of this theorem so let me again come back to the statement of theorem that given any set a of course this is Trivial part okay a is dominated by its power set but a is not numerically equivalent to the power set of a a and its power set are there can be no bisection between any set a and its power set okay does it immediately give us an example of an uncountable set does this the immediately yes what is that to do with this theorem right that's right that is suppose we take a as the set of all natural numbers suppose I take a as the set of all natural number then n and 2 power n there can be no bisection right there can be no bisection and it means that 2 power n is an uncountable set right okay so this immediately gives that uh 2^ n is an uncountable set okay so we have got an example of an uncountable set okay in fact it can be shown that this 2 power n is actually numerically equivalent to real numbers okay this 2^ n is actually numerically equivalent to real numbers okay uh let me give you some idea about this okay how how one shows that I'll just give you some steps in this may not be the whole thing okay uh you have heard of this term binary sequence it's a sequence whose terms are zero and one sequence is what as we have seen the sequence is a function from the set of all natural numbers okay so any sequence whose terms are just zero and one those are called binary sequences okay right okay on the so what I want to say is that suppose you take the set of all binary sequences okay suppose we take the set of all binary sequences then that set is uncountable okay so set of all binary sequences is uncountable of course there are several ways of seeing this but one way of seeing that is that we can say that this set is nothing but this set okay this set is nothing but this set okay set of all by sequence nothing but sense it is numerically equivalent okay and okay let us give some name to this okay suppose suppose I call X is the set of all binary sequences let X denote the set of all binary sequences you want to set X is uncountable so I want to say this okay I'll write this as a claim claim means this is something that I want to show claim is X is numerically equivalent to 2^ n okay okay I will take uh I will take a map from here to here so so consider F from 2^ n to X that is given a subset of n given a subset of N I want to construct a binary sequence I want to construct a binary sequence so so let a be a subset of n okay and Define f of a Define f of a you all heard of what is meant by a characteristic function of a of a set right so F of a i define it is a characteristic function of a okay what does this mean that if it is if it is one if if a number belongs to a okay that is remember uh this let me repeat this okay this K suffix a of some natural number right it's a function uh see it's a function from n to n it's a because it's a sequence it's a function from n and not n to n n to the set 01 okay n to the set binary okay so we'll Define correct n is equal to 1 if n belongs to a and zero otherwise that is z if n does not belong to a okay for example if a is a set of all even numbers then the corresponding sequence is 0 1 0 1 0 1 Etc okay similarly we can see so is it clear that this characteristic function is basically a binary sequence characteristic function is a function okay it it's a function going from n to see each characteric function is a function going from n to this set 0 and 1 its values are 0 and one okay so it's a binary sequence okay right is this function one one that is that is given a subset let us say if there are uh if the characteristic functions of two sets coincide okay right that is when when do say something is one suppose F of a is equal to F of B okay that is same I saying the characteristic functions coincide okay will it imply that a is equal to B right that is clear okay is it onto that means given a binary sequence given a binary sequence can we construct a subset of n whose characteristic function is the given binary sequence that is again clear okay you take those n for which uh that uh is you look at those those n for which the value of the sequence is one collect those n and take that as a set a okay take that as a set a that will be a subset of n okay right so this map which takes a to its characteristic function is is is a bisection so f is a bisection okay that proves this right so if is a b and we already seen that this is an uncount aable set so X uncountable set okay we can also uh see one more proof of this that the set of all binary sequences is uncountable um or that is again a see I'll discuss this because it's is also one of the wellknown methods of proving that something is uncountable okay that is if if a set is countable we already know that is infinite then you can arrange its elements in the form of a sequence okay right right so suppose suppose X is countable suppose X is countable then we can write then we can write X as x s uh X1 X2 Etc okay remember each of this X1 X2 is a sequence right each of this X1 X2 ET is a sequence okay so let us have some notation for this for example what is the sequence X1 the sequence X1 is I'll denote it by X1 as say X11 X12 x13 Etc okay right see remember each of this X11 X12 either zero or one okay each of this elements Etc are either zero or 1 okay so similarly so let us say I sequence x i i can denote it as x i1 x I2 Etc okay and to show that this set is suppose this were the case it will mean that you can list all by sequences in this fashion okay and what we want to show is that that cannot be done okay okay okay so suppose I construct a sequence which is different from all these okay then it will mean that X is not countable right okay all right now Define binary sequence X as follows okay binary sequence X as follows okay I'll use some because X1 I'll call that sequence y Define a binary sequence y as follows Y is equal to y1 Y2 Etc okay and I should say what is y1 what is Y2 okay what is y1 what is Y2 Etc okay what I say is as follows take y1 you look at X11 okay if X11 is zero you take y1 as 1 and if it is one you take y1 as zero okay right so take y1 as 1 if X11 is 0 and 0 if X11 is equal to 1 okay similarly you take Y2 same way look at this x22 second sequence X2 second X2 X2 1 x22 Etc look at this uh entry x22 here if x22 is one you take Y2 as zero if it is zero you take y as one so you take Y2 as 1 if x22 is0 and 0 if x22 is equal to 1 okay and now it's clear how to go about it proceed in this way take the general uh entry YN as follows YN is equal to 1 if xnn is zero that is xnn will be somewhere here suppose this is xn maybe xnn and zero if xnn is equal to 1 okay then Y is a binary sequence okay Y is a binary sequence okay but since y if Y is a binary sequence it must be one of this X1 X2 xn okay right but you can see that it cannot be X1 because y1 is different from X11 it cannot be X2 because Y2 is different from x22 okay it cannot be xn because YN is different from xn so y cannot be any of these and still it's a binary sequence okay right so this is a contradiction and this contradiction we got because of what because we assumed that X is countable and wrote The Elements of X in this form X1 X2 Etc okay that cannot be done okay this is also a fairly standard technique of proving that a set is not countable okay and this method is uh known as uh diagonal method the diagonal method of proof and you can see the reason why it is called diagonal method okay that is you are arranging the elements in something like in the form of a matrix and looking at the diagonal entries okay and then constructing a new sequence which differs from each of the diagonal entries okay that is why it is called diagonal method or diagonal process okay is this clear all right okay now you all know that uh every real number has a decimal expansion can be expressed in terms of it decimal expansion right you also know that it can also be expressed using binary expansion right decimal expansion is just one choice it can also Express by using binary numbers just zero and one okay so so what you can say is that the set of all binary sequences is nothing but the set of all real numbers you take any real number and take its binary expansion that's a binary sequence right so for each binary so each real number you can associate a binary sequence which is nothing but its binary expansion right and similarly if you are given any binary uh sequence you can associate a real number with that okay only problem is that uh which of the entries you take as an integer part and which of this you take as a fractional part that will be a problem to decide with but let us say we take only those numbers lying between 0er and 1 okay let us just take the numbers lying between 0 and one okay right then this problem will not be there there is there is no integer part okay so you can say that all so suppose you are given any binary sequence like that okay you let us say some sequence 1 0 1 you can take that number at 0. 1 0 1 0 Etc that is the binary expansion of the given number so in other words this sequence X you can say that it is numerically equivalent to X okay this sequence X is a numerically equivalent to X so what does that Pro that the interval 01 is uncountable okay it is it is numerically equivalent to the site of all binary sequences which we already showed to be uncountable so that is uncountable okay all right now we have proved in the last class that a subset of a countable set is countable does it also follow from that immediately that if if a is a set and if it has an uncountable subset then the a itself must be uncountable right suppose a set contains an uncountable subset then the whole set itself must be uncountable right it's basically the same it's basically the same statement said in a different different method okay different language so now if this is uncountable that will mean that R is uncountable okay this uncountable it means that R is also uncountable okay in fact um you can show something more okay if if we were simply to say that R is uncountable then this is enough okay pick up some subset that is uncountable once show that okay but we can say something more okay it is the following okay I'll give that you as an ex you take any open interval of R okay then you can show that that open interval is numerically equivalent to the whole of R okay that is in particular okay I will just give you this to you as an exercise okay show that and if you can do this for this interval you can do it for any interval okay show that what does it mean that show that there exists a bisection from the open interval 0 to one to the whole whole of R okay element try to try to find such a function on your own okay and once you can do this you can show that there is nothing particular about zero and one okay you can take any open interval and that any open interval is numerically equivalent to R and in particular any two open intervals are numerically equivalent to each other okay right okay but once you show this it will it will mean that R is numerically equivalent to 2^ n that's clear right we already show that this is numerically equivalent to x and x is equal 2^ n and this is numerically equivalent to R so comparing all this you can say that R is numerically equalent to the power set of n okay all right okay now I'll just make a few comments about what are known as uh cardinal numbers and then we shall close this discussion about the countable uncountable sets Etc okay cardinal numbers I think I have mentioned it earlier also if a is a finite set let us take set if a is a finite set Cal by cardal number is nothing but a symbol which we associate with every set okay we call it the Cardinal number of that set okay we call it a cardinal number of that set so suppose a is a set um let us say suppose a is a finite set okay we shall say cardal number of a is zero if a is empty okay right and this is equal to n this is equal to n if if a is numerically equalent to this J suffix n okay we have said that a is finite we said a is finite that means a is either empty or a is numerically remember remember what what was the suffix n it was this set 1 2 3 ET up to n segment consisting of first natural numbers okay in other words this n Cardinal number at for finite set is nothing but the number of elements in that set okay is nothing but the number of elements in that set okay then Cardinal number of this set of all natural numbers okay that is denoted by this symbol it is called Alf not it is it is read as Alf not okay Alf suffix zero okay left not okay and then Cardinal number associated with this set okay with any of these sets Okay R 0 1 or 2 power n Etc whatever I'll just take this set 2 power n that is usually Tak as the symbol small C okay okay and that is called cardinality of the Continuum it is called cardinality of the Continuum now now if you take uh various cardinal numbers then we Define a relationship between them so suppose suppose A and B are cardinal numbers okay of course one thing is clear a equal to B will happen in which case a equal to b means [Music] uh those are associated with two sets which are numerically equivalent to each other that is a equal to b means let us write it in full form it means there exists sets A and B such that Cardinal cardinality of a is small a cality of B is small b and a is numerically equivalent to B okay so if the two sets are numerically equivalent the Cardinal number associated with them is the same okay okay let us now also see what is the meaning of this a less than or equal to B okay again it means that uh okay there exist is sets a b such that cardinality of a is small a cality of B is small b and a is dominated by B okay that means there exist sets A and B such and an inactive function f going from A to B which is 1 one okay and and corresponding numbers are small a and small B okay and similarly one will also like to Define what is meant by a strictly less than b okay okay this again as usual we'll say that a is less than or equal to b and a not equal to B okay in terms of sets what does it mean it means that there exist sets A and B such that cardinality of big a is small a cality of Big B is small b and a is dominated by B but not numerically equivalent to B okay and in fact there exist no two sets with this property which are numerically equivalent to each other okay that is the meaning of saying that a is strictly less than b okay now if you look look at the set of all cardal numbers uh can you see that this is now a partial order for example we can see this property that is a is of course a is less than or equal to a that is clear okay a is less than or equal to a okay then second thing is that a is less than or equal to B and B is less than or equal to C that implies a is equal to C okay and lastly a is less than or equal to B and B is less than or equal to a now this time I can say this implies a is equal to B okay and then this last thing follows from the Sher bues theorem okay okay because a is less than or equal to B and B is less than or equal to a means what that means there exist two sets this A and B satisfying the properity cality of a is small a of B is small b and a is dominated by B and B is also doin by a then in view of St B theorem A and B must be numerically equivalent which is same as saying that small a is equal to small B okay so now among the set of all cardinal numbers this relation less than or equal to is a partial order okay this relation is a partial order in in those numbers okay okay now let us take uh one more definition in this suppose a is a cardinal number okay Cardinal number a this is called infinite Cardinal infinite cardal okay infinite Cardinal if this number Alf not is less than or equal to a okay it's called infinite okay okay now coming back to this relationship okay for example electron itself is an infinite Cardinal C is an infinite Cardinal any number bigger than or equal to C is also any cardal number bigger than or equal to C is also infinite Cardinal okay one more thing that one should notice here is that in view of contrast theorem okay for any Cardinal number a a is less than 2 power a okay and what is meant by 2 power a if if this number a is associated with a set a if Cardinal number of a then 2 power a is the cardinality of the power set of a 2 power a is the cardinality of the power set of a because that is what follows from the various definitions that we have seen so far okay all right now we can see the relationship between whatever the cardal numbers that we have seen so if you try to arrange all of them in certain particular order the smallest cardal number is of course zero okay then zero that is less than or equal to 1 that is less than or equal to 2 Etc okay and this is less than or equal to n okay that takes into account all finite cardinal numbers those are same as the zero and other natural numbers then all these finite cardal numbers those are strictly less than Alf not okay okay what it means that given any finite set you can have an inactive map going from that set to n but no onto map okay there's no bisection okay so that is the same say all these finite cardal are strictly less than F not okay all right and then what by what you observed there LF not is strictly less than 2^ LF not okay right but 2 power Alf not is same as C that is what we okay that is what we are seen here okay R is numerically equal to 2 power n cardal number associated with n is LF not that associated with r is continum so which is same as saying that this 2 power Alf not is same as C right okay then C will be again strictly less than 2^ C what is 2^ C it is you take the set of all subsets of R okay and whatever the cardal number you'll associate with that that will be 2^ C okay and similarly you can go on okay so 2^ c will be less than 2 power C sorry 2 power 2 power C Etc okay then that will less than 2 power 2 power 2 power C that way you can go on okay okay now this leads to one very natural question okay okay now this is fine Al F not is less than two less than 2 power C that is okay C is less than 2^ C that's also fine the question is do do there exist any cardinal numbers lying between these two okay do there exist any cardal numbers lying between these two okay for example between Al not and c and between C and 2 power C okay so let me make that question precise okay that is uh of course that question is Trivial if you take here okay if it's a finite Cardinal then you can easily find the numbers lying between n and 2^ n okay if it's a finite Cardinal there you can easily find numbers lying between n and 2^ n okay that is Trivial okay but it is not clear about the infinite Cardinals okay so let me just say this let a be an infinite Cardinal an infinite Cardinal does there EX exists does there exist a cardinal number B such that a is strictly less than B and B is strictly less than 2 power a okay of course this is a question in fact it will be easier to understand this question if you uh formulate it in terms of sets Okay suppose you are given an infinite set okay we have shown that every infinite set contains a accountable infinite subset okay so the cardinality of an infinite set will be bigger than or bigger than or equal to Al LF not so if you take any infinite sets its Cardinal number will be an infinite Cardinal Okay so suppose you take any infinite set and you take its power set okay right then cality of that set will be a c of the power set is 2 so asking whether there exists a b with this property means given an infinite set and its power set okay can you find a subset which is bigger than given which is bigger than or equal to the given set okay that means this okay can you find a b such that a is dominated by B but not equivalent to B and B is dominated by 2^ a but not equivalent to 2 power a okay that is what it means in terms of set the and as such Nobody Knows the answer to this question till now okay this is a this is an open question in set theory the answer is not known okay and there are certain special cases of this they have some very special name one of them is called Continuum hypothesis it is called Continuum hypo is continum hypothesis assumes negative answer for this when a is Al not okay in other words Contin says that there is no cordal lying between Alpha not and C okay or in terms of set there is no set which is strictly bigger than uh set of all natural numbers and strictly less than set of all real numbers okay that is Continuum hypothesis okay and similarly there is another another thing which is called generalized Continuum hypothesis okay it is let me simply generalized Contin hypothesis generalized Contin hypothesis says the answer to be no for this whole question okay answer to be no for this question okay and what is known about this Continuum hypothesis is that using the other EXs standard EXs of the set theory you cannot prove or disprove hypothesis okay now this is something you maybe find it difficult to understand this it more to do with logic okay what it means is that uh if you assume that continum hypothesis is true okay that is quite consistent with all other acems of set theory okay and you can develop certain kind of set theory assuming that continum hypothesis is true okay at the same time if you assume that the continum hypothesis is false then that is also consistent with all the other actions of the set theory and you can develop some other kind of model of set theory assuming all other EXs and assuming that continum hypothesis is false okay now this is expressed by saying that the Continuum hypothesis is independent of all the other ACs of set theory okay that is using other ACs of set theory you cannot prove or disprove continum hypothesis okay right that is that so that is the answer known about discontinu hpis okay but but even that is not known about this generalized whether even even whether that is the case or not is not known about this generalized Contin hypothesis okay all right so with this I will close this discussion of countable uncountable and finite sets for the time being from the next class we'll go to the next [Music] topic [Music]