a set is a collection of objects we call elements that could mean physical objects thoughts ideas and concepts including mathematical objects which will of course be the main focus for us possibly more importantly a set is a way of packaging up objects which share similar properties in a meaningful way consider the set of triangles we can unambiguously state whether something is or isn't in this set this is in so is this but this shape isn't it's not a triangle this lack of ambiguity in what is or what isn't in a set is foundational to set theory we can also make claims about the set and assess again without ambiguity whether they're true or false it's true that an element of the set of triangles has three sides but it's not true that the sum of the internal angles is 360 degrees a set containing the numbers 1 2 and 3 would be written like this with curly brackets and the elements separated by commas we can name the set in this case if we say a is equal to the set 1 2 and 3 we can just refer to the set as a which is much easier than saying the set containing 1 2 and 3 again and again to express symbolically that an element belongs to a set we use this symbol for example if a is the set containing 1 2 and 3 then 1 is in a and 2 is in a but 4 is not in a and we use the symbol for in but with a line through it to denote not in [Music] in most cases we don't write out all the elements in a set but we'll write a shorthand description using something called set builder notation for example the set of prime numbers could be written as capital p is the set of little p such that little p is prime here the little p is a variable which must satisfy some criterion we call the predicate since its belonging to the set is predicated on this criterion in this case the predicate is being a prime number also notice we have a shorthand for the phrase such that which is this vertical line it's good practice when dealing with sets of numbers to declare explicitly which sets you starting with this is done before the such that symbol for example p in the natural numbers such that p is less than five is a completely different set to r in the real numbers such that r is less than five two sets are equal if they both contain the same elements if for all little and capital a little a is also in b and for all little b in capital b little b is also in capital a then the sets a and b are equal this definition means that the order of the elements doesn't matter we only need to show that they share the same elements so if a contains one two and three and b contains two three and one we say one is in a and it's also in b 2 is in a and it's also in b and 3 is in a and it's also in b we then do the same for all the elements in b and so we've shown that a is equal to b it also doesn't matter if the elements are repeated like before as long as every element in one set can be shown to also be in the other we still have equality generally we just write the elements in a way that's easiest to read which usually means without repetitions and often in some sensible order but just to be clear it makes no difference to the set just to use as readers the size or cardinality of a set is the number of elements it contains so if a contains one two and three then the cardinality of a is three and we denote the cardinality of a set with two vertical lines if a set has an infinite number of elements like the set of prime numbers for example then it's perfectly fine to write the infinity symbol as the cardinality of the set a set is a subset of another if all of its elements are also elements of another set for example if a is the set containing 2 4 and 6 and b is the set containing 1 2 3 4 5 and 6 then since the elements 2 4 and 6 which are in a are also in b then a is a subset of b and we use this symbol to denote a being a subset of b if b equals the set little b in the natural numbers such that b is even which of these are subsets of b a for b the set containing 10 100 and a thousand or c the set containing a such that a is equal to 2k where k is in the natural numbers well 4 is an element of b but not a subset it's really easy to get mixed up between elements and subsets but a clue is that the word subset contains the word set and subsets are always sets themselves the set containing 10 100 and 1 000 is a subset of b because these are all even numbers the set of a such that a is equal to 2k where k is in the natural numbers is actually another way of writing the even numbers since 2 times any number is even and so this is equal to b but all the elements of this set are also in b so technically it is a subset of b this highlights a general property about subsets all sets are subsets of themselves we can also take this further to give a different definition of set equality if a is a subset of b and b is a subset of a then a is equal to b this is essentially reframing the earlier definition of set equality that all the elements in one must also be in the other but in the language of subsets if a is a subset of b but a is not equal to b then we call a a proper subset of b this of course implies there are elements in b that are not in a otherwise they'd be equal in some textbooks a proper subset is denoted like this but sometimes the same symbol is used for subsets that might be equal so you need to infer from context which they mean some textbooks use this symbol for proper subsets which is more explicit about them not being equal a really nice and intuitive property of subsets is that if a is a subset of b and b is a subset of c then a is a subset of c it's pretty simple to prove but probably best illustrated visually if all of the elements in a are in b and all of the elements in b are in c then all of the elements in a are in c this property shows up a lot in sets of numbers for example all odd numbers are integers and all integers are rational so we can be sure that all odd numbers are rational the empty set is a set which contains no elements it's a special set we give its own symbol and it has its own properties firstly the empty set is a subset of any set let a be a set since the empty set has no elements all the elements in the empty set must also be an a therefore the empty set is a subset of a the second property of the empty set is that it's unique let empty set one and empty set two be two empty sets since the empty set is a subset of all sets we already can deduce that empty set 1 is a subset of empty set 2 and empty set 2 is a subset of empty set 1. this is the definition of equality we saw earlier if empty sets 1 and 2 are equal then we only really had a single unique empty set to begin with and so we can drop the subscripts one and two and just call them the empty set two sets may share some elements we indicate the elements in common to both sets using the overlap of two circles in what's known as a venn diagram the union and the intersection are two ways of combining the elements in two sets into a new set the union of two sets a and b is a set containing all of the elements in a as well as all of the elements in b we write this formally as a union b where the large u shape symbolizes the union is the set x such that x is in a or x is in b the word or is the most important bit here this is like taking all of the elements indicated in this shaded area of the venn diagram and notice that it includes elements in both a and b the intersection of the sets a and b is a set containing elements that are in both a and b the intersection of a and b or a intersect b for short is symbolized with an upside down union symbol and is formally defined as x such that x is in a and x is in b the word and being the most important bit if the elements of the intersection must be in both a and b then we're talking about the overlapping part of the venn diagram let a be the set containing zero and one and b be the set containing one two and three what is the union of a and b and what is the intersection of a and b the union of a and b contains all the elements in a so zero and one as well as everything in b which is one two and three so all together and ignoring the repeating one we have the union of a and b is the set containing 0 1 2 and 3. remember just to be clear we get a set containing 0 1 2 and 3 from taking the union not just the elements 0 1 2 and 3. the intersection of a and b will contain only elements in both a and b in this case only 1 is common to both a and b and so the intersection of a and b is the set containing one let's do a second example let a be the set of little a in the natural numbers such that little a is odd the odd numbers for short and b be the set of even natural numbers what is a union b and what is a intersect b the union of a and b will be a set that contains all the odd numbers and all the even numbers which is the set of all natural numbers the intersection of a and b would contain only numbers that are both odd and even there aren't any numbers which fit this criterion and so the intersection of a and b is just the empty set let's look at some properties of the union firstly the union of any set a with the empty set is just a since the empty set has no elements we have a similar situation with taking the union of any set a with itself which just gives a if a is a subset of b then the union of a and b is just b because all of the elements in a are already in b and so we don't add anything new to the union another example is that the union of a and b is the same thing as taking the union of b with a the final property of unions is if we have three sets a b and c we can exchange the order we take the union by moving the brackets and we'll still get the same outcome on the left hand side we take the union of b with c first and then take the union with a we end with all the elements in a as well as all those in b and c taking the right hand side we start with the union of a and b and then take the union of that with c and just as before we get all the elements from all three sets this rule actually generalizes to any number of sets and you can take the union in any order you like some properties of the intersection now remember this is all the elements common to both sets firstly for any set a the intersection of a with the empty set is just the empty set since the empty set has no elements it can't have any elements in common with any other set the intersection of any set with itself is just itself if you remember this is exactly the same as with unions if a is a subset of b then the intersection of a and b is just a the small set of the two as indicated by the shaded area this is because the elements in a are also in b and just like with the union a intersect b is the same as b intersect a that is the order of the sets doesn't make any difference to the intersection again like with the union the fact that the order doesn't matter extends to three or more sets with brackets we can see that b intersects c then the intersection of the result of that with a is the same as taking the intersection of a and b and then the intersection of that with c in both cases we end up with a set containing the elements found in a and b and c the shaded area in the middle let's look at the cardinality of the union and intersection of two sets because there's a useful identity let a be the set containing one two and three and b be the set containing three and four we can see that a contains three elements and b contains two elements and the union of a and b would contain one two three and four and so has a cardinality of four the intersection of a and b contains only three and so has a cardinality of one now notice that the two on the left added together equals the two on the right this isn't coincident but it's always true the identity is usually written as the cardinality of the union of a and b is equal to the cardinality of a plus the cardinality of b minus the cardinality of the intersection of a and b also because we're taking away the cardinality of a intersect b we can also write this as an inequality a union b is less than or equal to the cardinality of a plus the cardinality of b we also have a couple of identities involving both unions and intersections for three sets a b and c taking the union of a with the intersection of b and c is the same as if we take the union of a and b and the union of a and c separately and then taking the intersection this looks a lot like multiplying out the brackets so it's relatively easy to remember but how do you remember which order the union and intersection signs come in luckily you don't need to this is because the identity works if we exchange the unions for intersections and the intersections for unions here the intersection of a with the union of b and c is the same as the union of a intersect b with a intersect c as we've already discussed these identities are similar to multiplying out the brackets and this kind of property in general is known as distributivity or the distributive property you might be thinking at this point how are these identities useful so i'm what they call a fair weather cyclist i only cycle in the summer or in the winter when it's warmer than 20 degrees celsius let's make sets of these potential days i could ride a bike we have summer winter and those that are more than 20 degrees c the shaded area is therefore the days that i can cycle and we could write this as the union of summer and the intersection of winter with days warmer than 20 degrees we can use the distributive property we've just seen to work with the logic of a given statement so if we have the set of days in the summer or winter and more than 20 degrees the identity says that this must be the same as summer or winter and summer are more than 20 degrees which at first sight doesn't seem to make much sense but notice that summer or winter is anytime and summer or more than 20 degrees is the days when i cycle we're ignoring other seasons in this example and we're taking the intersection of these so we get something like i cycle any day of the year but only when it's summer or more than 20 degrees which actually makes sense and is another way of saying the original statement but what makes this more satisfying is that we've come to it from a set theoretic identity which shows how we might use set theory to manipulate logical statements now consider the statement i only wear white or blue shirts here we have three sets shirts blue clothes and white clothes and for specifically blue and white shirts we take the intersection of the union of blue and white clothes with shirts and so the formula might look something like this like before we can use the distributive rule to play around with the logic so shirts and blue or white becomes blue shirts or white shirts this can now be interpreted as i only wear blue shirts or white shirts it doesn't feel too different to the original statement but again it's quite satisfying that it comes straight out of the set theoretic rules but before we move on from unions and intersections i want to show you how we can mathematically prove a statement such as this one remember how earlier we showed that if a is a subset of b and if b is a subset of a then a is equal to b well here we can use that exact method to prove this equation we'll show first that a union b intersect c is a subset of a union b intercept with a union c and that a union b intersected with a union c is a subset of a union b intersect c which implies they're equal to one another first suppose we have an element x which is in a union b intersect c well it's either in a or it's in b intersect c which would mean it's in both b and c in either case x is in both a union b and a union c because if it's in a this is true and if it's in b it's also in c so it's still true so this means that a union b intersect c the thing we started with is a subset of a union b intersected with a union c since we've shown any element of the left hand side is an element of the right hand side now suppose x is in a union b intersect with a union c this means that x is in both a union b and a union c if x is not in a then it must be in both b and c so it must be in the intersection of b and c and otherwise x is in a so x is in the union of a and b intersect c which means a union b insect a union c is a subset of a union being sect c altogether we've shown that a union b insect c is a subset of a union b insect with a union c and that a union b intersect with a union c is a subset of a union b insect c which proves they're equal the set theoretic difference of two sets a and b is a set of all elements in a that aren't in b it's usually denoted by a backslash and can be thought of as like subtracting b from a i'll call it a minus b for the rest of the video but remember this is just to make things easier to say for example if a equals a set containing 1 2 3 4 and 5 and b is the set containing 2 4 6 and 8 then a minus b is the set containing one three and five since we've removed the two and the four that were in b b minus a is six and eight since we've again removed two and four if b is a subset of a the set theoretic difference of a and b is called the complement of b with respect to a it's usually denoted with a superscript c above the subset b or as c with b in brackets like a function why is this important enough to give it its own name well it's kind of like a background to be the things outside of b in general it's elements not in the set we're interested in but not totally irrelevant here is where we introduce the universal set the universal set u is a set of all elements that are relevant for some given topic of interest if our set a isn't the subset of something specific we usually assume the complement to a is the universal set and what that universal set is depends on context this quote from the foundations of mathematics by stuart and tall sums it up nicely in the discussion about dogs when thinking about all non-sheep dogs it's pointless to worry about camels imagine we're throwing two dice let a be the number of outcomes of rolling a pair of dice in which both dies show the same number a sensible universal set in this case would be the set of all possible outcomes of rolling two dice and the complement of a would be the outcomes where each die shows a different number [Music] here are some other examples of complements the complement of the set of odd numbers is the even numbers and the complement of the rational numbers is the set of irrational numbers notice with the complement we often get something that feels like the opposite of the original set and that's because the complement negates the predicate with our set builder notation we have a set a which contains all x from sunset b such that it fulfills some predicate p well the complement of a the things not in a must by definition not satisfy p so the complement of a is the elements x in b such that p isn't true and we have this symbol before p to say it's not true for example if a is the set of animals that are dogs then the complement of hay is animals that aren't dogs let a and b be subsets of the universal set u because nothing is in the empty set its complement is u similarly the complement of u which contains everything is the empty set here's an interesting one the complement of the complement of a set returns the original set that's because taking the complement of a leaves all the things in u but not in a taking the complement again we can see that all that's left in u but not in our current set is a if a is a subset of b then the complement of b is a subset of the complement of a it's easy to show visually why this is true since everything in a is also in b there are things in b that aren't in a i'm assuming that they're not equal here that means that these elements that are in b but not in a will turn up in the complement of a but not the complement of b and so we end up with the complement of a containing everything in the complement of b and more we now have the famous de morgan's laws first the complement of a union b is a complement intersect b complement and second the complement of a intersect b is a complement union b complement let me show you some examples so you can see what's going on here let u be the set of all animals and let a be the set of dogs and b be the set of cats the de morgan's laws say that the compliment of dogs union cats is equal to dog's compliment intersect cat's compliments animals that are neither dogs nor cats are not dogs and are not cats you can see that this makes sense logically to illustrate the second law if u is the set of natural numbers let a be the set of prime numbers and b be the set of x in the natural numbers such that x is less than 100. using the de morgan's law we get that the complement of prime and less than 100 is equal to the complement of prime numbers are the complement of less than a hundred remember the complement is like changing true to not true and so we get the set of numbers that are not prime and less than a hundred is the set of numbers that are either not prime or greater than 100 notice that we're allowing numbers greater than 100 but only those that are not prime we've had a few examples so far of identities which still work when we switch the intersections and unions this is a general rule that always works and is called the de morgan duality principle given any set theoretic identity involving the union and the intersection if the union and intersection are interchanged throughout then the result will be another valid identity so for all of these identities you've seen so far that they come in pairs you'll be happy to know that you can just remember one of them and exchange the union and the intersections to get a second one the elements of a set may be sets themselves if we have this set a then the set containing 0 is an element of a but not zero on its own since the elements of a are all sets here it becomes tricky to keep track of what's an element and what's a subset the set containing zero isn't a subset of a it's an element as we've seen already in fact the set containing the set containing zero is a subset of a and it's important to really think about the difference in cases like this the power set is a common thing to encounter and it contains all subsets of a given set so let a be a set the power set of a p brackets a contains all sets x such that x is a subset of a so for a equals the set containing 0 and 1 the power set of a would contain the empty set a self the set containing zero and the set containing one we also have what are called indexed families of sets essentially each element which is a set itself is indexed by a number and usually written as a subscript so a being a sub i for i in the set one two three is saying that a contains three sets a1 a2 and a3 and in some cases it might be easier to read if we package things up like this if a is the set containing set 0 set 0 and 1 and set 0 1 and 2 we can write this as a1 a2 and a3 where a1 is the set containing 0 a2 is a set containing 0 and 1 and a3 is the set containing 0 1 and 2. imagine a set containing everything everything in the universe everything you can imagine all the combined knowledge of everyone on earth and more we'll call this set omega because omega contains everything and it itself is something then we have this interesting property that omega contains itself this leads to a kind of infinite regress of omegas within omegas to avoid this we might change the definition of omega and let omega be the set containing all sets that do not contain themselves now assume omega isn't a member of itself by definition then it must contain itself if it does contain itself well it can't contain itself this is known as russell's paradox in fact this is less a problem with how we've built the set and more a problem of how we define what a set is in the first place naive set theory in general does not give any guidance on what constitutes a set mostly we don't need to worry about this but as you've seen it can lead to problems axiomatic set theory aims to navigate the paradoxes of naive set theory by providing a rigorous definition of what a set is in the form of a list of axioms statements something must satisfy in order to be upset thanks for watching i'll see you next time