Section 8.1 Subsets
When we defined sets way back at the beginning of the course, we saw that the only thing we can ask a set is
Is this object in the set?
and the set can only respond to us with either
We can make this simple structure much more interesting by enriching it using some of the logic we have learned. Consider the sets
We see that every single element of
is contained in the set
So rather than asking one-by-one whether or not individual elements of
are contained in
we can instead ask if all the elements of
are contained in
Equivalently, we can ask “Is
contained in
”. This is the idea of
being a subset of
Definition 8.1.1.
We say that
is a
subset of
if every element of
is also an element of
We denote this
If
is not a subset of
then we denote this as
Further, if
is a subset of
but there is at least one element of
that is not in
then we say that
is a
proper subset of
We denote this by
If
then
is a
superset of
which we can write as
Similarly, if
then
is a
proper superset of
which write as
Two sets
and
are equal if
is a subset of
and
is a subset of
That is
The empty set is a subset of every set. That is, for any set
we always have that
That
is equivalent to saying that if we take any element of
then it is also an element of
That is
If
then there is at least one element of
that is not in
That is
Since two sets are equal when they are subsets of each other, we prove set equality using a two part proof. The first part proving that
and then the second part showing that
Example 8.1.2.
Let
What are all the subsets of
Result 8.1.3.
First lets write a few elements of these sets
The result we are trying to prove is that
This is equivalent to showing that if
then
(which is essentially saying that if an integer is divisible by 6 then it is divisible by 2). Hence to prove the result we are going to assume that
and then work our way to proving that
First up we make sure that the reader knows we are going to take
to be the sets in the statement of the result.
Then this means that
is an integer that is divisible by 6. That is
for some
We need to show that
This is equivalent to showing that we can write
where
is some integer.
But we know that
and since
we are done.
Of course, we aren’t really done until we write thing up nicely.
Proof.
Let be the sets defined in the result. Assume that Hence we can write where But now since and is an integer, we know that Thus
The following result expresses that being a subset is a transitive relation. We’ll see much more about transitivity in the near future.
Result 8.1.4.
Let
be sets. Then if
and
then
We should start by breaking things down carefully because there are a few nested implications hidden inside this result.
The hypothesis is
and
We can, in turn, write this as
The conclusion says
This can similarly be written as
Since we are trying to prove an implication, we start by assuming the hypothesis is true. So we assume that
Notice this we do
not assume that
and
rather we are assuming that the above implications are both true
89 .
Now we want to prove that the conclusion is true, namely that
This we can do by assuming that the hypothesis is true and showing the conclusion.
90 That is, assume that
and then work towards showing that
Since now we have assumed that
and
we know that
And then, in turn, our assumption that
we know that
Precisely what we need!
Oof! The above analysis becomes much easier with practice.
Proof.
Assume that and We wish to show that now so let Since we know that we know that And since we know that we know that Hence we have shown that
So even though our scratch work took some twists and turns, our proof is quite succinct.
Once you start thinking about subsets of a set
it is quite natural to ask
91 “What are all the subsets of a given set?” The resulting
set of sets is called the
power set. This set will be very important when we look at the cardinality of sets, particularly the cardinality of infinite sets. But first, we should really give it a precise definition.
Definition 8.1.5.
Let
be a set. The
power set of
denoted
is the set of all subsets of
Note that the elements of
are themselves sets, and
When we get to the chapter on cardinality we’ll prove that if
is a finite set with
then
We will also prove an important result about the power set of an infinite set.
Example 8.1.6.
Result 8.1.7.
Let
be sets. Then
if and only if
Since this is a biconditional we need to prove both directions. Lets start with the forward implication and then turn to the converse.
So we assume that
and we want to prove that
This is equivalent to showing that
— note that
is now itself a set (which is why
92 we’ve used a capital
rather than a lower case
).
So just as was the case in the previous proof, we assume that the hypothesis,
is true. This means that
This, in turn, implies that
and so
Okay, now lets look at the converse.
Hence
must be a subset of
— by definition of the power set.
As always, once the scratch work is done, its time to write up.
Proof.
We prove each implication in turn.
Assume that and let Hence By our result above, this, in turn, implies that By the definition of the power set, this tells us that Thus we have shown that
Now turn to the converse and assume that Since this implies that But, by the definition of the power set, this tells us that and we are done.
Since we have proved both implications we have proved the result.
We can think of forming the power set as an operation on a set. Since it is the only operation we have discussed so far, we could keep applying it to see what sorts of things we get. That is, what is the power set of a power set of a power set of a… This is not an entirely silly idea, and we will look at this when we get to the chapter on cardinality, but exploring other set operations is a better use of our time at present.
And, as you have now memorised, an implication is only false when its hypothesis is true and its conclusion false.
Equivalently, we know that either or When we have precisely this case. On the other hand, if then the implication is true since the hypothesis is false. So it is only when that there is work to do.
Well, the author thinks it is a natural question and hopes you think it is one too.
The power of good notational conventions!
We could refer to this by number as well — that is probably a good idea if the result isn’t so close by within the document. However, it is just up there so referring to it as “previous result” is fine.