- [Instructor] Hi, we've got some material coming up
that involves sets,
we're gonna look at equivalence relations
and equivalence classes, disjoint sets and so on.
And so I thought it would be helpful
if we just had a quick review of sets.
If you're totally on top of sets, then you can skip this.
If you want a quick refresher, it can't hurt,
but we're just gonna go over the rudiments of sets
so we have the foundation that we need
to cover the material that's coming up next.
So again, a lot of this is gonna look
pretty familiar to you.
So let's start with a set.
A set is an unordered bag of stuff, basically.
And sometimes we draw pictures of sets
with some shape that represents the boundary of a set.
And inside the boundary is all the stuff
that belongs to the set.
So here we have the set of all capital letters
in the English alphabet.
And the stuff outside the boundary
is all the stuff that's not in the set.
The lowercase letter d here is not an element of this set.
Here's a set of some foods,
and we refer to contents of a set as the elements of a set.
So pizza is an element of the set of foods.
And so is pretzel, and so is cheese, okay?
Now, a set may have just one element.
If so, we call this a singleton, this is a singleton set.
Sets can be empty too.
That is a set might not have any elements,
in which case we call it the empty set,
and we denote it with this symbol here.
An empty set is a set that has no elements.
Now, let's take this set that we saw before
and we'll give it a name, A, just for notation purposes.
And we'll say that pretzel is an element of A,
this symbol here indicates that this object here
is an element of the set that we called A.
So yep, pretzel's in there, there's A,
pretzel is an element of A.
We strike through that symbol
to indicate that something is not an element of A.
So here we have the sailing ship,
and the sailing ship is clearly not an element of this set.
So we strike that through
and we read this sailing ship is not an element of A,
or sometimes not contained in A, same thing.
Now, we call the number of elements in a set
the sets cardinality, and we write this with two bars.
It looks like absolute value notation.
But when we're talking about sets, when this A is a set,
we're talking about the cardinality of the set,
the number of elements in the set.
So here we have one, two, three, four, five,
the cardinality of A is five.
Do keep in mind that some sets are infinite.
For example, the set of integers.
We'll get to that in a minute.
Now, what can we do with sets?
Well, we have some operations on sets
and the two most basic are union and intersection.
We can take the union of two or more sets,
and the result of the union will be another set
that contains all the elements in the sets under union.
So here we have the set, we take the union with this set,
and we get a result that contains
all of these elements, okay?
We can also take the intersection of two sets.
The intersection of two sets consists of the set of elements
that are in all of the sets under intersection.
So here we have the set here, here we have the set here,
this is the symbol for intersection, and this is our result.
Why?
Well, because the football, the American football
is in both sets, and the volleyball is in both sets,
but those are the only two elements
that are common to both sets, that's the intersection.
Now, you may have seen Venn diagrams before,
and Venn diagrams are commonly used
to indicate such an intersection.
They don't have to, but they're commonly used for this.
So here we see the same two sets,
and the intersection is shown
as the part where the interiors of those sets overlap.
That's a Venn diagram.
Here's another example.
We have the set of all things that are red,
we have the set of all flowers,
and roses here sits in the intersection.
Now, two sets may not have an intersection
or I should say their intersection is empty.
And that is that two sets have no elements in common.
And if two sets have no elements in common,
we call them disjoint.
So here's the set of all football teams.
Here's the set of things in my top desk drawer.
And you see, they have no common elements,
there is no intersection.
So we would write A intersection B is the empty set.
That's assuming that we call the set of all football teams A
and the set of all things in my top desk drawer B.
A intersection B is the empty set.
These two sets again are disjoint.
Now, sets can be contained within sets.
In which case we can speak of subsets.
So, here we have the set of all vertebrates,
those are animals with a backbone.
And the set of all mammals is a subset
of the set of all vertebrates.
And the set of all cats is a subset
of the set of all mammals.
And the set containing fluffy is a subset
of the set of all cats, and so on.
And we have a convenient notation for writing this.
We have a subset symbol, this is a subset symbol.
So here's the set containing fluffy.
We indicate a set in curly braces,
and this set is a subset of the set of all cats,
which is in turn a subset of the set of all mammals,
which in turn is a subset of the set of all vertebrates.
So as far as that notation goes,
we have two flavors, basically.
We have this symbol, which is meant to be a strict subset.
Now, some authors will use this differently,
but this is how it's most commonly done, I believe.
And this is certainly the way I'll present things.
This symbol means that it's a strict subset.
It means it's not coincident with all cats.
The set containing fluffy
is smaller than the set of all cats.
So the set containing fluffy
does not equal the set of all cats, this is a strict subset.
And we use this symbol, which is also true.
You can think of this as subset or equal to,
and that's also true in this case,
but it's not as strong a claim, right?
Now, some sets are so commonly used and so important
that we give them their own special symbols.
This is of course for mathematics,
but we use these in computer science quite a bit,
especially the first two.
This symbol or double strike Z
represents the set of all integers.
That would be all integers
positive or negative, including zero.
We get the letter Z from the German Zolan
which means number.
This double strike n symbolizes the set
of all natural numbers.
Those are the counting numbers,
one, two, three, four, five.
And then we also have the double strike R
which represents the set of all real numbers.
And that's again, an infinite set.
Here's some examples, five, 2.2, PI,
negative 17.62 one third.
All of these in fact are infinite sets.
Now, the last thing I wanna cover
is what's called set builder notation,
and this gives us a convenient way
of indicating elements in a set
without having to enumerate all of them,
which can get tedious,
especially if you have very large sets.
So here are a few examples.
First we have the set A, and the set A
consists of all acts that are elements of the integers,
such that we read this bar such that,
and it indicates a condition for being a member in the set
such that x is greater than seven.
So this would be the integers eight and greater.
Here's the set B where we don't specify any underlying set,
so we assume it's the set of all possible objects,
and the condition is y is blue.
So this is the set of all blue things.
And here's another set C,
which is the set of all z such that z has four wheels, okay?
So think about what those are.
Again, in the case of A,
we have the integers greater than seven.
In the case of B, we have the sky,
we have blueberries, we have Neptunes.
There's no other condition other than the y is blue, okay?
And in the last case,
we have things like cars, shopping carts and lawnmowers,
but you see, this as a very convenient shorthand
for writing a set, call that set builder notation,
also sometimes called a conditional notation.
And that's really all we're gonna need for this class.
Subsequently, we're gonna look like I said,
at equivalence relations,
equivalence classes, disjoint sets,
we're going to work with taking the unions of sets.
And this was intended just to give you a quick overview.
See you in the next lecture.