Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

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

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\text{.}\) We denote this \(A \subseteq B\text{.}\)
  • If \(A\) is not a subset of \(B\text{,}\) then we denote this as \(A \not\subseteq B\text{.}\)
  • 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\text{.}\) We denote this by \(A \subset B\text{.}\)
  • If \(A \subseteq B\) then \(B\) is a superset of \(A\) which we can write as \(B \supseteq A\text{.}\) Similarly, if \(A \subset B\) then \(B\) is a proper superset of \(A\) which write as \(B \supset A\)
Finally,
  • Two sets \(A\) and \(B\) are equal if \(A\) is a subset of \(B\) and \(B\) is a subset of \(A\text{.}\) That is
    \begin{align*} (A = B) & \equiv ((A \subseteq B) \land (B\subseteq A)) \end{align*}
Some things to note
  • The empty set is a subset of every set. That is, for any set \(A\text{,}\) we always have that \(\es \subseteq A\text{.}\)
  • That \(A \subseteq B\) is equivalent to saying that if we take any element of \(A\) then it is also an element of \(B\text{.}\) That is
    \begin{gather*} (A \subseteq B) \equiv (\forall a \in A, a \in B) \equiv (a \in A \implies a \in B). \end{gather*}
  • If \(A \not\subseteq B\text{,}\) then there is at least one element of \(A\) that is not in \(B\text{.}\) That is
    \begin{align*} \left(A \not\subseteq B\right) & \equiv \left( \exists a \in A \st a \not\in B \right) \end{align*}
  • 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 \(A\subseteq B\) and then the second part showing that \(B\subseteq A\text{.}\)

Example 8.1.2.

Let \(S = \{1,2\}\text{.}\) What are all the subsets of \(S\text{?}\)
  • The subsets are \(\es, \{1\}, \{2\}, \{1,2\}\text{.}\)
First lets write a few elements of these sets
\begin{align*} A &= \set{\dots, -18,-12,-6,0,6,12,18,\dots} & B &=\set{\dots,-6,-4,-2,0,2,4,6,\dots} \end{align*}
The result we are trying to prove is that \(A \subseteq B\text{.}\) This is equivalent to showing that if \(a \in A\) then \(a \in B\) (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 \(a\in A\) and then work our way to proving that \(a \in B\text{.}\)
  • 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 \(a\in A\text{.}\)
  • Then this means that \(a\) is an integer that is divisible by 6. That is \(a=6\ell\) for some \(\ell \in \mathbb{Z}\text{.}\)
  • We need to show that \(a \in B\text{.}\) This is equivalent to showing that we can write \(a=2k\) where \(k\) is some integer.
  • But we know that \(a=6\ell = 2(3\ell)\) and since \(3\ell \in \mathbb{Z}\) 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 \(a\in A\text{.}\) Hence we can write \(a=6\ell\) where \(\ell \in \mathbb{Z}\text{.}\) But now since \(6\ell = 2(3\ell)\) and \(3\ell\) is an integer, we know that \(a \in B\text{.}\) Thus \(A\subseteq B\text{.}\)
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 \(A\subseteq B\) and \(B\subseteq C\text{.}\) We can, in turn, write this as
    \begin{gather*} (a \in A \implies a \in B) \land (b \in B \implies b \in C) \end{gather*}
  • The conclusion says \(A \subseteq C\text{.}\) This can similarly be written as
    \begin{gather*} a\in A \implies a\in C. \end{gather*}
  • Since we are trying to prove an implication, we start by assuming the hypothesis is true. So we assume that
    \begin{gather*} (a \in A \implies a \in B) \land (b \in B \implies b \in C) \end{gather*}
    Notice this we do not assume that \(a\in A\) and \(b\in B\text{,}\) rather we are assuming that the above implications are both true 89 .
  • Now we want to prove that the conclusion is true, namely that
    \begin{gather*} a\in A \implies a \in C. \end{gather*}
    This we can do by assuming that the hypothesis is true and showing the conclusion. 90  That is, assume that \(a \in A\) and then work towards showing that \(a \in C\text{.}\)
  • Since now we have assumed that \(a \in A\) and \(a \in A \implies a \in B\text{,}\) we know that \(a \in B\text{.}\) And then, in turn, our assumption that \(a \in B \implies a \in C\text{,}\) we know that \(a \in C\text{.}\) Precisely what we need!
Oof! The above analysis becomes much easier with practice.
Assume that \(A\subseteq B\) and \(B \subseteq C\text{.}\) We wish to show that now \(A \subseteq C\text{,}\) so let \(a \in A\text{.}\) Since we know that \(A \subseteq B\text{,}\) we know that \(a \in B\text{.}\) And since we know that \(B \subseteq C\text{,}\) we know that \(a\in C\text{.}\) Hence we have shown that \(A \subseteq C\text{.}\)
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\text{,}\) 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\text{,}\) denoted \(\mathcal{P}(A)\text{,}\) is the set of all subsets of \(A\text{.}\)
Note that the elements of \(\pow{A}\) are themselves sets, and
\begin{gather*} X \in \pow{A} \iff X \subseteq A. \end{gather*}
When we get to the chapter on cardinality we’ll prove that if \(A\) is a finite set with \(|A| = n\) then \(|\mathcal{P}(A)| = 2^n\text{.}\) We will also prove an important result about the power set of an infinite set.

Example 8.1.6.

What are \(\pow{\set{1,2,3}}, \pow{\es}\) and \(\pow{\pow{\es}}\text{?}\)
\begin{align*} \pow{\set{1,2,3}} &= \set{\es, \set{1},\set{2},\set{3},\set{1,2},\set{1,3},\set{2,3},\set{1,2,3}}\\ \pow{\es} &= \{ \es \}\\ \pow{\pow{\es}} &= \pow{\{ \es \}} = \{ \es, \{ \es \} \} \end{align*}
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 \(A\subseteq B \implies \pow{A} \subseteq \pow{B}\text{.}\)
  • So we assume that \(A\subseteq B\) and we want to prove that \(\pow{A} \subseteq \pow{B}\text{.}\)
  • This is equivalent to showing that \(X \in \pow{A} \implies X \in \pow{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, \(X\in\pow{A}\) is true. This means that \(X \subseteq A\text{.}\)
  • But our previous 93  result — Result 8.1.4 — tells us that if \(X \subseteq A\) and \(A\subseteq B\) then \(X \subseteq B\text{.}\)
  • This, in turn, implies that \(X \in \pow{B}\text{,}\) and so \(\pow{A} \subseteq \pow{B}\text{.}\)
Okay, now lets look at the converse.
  • We want to show that \(\pow{A} \subseteq \pow{B} \implies A\subseteq B\text{.}\)
  • So we assume that \(\pow{A} \subseteq \pow{B}\text{.}\)
  • But now \(A \in \pow{A}\text{,}\) and so \(A \in \pow{B}\text{.}\)
  • 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 \(A \subseteq B\text{,}\) and let \(X\in \pow{A}\text{.}\) Hence \(X \subseteq A\text{.}\) By our result above, this, in turn, implies that \(X \subseteq B\text{.}\) By the definition of the power set, this tells us that \(X \in \pow{B}\text{.}\) Thus we have shown that \(\pow{A}\subseteq\pow{B}\text{.}\)
  • Now turn to the converse and assume that \(\pow{A}\subseteq\pow{B}\text{.}\) Since \(A\in\pow{A}\text{,}\) this implies that \(A\in\pow{B}\text{.}\) But, by the definition of the power set, this tells us that \(A \subseteq B\text{,}\) 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 \(a \in A\) or \(a \not\in A\text{.}\) When \(a \in A\) we have precisely this case. On the other hand, if \(a \not\in A\) then the implication \((a\in A) \implies (a \in C)\) is true since the hypothesis is false. So it is only when \(a \in A\) 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.
<Prev^TopNext>