Skip to main content

PLP: An introduction to mathematical proof

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
Yes.
No.
We can make this simple structure much more interesting by enriching it using some of the logic we have learned. Consider the sets
A={1,2,3}B={0,1,2,3,4}.
We see that every single element of A is contained in the set B. So rather than asking one-by-one whether or not individual elements of A are contained in B, we can instead ask if all the elements of A are contained in B. Equivalently, we can ask “Is A contained in B”. This is the idea of A being a subset of B.

Definition 8.1.1.

Let A and B be sets.
  • We say that A is a subset of B if every element of A is also an element of B. We denote this AB.
  • If A is not a subset of B, then we denote this as AB.
  • Further, if A is a subset of B but there is at least one element of B that is not in A then we say that A is a proper subset of B. We denote this by AB.
  • If AB then B is a superset of A which we can write as BA. Similarly, if AB then B is a proper superset of A which write as BA
Finally,
  • Two sets A and B are equal if A is a subset of B and B is a subset of A. That is
    (A=B)((AB)(BA))
Some things to note
  • The empty set is a subset of every set. That is, for any set A, we always have that A.
  • That AB is equivalent to saying that if we take any element of A then it is also an element of B. That is
    (AB)(aA,aB)(aAaB).
  • If AB, then there is at least one element of A that is not in B. That is
    (AB)(aAs.t.aB)
  • 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 AB and then the second part showing that BA.

Example 8.1.2.

Let S={1,2}. What are all the subsets of S?
  • The subsets are ,{1},{2},{1,2}.
First lets write a few elements of these sets
A={,18,12,6,0,6,12,18,}B={,6,4,2,0,2,4,6,}
The result we are trying to prove is that AB. This is equivalent to showing that if aA then aB (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 aA and then work our way to proving that aB.
  • First up we make sure that the reader knows we are going to take A,B to be the sets in the statement of the result.
  • Assume aA.
  • Then this means that a is an integer that is divisible by 6. That is a=6 for some Z.
  • We need to show that aB. This is equivalent to showing that we can write a=2k where k is some integer.
  • But we know that a=6=2(3) and since 3Z we are done.
Of course, we aren’t really done until we write thing up nicely.
Let A,B be the sets defined in the result. Assume that aA. Hence we can write a=6 where Z. But now since 6=2(3) and 3 is an integer, we know that aB. Thus AB.
The following result expresses that being a subset is a transitive relation. We’ll see much more about transitivity in the near future.
We should start by breaking things down carefully because there are a few nested implications hidden inside this result.
  • The hypothesis is AB and BC. We can, in turn, write this as
    (aAaB)(bBbC)
  • The conclusion says AC. This can similarly be written as
    aAaC.
  • Since we are trying to prove an implication, we start by assuming the hypothesis is true. So we assume that
    (aAaB)(bBbC)
    Notice this we do not assume that aA and bB, rather we are assuming that the above implications are both true 89 .
  • Now we want to prove that the conclusion is true, namely that
    aAaC.
    This we can do by assuming that the hypothesis is true and showing the conclusion. 90  That is, assume that aA and then work towards showing that aC.
  • Since now we have assumed that aA and aAaB, we know that aB. And then, in turn, our assumption that aBaC, we know that aC. Precisely what we need!
Oof! The above analysis becomes much easier with practice.
Assume that AB and BC. We wish to show that now AC, so let aA. Since we know that AB, we know that aB. And since we know that BC, we know that aC. Hence we have shown that AC.
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 A, 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 A be a set. The power set of A, denoted P(A), is the set of all subsets of A.
Note that the elements of P(A) are themselves sets, and
XP(A)XA.
When we get to the chapter on cardinality we’ll prove that if A is a finite set with |A|=n then |P(A)|=2n. We will also prove an important result about the power set of an infinite set.

Example 8.1.6.

What are P({1,2,3}),P() and P(P())?
P({1,2,3})={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}P()={}P(P())=P({})={,{}}
Since this is a biconditional we need to prove both directions. Lets start with the forward implication and then turn to the converse.
  • We want to show that ABP(A)P(B).
  • So we assume that AB and we want to prove that P(A)P(B).
  • This is equivalent to showing that XP(A)XP(B) — note that X is now itself a set (which is why 92  we’ve used a capital X rather than a lower case x ).
  • So just as was the case in the previous proof, we assume that the hypothesis, XP(A) is true. This means that XA.
  • But our previous 93  result — Result 8.1.4 — tells us that if XA and AB then XB.
  • This, in turn, implies that XP(B), and so P(A)P(B).
Okay, now lets look at the converse.
  • We want to show that P(A)P(B)AB.
  • So we assume that P(A)P(B).
  • But now AP(A), and so AP(B).
  • Hence A must be a subset of B — by definition of the power set.
As always, once the scratch work is done, its time to write up.
We prove each implication in turn.
  • Assume that AB, and let XP(A). Hence XA. By our result above, this, in turn, implies that XB. By the definition of the power set, this tells us that XP(B). Thus we have shown that P(A)P(B).
  • Now turn to the converse and assume that P(A)P(B). Since AP(A), this implies that AP(B). But, by the definition of the power set, this tells us that AB, 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 aA or aA. When aA we have precisely this case. On the other hand, if aA then the implication (aA)(aC) is true since the hypothesis is false. So it is only when aA 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.