[Music] now let's talk about subsets in the infinite context so how do we talk about subsets of the numbers in a precise way so this is something called set comprehension so this is just some jargon so a set comprehension is just a term used for this which we have sometimes seen and which we will now review so if we want to talk about the set of even integers the set of even integers are those integers which when divided by 2 have a remainder 0 so remember that the remainder is called mod so X mod 2 is the remainder when divided by 2 so if X mod 2 is 0 it means that when we divide X by 2 there is no remainder so any such X is an even number so this notation that we have written is actually the set comprehension notation so let's try and separate out the different parts and understand what's going on so when we use cept convention first of all we can only do set comprehension when we have a starting set so we have to begin with a set and construct a subset of that set so the first thing says that we want to take all X in Z so this here says that we are looking at elements from an existing set in this case this set is a set of integers then it says I want to take all elements and apply some condition to decide whether to keep that number or not so that is the second part of the right hand side so we have the first part which tells us which set we are looking at the second part which tells us what condition we want so we are really saying X in Z such that X mod 2 is 0 and finally with this bar and this left-hand side we are saying collect together all the X which satisfy this so this overall this notation says collect all the X for which X is and Z such that X mod 2 is 0 or in other words X is even so this is set comprehension notation and this is formally how you define a subset of an infinite set remember that we can't list out the elements in an infinite set now we assume that we already have a set like Z or N or Q or R for which we know what elements are so we don't have to describe how to pick out element we know what those elements are what we are now giving is a description of how to choose elements which satisfy a given property so let's look at some more examples so for instance let's look at perfect squares so remember that we said an integer is a perfect square if it's square root is also an integer so for instance 25 is a perfect square because the square root is 5 but 26 is not a perfect square because there is no integer which multiplied by itself is 26 so here is a set comprehension notation of the perfect square so first of all remember square number has to be positive we already discussed that negative numbers cannot be squares because when we multiply two numbers by them to the same number by itself the two numbers will have the same sign so either it'll be minus into minus is plus or it will be plus into plus is plus because the multiplication rule says that if the two numbers you are multiplying at the same sign the outcome is always positive so first of all we can only have positive numbers so instead of looking at integers it suffices to look at the natural numbers so we say for all M which are natural numbers such that the square root of M is also a natural number so this is that the square root of M also belongs to set in collect all such n so we are collecting all the M so this will give us if we write it out explicitly one will fall into this set the next number that will fall into the set is 4 then 9 and then 16 and then 25 and so on right so the notation in blue is a succinct way of writing this informal infinite list which starts with 1 and goes on so we are pulling out the numbers from N one by one checking if they are perfect squares and if so we are enumerated then we also talked about rationals in reduced form we said that there are many different ways of writing the same rational number because if we multiply the numerator and the denominator by the same quantity the the number we are representing doesn't change and we use this fact in order to make denominators same when we did comparisons or arithmetic like addition and subtraction so what are the actual rationals in reduced form so this is a subset of the rations for example 3 by 5 is in reduced form 6 by 10 is not in reduced form because again cancel the 3 right the two and get three by five so if we want numbers and rationals in reduced form first of all we pick up any two numbers which are integers remember that a rational is actually a pair a numerator and a denominator which are integers so every rational looks like this P by Q right but we don't want any such P by cube we want P by Q such that they don't have any common divisors other than one so recall the GCD is the greatest common divisor it is the largest number that divides both P and Q and what we want is that P and Q have no numbers which can be divided into them other than one and if the GCD of P and Q is 1 then P by Q is a rational and it is in reduced form because the DCD is 1 right so this is another example of set comprehension in order to define an interesting subset of the rationals one of the things that we will often use with respect to numbers is to define intervals of numbers numbers between something and something else so for instance if you are looking at the integers we might want the integers from some lower limit or some upper limit this for example is an expression which describes the integers between minus 6 and plus 6 right so it says I want all Z which belong to the set of integers such that Z is above minus 6 greater than equal to minus 6 and less than or equal to 6 now we could split this for instance into two conditions we could also say Z is bigger than minus 6 and Z is smaller than 6 and so on so the way in which we write this condition which applies to the thing may vary and all of them could be equivalent to each other so we will not be very pedantic about what syntax we used to write there so for instance in the previous case here we could have just read written X is even instead of X more to 0 okay so we will not worry too much but it's just that we have this format where we take the underlying set we pick out all elements make it satisfy condition if it satisfy the condition it belongs to a subset so intervals are more interesting when we talk about real numbers and one of the intervals that we really often want to talk about is the interval between 0 and 1 so 0 to 1 is quite into because we will often talk about probabilities for instance in probabilities range between zero and one so what can we do between zero and one well first of all we can take all the real numbers between zero and one including both zero and one and this is called the closed interval the closed interval means in this case it includes the endpoints so if I draw this as a number line for instance so normally I have zero one two minus one and so on so this is my number line so then this closed interval says I want all the numbers from zero to one including zero and one so this is my closed interval right so what we write is take all our in the set of reals such that 0 less than equal to R and R less than equal to 1 so R must be between 0 and 1 it could be zero and it could be 1 if we want to exclude the endpoints then we get what is called an open interval and the way we draw an open interval if we want to draw it in a pictorial way is to emphasize that the endpoints are missing by drawing a circle there so we draw a circle to indicate that those are not included so if we start to fill in the circle corresponding to the endpoints that endpoint is included in our interval if we don't fill it in it's not included but formally it is just a set defined using set comprehension and whether it is open or closed depends on whether the qualities is the inequality has an equal to or not whether there is strictly less than or it is less than equal to whether it's strictly greater than or greater than equal to now there is nothing to stop us from including one endpoint and not including the other so we hadn't closed interval which had both endpoints we had an open interval which had both endpoints missing and we could say for instance that an interval is left open so it is all numbers between 0 & 1 it doesn't allow us to use 0 but 1 is included so in notation we will use this so notice that we use this round bracket for open and we use the square bracket for closed so here obviously we will use a round bracket for the open end and a square bracket for the closed end so the left is open so we call this a left open interval so left open interval has all numbers which are strictly bigger than zero but less than equal to one so correspondingly you could have a right open interval okay and what would this be this would be all the are such that R belongs to a set of reals now 0 is less than equal to R we're allowed to include 0 but we should not include 1 right so this is the right open interval so this will be an important part of many discussions so you should be aware of these intervals as representing sets of points in particular the subset of the reals which can be defined using set comprehension so finally let us look at some simple operations on sets which we are all familiar with so the first one is Union so the union of two sets just combines them into a single set so suppose we have ABC as one set and we combine it with CDE then we get a single set and notice that we have some elements which may appear in both sets and they appear only once in the final set because remember that a set has no duplicates right so in the union if we take sets which have some common elements across the two sets they get represented exactly once in the final set so therefore the cardinality of the Union will in general be less than the cardinality of the two sets put together so here we have two three element sets we take the Union we get a 5 element set not a 6 element set because there are some elements which are common and the symbol for union is this U right so X Union U and if we go back to our Venn diagram so remember that we used when diagrams in order to informally look at sets and we talked about subsets so here we have a Venn diagram which represents the left-hand side setlist X the right-hand side this way y and the picture suggests that X is not a subset of Y and Y is not a subset of X but there may be some overlap so this is the general case right generally speaking if I give you two sets there will be some elements which belong only to X some elements should belong only to Y and some which belong to both so this kind of a picture with two overlapping circles or ellipses is a particularly general picture of two sets represented as Venn diagrams even though we are not specifying what the elements are this is a picture so here for instance if we wanted to write out these elements in this particular set if you wanted to write we have a be here see here D here and E here so what this means is that if we look at the circles ABC belongs to the left circle CDE belongs to the right circle but we put C in the portion which is covered by both circles to indicate that it isn't the common portion so this gray shaded area in this particular case represents the union of two sets so the corresponding thing which takes up only the elements which occur in both sets as you know is called intersection so intersection is written with the upside down version of the Union sign right so X intersection Y is written like this so here for instance we look at elements turn both sides so we have ABCD intersection ad EF so a is common to both B is not there on the right hand side C is not there on the right hand side D is common to both and if you go to the right hand side Yi is not there on the left hand side F is not there so only a and D are surviving it is it so again if we draw this out as a Venn diagram on the right the shaded portion which is the area which is overlapped by both the circles is the intersection so in this particular case we would write a here because it's in both B here notice the order is not important and in a Venn diagram if we actually put the elements the position is not important so I can put them anywhere okay and then I put a here and F there for instance so this is a pictorial representation of the two sets on the left the shaded area corresponds to the intersection and the non shaded portions are those which are in one set but not in the other another operation on sets is called set difference so in set difference we take two sets and we want to know what is there in the first set that is not there in the second set so for instance we want to know which are the real numbers which are not rational so then we would write in this notation which are the real numbers which are not rational right or which are the rational numbers which are not integers so this is a common thing that we might want to do so we write either this direct subtraction which is the normal minus sign or we write this back slash kind of notation to indicate the set difference so it is all elements in the first set which are not in this it said so here for instance if you look at the first set is there but it is also there in the second set so a is not counted B is there but B is not there in a second set so b is in the set difference c is there c is not there in the second set so C is in the set difference but D for instance appears here so D is not counted so here we have that the first set - the second set has B and C because those are the two elements in the first set which are not in the second set now this is like subtraction not symmetric in the sense that you know that 3 minus 5 is not the same as 5 minus 3 unlike 3 plus 5 right so 3 plus 5 is the same as 5 plus 3 but 3 minus 5 is not the same as 5 minus 3 so if it a union for instance then why Union X is equal to X Union Y right and Y intersection X is equal to X intersection Y because this it doesn't matter which side you take from because finally you're going to look at all elements which I as a common to both side or include it in both sides now here if I take the reverse if I take a d e f right and I subtract out the elements from ABCD then I would see that again a would disappear so the same elements disappeared because the common part is the same so a would disappear and D would disappear because these are the parts which are on both sides but what survives now is EF so when I do it in the other way around I get the elements on the right-hand side which are not on the left-hand side so in said difference the order of the LM the sets in the expression matters X minus y is not the same as Y minus 6 just like in subtraction and here we have a picture right so this shows us this picture it says that you take everything in X and you remove everything that also includes so in particular you remove all these elements which are in the intersection and that gives us X set - y and finally we often talk about the complement we say those numbers that are not prime so those numbers that are not prime in particular are called composite numbers so composite number is defined to be a number which has factors other than 1 and so any number which is not prime has more than two factors so such a number is called a composite number so clearly a number is either a prime or it is not a prime so either it is prime or it is a composite so the composite numbers are disjoint from the prime and there are all the numbers that are not prime so this is what we mean by complement complement means the opposite side it means everything else but complement is a very comp is not very straightforward in set theory because complement with respect to what so if I say numbers that are not prime but I don't tell you in what set I'm talking about this thing if I look at complement ins for example in the reals it will include all numbers like PI a and E and square root of 2 and so on and that's not what you mean right when I say the complement of the Prime's you are not thinking of rational numbers irrational numbers and so on you're thinking of integers or in particular you are talking about natural numbers which are not primes right so we would always want to define what is called a universe okay so we need a universe with respect to come which we are going to complement so if we say that the complement of prime numbers in the universe of natural numbers then we get the composite numbers so when we say Prime's for instance we the we see this Venn diagram on the right we see Prime's as a subset of the natural numbers so then the gray shaded area is all the composite numbers right but if this was not this but R then we would have various things we would have square root of 2 e and so on sitting here which is not what we intend so whenever you use the word complement you must make sure that you have specified complement with respect to what what is the overall set with respect to which you are negating the set that you have and that is very important so let's wrap up this lecture so we are all familiar with sets as an informal term which we have come across from school level and a set is a standard way to represent a collection of mathematical objects so it's very important to be familiar with the terminology of sets element of subsets of and so on and also the notation the curly brace listing out the elements set comprehension and so on so sets may be finite or infinite and infinite sets are actually quite tricky and interesting and most of the interesting sets that we are going to look at will be infinite because very often we will be thinking of sets in terms of numbers but we will also be thinking in terms of finite things for instance we talked about we could talk about for instance a time table then we might want to know the set of stations at which the train stops or we might want to look at a shopping list and we might want to look at the set of items that the store has in its inventory so sets are a very useful way to talk about collections of objects infinite collections are important because numbers are infinite but other finite collections are also important from a computational and data science point of view so we saw that we have some useful notation like set comprehension which allows us to define subsets of infinite sets and we have these standard operations on sets like Union intersection set difference and complement which allow us to take sets and combine them in many different ways so it's important that you get used to all these notions as I said because these notions are used implicitly throughout mathematics and these are not difficult notions is just a question of understanding the notation and understanding exactly what happens when you apply each of these operations