Now we talk about sets. So a set is a collection of elements.
This is a very vague definition,
but it's definitely good enough for us,
and we can do mathematics with this definition.
Now, you can get into some sticky situations if you're not careful
with what you do. You can define some
paradoxical things.
But for now let's just take for granted a set as a collection of elements,
and we have some examples of some sets.
So for us, the natural numbers begin with 1
so I wanted to emphasize that here.
For example, we also have the rational numbers.
The rational numbers are fractions a over b,
real numbers, such that
a is an integer, b is an integer and b is non-zero.
We say here R is the universe,
or sometimes the universe of discourse, either way.
That's an example of defining the rationals.
We have the examples of the empty set,
so the first one’s an empty set, second one's the empty set,
and the third one is not the empty set.
This is the set containing the empty set,
so the third set has one element in it,
the other two do not have an element in it.
There's a big big difference even though they look very similar,
so I wanted to throw this out here just to remind you, okay
this thing is different this is a set consisting of a set, that's possible.
On here, it's the set consisting of the empty set.
Last thing I want to mention is this notation.
So x is in S and x is not in S.
For example, 2 is inside the natural numbers, so
2 in N is a possibility,
and 0 is not in N,
for us.
This is important in any proofs with sets.
What do I mean by that? Well so sometimes
if you get stuck in a set proof question,
one thing that you might want to try to do is say, “Okay well
I have an element,
however I have it, it’s this element x, let's say, in some bigger set,
and now I know it's either in the smaller set, or it's not in the smaller set.
And doing things like that might help you to
progress in the proof, right?
Elements are either in sets or not in sets.
There's no limbo for elements and membership in sets.
You're either in or you're out, there's no on the fence.
So that's the rough intro to sets.
Some other set examples, so
we did some exercises in class with these two,
so I wanted to give two examples. The two most important ones that we did in class.
Set of even numbers between 5 and 14 inclusive.
Well if you're just dealing with the set of even numbers between 5 and 14,
you can just write down all the even numbers between 5 and 14.
There's no problem. You don't have to use
set notation if you don't want to.
So if you don't it's just 6, 8, 10, 12, 14. That's perfectly fine.
If you do use set notation, then something like this will work, for example
n is a natural number
such that 5 is less or equal to n is less or equal to 14,
and 2 divides n. So here again we see that divisibility sign;
it’s gonna pop up everywhere in this course.
As another example, all odd perfect squares.
So here we're gonna do it in a different way.
So here we're going to define
the members to be the elements of the form 2k plus 1 squared,
and here what's k? Well k is a member of the integers.
You can also do it as k as a member of the natural numbers,
the difference here is that when k is in the integers,
you're going to get multiple representations of the same element of a set.
So remember that sets don't have overlap.
So, I mean, you can't have like
three copies of 1 in your set.
Once 1 is in your set, it's in your set. That's it.
There's not multiple levels of 1.
There's just 1 and that's it, okay?
So here even though there's multiple ways to write the same element,
it still describes the same set, that's fine.
Multiple numbers have different representations,
there’s sort of no avoiding this.
Well in this case there is avoiding it but in many cases it's not.
I guess I should say, so be careful here.
If you use N you actually miss 1, I really should say 2k minus 1.
Not a huge deal.
Okay. Set operations.
So let S and T be sets. We have a couple of definitions,
so if you see
the octothorpe, or the pound symbol, S
or if you see two vertical bars with the [letter] S,
that is the size of the set S.
The second notation is more common -
magnitude is more common than this pound notation,
but you might see either or.
S union T,
this is a set of elements x such that
x is in S [or] T.
S intersect T, this is a set of elements in both S and T.
So notice the similarity between the logic notations.
Union and ‘or’
and intersection and ‘and’.
They're similar and they're not completely independent, but
they are different so don't use
'or’ when you're talking about sets,
and don't use union when you're talking about statements.
S minus T is set difference, so x is in S and x is not in T.
S bar or S c. I think we’re gonna use
S bar in this course, but S c is also common.
This is the complement of S, so what does that mean?
It means x is inside my universe U such that x is not in S.
So if you use that, you can actually write this with set difference,
it's just to set U minus S.
The last thing I want to talk about is Cartesian Product, so S cross T.
It’s the set of ordered pairs
x comma y such that x is in S and y is in T.
This is important, right, so
notice that the elements x and y
are completely independent of themselves, so
even if you take something like Z cross Z,
it's not just all the elements of the form
(1,1), (2,2), (3,3), (4,4), etc.
(1,2) is in that set
and (2,1) [is] in that set, right? Those are two different elements in that set,
(1,2) and (2,1).
So it's the set of ordered pairs, order matters in a Cartesian Product.
Something to write about. Again, this is just ways to combine sets
to make new sets from old sets.
Okay, so that's the end of set operations.
A little bit more of set terminology.
So there are a lot of symbols in this notation. Now,
if you managed to find this video, the chances are you've
already looked at the Math 135 Resources Page,
and know that there are symbol cheat sheets.
You might need these for the first little bit
just to help you remember what all the symbols mean.
Again, it's a bad idea - really bad idea - to
try to answer a question if you don't know what the symbols mean,
if you don't understand the notation.
Best advice is: don't do it.
If you don't understand the notation, don't try to answer problems.
Try to understand the notation first and then try to answer the problem.
It's far easier that way.
Okay, so let S and T be sets.
Then S is a subset of T,
that's denoted by this symbol, and that means that every element of S is in T.
Here S is a proper subset, or a strict subset, of T. So
S is a subset of T and there's some element in T that's not in S,
so they're not equal.
Equality we'll get to in a minute.
So S contains T, and S properly contains T.
It's similar except now T is a subset of S
and T is a subset of S and S is not equal to T
so there’s some element of S that's not in T.
S equals T, what does that mean?
So, set equality, this is sort of the…
this is something that's really really important here, set equality.
Now what does this mean? S equals T
It means this. It means that S is a subset of T, and T is a subset of S.
That's what set equality means.
It's different than equality of integers
or equality of variables, things like this.
The equality operator does get overloaded.
So S equals T
does mean that S is a subset of T and T is a subset of S.
So if you are asked to prove that two sets are equal, you must show
that S is a subset of T and T is a subset of S.
We're gonna see an example that we saw in class on the next slide
that helps, again,
reiterate this fact and emphasize it.
So show that the set S equals the set T
if and only if S intersect T equals S union T.
That's what we're going to prove.
This is an ‘if and only if’ proof so we have to prove
the implication and its converse.
So the implication is, “Suppose that S equals T
and we'd like to show that S intersect T is equal to S union T.”
To show this, we need to show that
S intersect T is a subset of S union T
and that S intersect T contains S union T.
How do we show the first thing?
So to show that S intersect T is a subset of S union T,
start with an element of S intersect T
and show that it must be in S union T.
First, suppose that x is inside the intersection.
Well what does that mean? That means that x is in S and x is in T.
Well if x is in S and x is in T,
then definitely x is in S or T,
and so x is an element of S union T.
Next, suppose that x is an element of the union,
so x is in S or x is in T.
Well what does that mean? Since S equals T…
so this is something that we didn't need in the first half of the proof,
but in this half of the proof
we're going to use that fact. Well if x is in S, then X is in T,
and if x is in T, then X is in S because S is equal to T.
So, in either case, we know that x is in S and x is in T.
And so thus, x must be in the intersection.
So what have we shown? We showed that an arbitrary element
in the union must be in the intersection,
and previous to that we showed that an arbitrary element
of the intersection must be in the union.
Here I've used the same letter x to mean different things, okay?
You could have chose different letters.
The way I'm viewing this and the way I'm reading this
is that x ends after the bullet,
so the scope of x is only each bullet, okay?
It's probably sloppy, you should probably use different letters. It's not a huge deal.
It might be a huge deal if you start confusing them.
For me, I guess I know what I wrote, so I understand what I'm doing.
Just keep that in mind though, okay?
Okay.
So that shows the direction, if S is equal to T, then
S intersect T is equal to S union T.
Now we need to start… now we need to prove the converse.
So what does the converse say? Well we need to start with the conclusion,
S intersect T equals S union T,
and we want to show that S equals T.
How do we do that? We show that S is a subset of T
and T is a subset of S, okay?
Don't try to make your own rules up.
Try to follow this reasonably mechanically and you should
struggle less with sets. So,
if we're showing that S is a subset of T,
start with an element of S, an arbitrary element of S,
well if x is in S then x is inside S union T
because well x is in S so it's definitely in S or T,
and S union T is equal to the intersection.
But if x is in the intersection, then x is in S and x is in T.
So hence, X is in T.
Now in class, I mentioned well this is... you can actually
use the word "similarly", right? So now what I'm going to do is
I'm gonna just replace this letter S
with this letter T, and go through the proof exactly the same way.
x is in T so therefore x is in S union T,
which is equal to the intersection. Hence,
instead of x being in T, now x is in S
and that proves the inclusion S is a subset of T.
Now I’ve proved that S is a subset of T, T is a subset of S,
therefore they're equal, and that's the end of it.
So that is an ‘if and only if’ proof with sets,
so there's a lot on this slide; a lot to digest.
If you understand this slide and what happened here,
I feel like you're in pretty good shape with both sets and ‘if and only if’ statements.