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. 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're starting with. This is done before the such that symbol.
For example, p in the natural numbers such that p is less than 5 is a completely different set to r in the real numbers such that r is less than 5. Two sets are equal if they both contain the same elements. If for all little a in 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 1, 2 and 3 and b contains 2, 3 and 1, we say 1 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 us as readers.
The size or cardinality of a set is the number of elements it contains. So if a contains 1, 2 and 3, then the cardinality of a is 3, 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, 4. B, 4. the set containing 10, 100 and 1000 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 1000 is 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 two 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 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 it can be shown 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 in 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 1 and empty set 2 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 1 and 2 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 the 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 the 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 0 and 1 and b be the set containing 1, 2 and 3. 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 0 and 1, as well as everything in B. which is 1, 2 and 3. So altogether and ignoring the repeating one, we have the union of A and B is a 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 one is common to both A and B.
And so the intersection of A and B is the set containing 1. 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 1, 2 and 3 and B be the set containing 3 and 4. We can see that A contains three elements and B contains two elements and the union of A and B would contain 1, 2, 3 and 4 and so has a cardinality of 4. The intersection of A and B contains only 3 and so has a cardinality of 1. 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 B. of A and C separately and then taking the intersection.
This looks a lot like multiplying out the brackets, and 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 or more than 20 degrees, which at first sight doesn't seem to make much sense, but notice that summer or winter is any time 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 to 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 intersect 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 intersects 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 intersect A union C is a subset of A union. B intersect C. Altogether we've shown that A union B intersect C is a subset of A union B intersect with A union C and that A union B intersect with A union C is a subset of A union B intersect C.
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 & 5 and b is the set containing 2, 4, 6 and 8, then a minus b is the set containing 1, 3 and 5 since we've removed the 2 and the 4 that were in b. b minus a is 6 and 8 since we've again removed 2 and 4. 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 B, 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 a discussion about dogs, when thinking about all non-sheepdogs, 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 dice 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. 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 some set 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 A 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 complement of dogs union cats is equal to dogs complement intersect cats complement. 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 or the complement of less than 100. 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 100 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 zero 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 0 isn't a subset of A, it's an element as we've seen already.
In fact, the set containing the set containing 0 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 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 itself, the set containing 0 and the set containing 1. 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 1, 2, 3 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 a 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. 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 a set. Thanks for watching.
I'll see you next time. Oh