Section 1.2 Containment
One of the most important ideas when dealing with sets is that of a subset.
Definition 1.2.1.
Let \(A\) and \(B\) be sets. We say \(A\) is a subset of \(B\) if every element of \(A\) is also an element of \(B\text{.}\)
If \(A\) is a subset of \(B\text{,}\) we write \(A \subseteq B\) and write \(A \not\subseteq B\) otherwise.
Example 1.2.2.
Example 1.2.3.
Put \(X = \{a,b,c\}\text{,}\) \(Y = \{a,c\}\text{,}\) and \(Z=\{b\}\text{.}\) Then \(Y \subseteq X\text{,}\) \(Z \subseteq X\text{,}\) but \(Y \not\subseteq Z\) and \(Z \not\subseteq Y\text{.}\)
There is a prickly little set that arises very quickly when discussing subsets, which leads to all sorts of interesting examples.
Definition 1.2.4.
The empty set, denoted \(\varnothing\) or \(\{\}\text{,}\) is the set with no elements.
In the preceding section we discussed definitions, examples, theorems, and proofs. You saw the first two in that section; now, we will see our first theorem and its proof.
Theorem 1.2.5.
The empty set is a subset of every set.
A proof is simply an argument that convinces its reader of the truth of a mathematical fact. Valid proofs must only use definitions and the hypotheses of the theorem; it is not correct to assume more than you are given. So the ingredients in the proof of this theorem are simply going to the empty set, the second set (which must be arbitrary) and the definition of a subset.
Let's give a name to the second set, say, \(A\text{.}\) We may not assume anything else about it—not even finiteness or whether \(A\) itself is empty!
To prove that \(\varnothing \subseteq A\text{,}\) we will rely on the definition of a subset, which you just wrote down (right?): \(\varnothing \subseteq A\) if every element of \(\varnothing\) is an element of \(A\text{.}\) In a later section we will clarify this next step somewhat, but it turns out that saying “Everything in \(\varnothing\) is in \(A\)” is the same as saying “There is nothing in \(\varnothing\) that is not in \(A\text{.}\)” This is true, because there is nothing in \(\varnothing\text{!}\) To get an idea of why this weird conversion works, look back to the previous example. The reason \(\{a,c\} \not\subseteq \{b\}\) is because we can find an element (\(a\text{,}\) for instance) that is not in \(\{b\}\text{.}\) Had the set been empty, we could not have found that element.
Now that we have thought through our proof, we can write it down. We want to include enough details that the intended audience can understand it, but trim unnecessary verbage. The proof is below. Readers of the web version will have to un-“knowl” it like they do the examples.
Proof.
Let \(A\) be any set. To prove that \(\varnothing \subseteq A\text{,}\) we must prove that every element of \(\varnothing\) is an element of \(A\text{.}\) Equivalently, there must be no element in \(\varnothing\) that is not in \(A\text{.}\) Because there are no elements in \(\varnothing\) anyway, we may conclude \(\varnothing \subseteq A\text{.}\) Therefore, the empty set is a subset of every set.
Notice that the proof began with the assumptions (\(A\) is a set) and ended on a restatement of the desired theorem.
Here is another theorem. As an exercise, see if you can come up with the proof before you read it. You may not get it right, but it's important to at least try to think about why a theorem is true before reading the proof.
Theorem 1.2.6.
Every set is a subset of itself. That is, for all sets \(A\text{,}\) \(A \subseteq A\text{.}\)
Proof.
Let \(A\) be any set. If \(A\) is empty, then the proof is complete, because the empty set is a subset of every set.
Otherwise, let \(A\) be nonempty. Consider an arbitrary element \(a \in A\text{.}\) This element is also in \(A\text{.}\) Since \(a\) was chosen arbitrarily, any element of \(A\) must also be in \(A\text{.}\) Therefore, by definition, \(A \subseteq A\text{.}\)
Notice that this proof contains two cases: the case that \(A\) is empty and the case that \(A\) is nonempty. A proof must address every possible situation, or else the theorem should be restricted to only the appropriate cases.
Definition 1.2.7.
Let \(A\) be any set. Its power set is the set \(\mathscr{P}(A)\) whose elements are the subsets of \(A\text{.}\) That is,
Wait—our elements are sets? Yes, and this is perfectly fine! As we've said, elements can be anything: other sets included. When we have a "set of sets" we typically refer to it as a family or a collection of sets to avoid using the same word and over and over.
The symbol \(\mathscr{P}\) is a curly “P”. It's fun to practice writing, but don't worry if you don't get it perfect; any curly capital “P” will do. (Same goes for the curly braces \(\{\) and \(\}\text{.}\) Lots of students have trouble writing them at first!)
In the following example we will calculate the power set of \(\{a,b,c\}\text{.}\) Before you read the example, try to write it down for yourself. What are all the possible groups of elements from that set? Remember there are two special ones that students commonly forget at first (hint: reread the preceding theorems).
Example 1.2.8.
Let \(A = \{a,b,c\}\text{.}\) Then
It is also correct to say
(it's just a matter of notation).
Be careful that you do not use a capital letter to refer to a set that has not been given a name. Above, we declared that \(A=\{a,b,c\}\text{.}\) Had we not done so, it would have been incorrect to use \(A\) to stand in for \(\{a,b,c\}\text{.}\)
Example 1.2.9.
The power set of \(\varnothing\) is \(\mathscr{P}(\varnothing) = \{\varnothing\}\text{.}\) The power set of the power set of \(\varnothing\) is
As an exercise (in writing curly braces), see if you can calculate \(\mathscr{P}\big(\mathscr{P}(\varnothing)\big)\text{.}\)
Finally, we are often interested in knowing whether two sets are equal. This is often how we prove that being one type of object is the same as being another type of object. What does it mean for two sets to be equal? Then, we will prove a useful theorem that shows two sets are equal if they contain each other.
Definition 1.2.10.
Two sets \(A\) and \(B\) are equal if they contain exactly the same elements. In this case, we write \(A=B\text{.}\)
Example 1.2.11.
The sets \(\{a,b,c\}\) and \(\{a,b\}\) are unequal. If we know that \(a=1\text{,}\) \(b=2\text{,}\) and \(c=3\text{,}\) then \(\{a,b,c\}\) and \(\{1,2,3\}\) are equal. They are also equal if \(a=3\text{,}\) \(b=1\text{,}\) and \(c=2\) (etc.) Unless we know something like that, we otherwise consider \(\{a,b,c\}\) and \(\{1,2,3\}\) to be unequal.
The following principle of mutual inclusion is often very useful in proving two sets are equal.
Theorem 1.2.12.
Let \(A\) and \(B\) be sets. Then, \(A=B\) if and only if \(A \subseteq B\) and \(B \subseteq A\text{.}\)
This theorem contains the phrase “if and only if,” which we will learn about in detail shortly. Here, it means that if \(A=B\text{,}\) then \(A\) and \(B\) contain one another as subsets; and vice-versa, that if \(A\) and \(B\) contain each other, then \(A=B\text{.}\) This conditional statement works both ways. Generally, conditional statements do not work both ways (this will be important later!)
So, we will prove this statement in two parts. First, we will prove that if \(A=B\text{,}\) then \(A \subseteq B\) and \(B \subseteq A\text{.}\) Next, we will prove that if \(A \subseteq B\) and \(B \subseteq A\text{,}\) then \(A=B\text{.}\) Truly adventurous readers may try to sketch the proof themselves, or think about how it may go, before reading the proof that follows.
Proof.
Let \(A\) and \(B\) be sets. First, suppose that \(A=B\text{.}\) This means that \(A\) and \(B\) contain exactly the same elements. Therefore, \(A \subseteq B\) because every element of \(A\) is also an element of \(B\text{.}\) Likewise, \(B \subseteq A\text{.}\)
Conversely, suppose that \(A \subseteq B\) and \(B \subseteq A\text{.}\) If \(A \subseteq B\text{,}\) then that means there are no elements of \(A\) that are not in \(B\text{.}\) If \(B \subseteq A\text{,}\) that means there are no elements of \(B\) that are not also elements of \(A\text{.}\) This means that \(A\) and \(B\) must contain exactly the same elements, so, \(A=B\text{.}\)
Thus, \(A=B\) if and only if \(A \subseteq B\) and \(B \subseteq A\text{.}\)
The word conversely means “We are turning the conditional statement around.” It is a very handy word for writing proofs with two directions.