There are two notions of being “inside” a set. A thing may be an element of a set, or may be contained as a subset. Distinguishing these two notions of inclusion is essential. One difficulty that sometimes complicates things is that a set may contain other sets as elements. For instance, as we saw in the previous section, the elements of a power set are themselves sets.
A set \(A\) is a subset of another set \(B\) if all of \(A\)'s elements are also in \(B\). The terminology superset is used to refer to \(B\) in this situation, as in “The set of all real-valued functions in one real variable is a superset of the polynomial functions.” The subset/superset relationship is indicated with a symbol that should be thought of as a stylized version of the less-than-or-equal sign, when \(A\) is a subset of \(B\) we write \(A \subseteq B\).
We say that \(A\) is a proper subset of \(B\) if \(B\) has some elements that aren't in \(A\), and in this situation we write \(A \subset B\) or if we really want to emphasize the fact that the sets are not equal we can write \(A \subsetneq B\). By the way, if you want to emphasize the superset relationship, all of these symbols can be turned around. So for example \(A \supseteq B\) means that \(A\) is a superset of \(B\) although they could potentially be equal.
As we've seen earlier, the symbol \(\in\) is used between an element of a set and the set that it's in. The following exercise is intended to clarify the distinction between \(\in\) and \(\subseteq\).
Let \(A = \left\{ 1, 2, \{ 1 \}, \{ a, b \} \right\}\). Which of the following are true?
| i) \(\{ a, b \} \subseteq A\). | vi) \(\{ 1 \} \subseteq A\). |
| ii) \(\{ a, b \} \in A\). | vii) \(\{ 1 \} \in A\). |
| iii) \(a \in A\). | viii) \(\{ 2 \} \in A\). |
| iv) \(1 \in A\). | ix) \(\{ 2 \} \subseteq A\). |
| v) \(1 \subseteq A\). | x) \(\{\{1\}\} \subseteq A\). |
Another perspective that may help clear up the distinction between \(\in\) and \(\subseteq\) is to consider what they correspond to in Logic. The “element of” symbol \(\in\) is used to construct open sentences that embody the membership question — thus it corresponds to single sentences in Logic. The “set containment” symbol \(\subseteq\) goes between two sets and so whatever it corresponds to in Logic should be something that can appropriately be inserted between two sentences. Let's run through a short example to figure out what that might be. To keep things simple we'll work inside the universal set \(U=\{ 1, 2, 3, \ldots 50 \}\). Let \(T\) be the subset of \(U\) consisting of those numbers that are divisible by 10, and let \(F\) be those that are divisible by 5. \begin{equation*} T = \{10, 20, 30, 40, 50 \} \end{equation*} \begin{equation*} F = \{5, 10, 15, 20, 25, 30, 35, 40, 45, 50 \} \end{equation*}
Hopefully it is clear that \(\subseteq\) can be inserted between these two sets like so: \(T \subseteq F\). On the other hand we can re-express the sets \(T\) and \(F\) using set-builder notation in order to see clearly what their membership questions are. \begin{equation*} T = \{ x \in U \; \suchthat \; 10\divides x \} \end{equation*} \begin{equation*} F = \{ x \in U \; \suchthat \; 5\divides x \} \end{equation*}
What logical operator fits nicely between \(10\divides x\) and \(5\divides x\)? Well, of course, it's the implication arrow. It's easy to verify that \(10\divides x \, \implies \, 5\divides x\), and it's equally easy to note that the other direction doesn't work, \(5\divides x \, \nRightarrow \, 10\divides x\) — for instance, \(5\) goes evenly into \(15\), but \(10\) doesn't.
The general statement is: if \(A\) and \(B\) are sets, and \(M_A(x)\) and \(M_B(x)\) are their respective membership questions, then \(A \subseteq B\) corresponds precisely to \(\forall x \in U, M_A(x) \implies M_B(x)\).
Now to many people (me included!) this looks funny at first, \(\subseteq\) in Set theory corresponds to \(\implies\) in Logic. It seems like both of these symbols are arrows of a sort — but they point in opposite directions! Personally, I resolve the apparent discrepancy by thinking about the “strength” of logical predicates. One predicate is stronger than another if it puts more conditions on the elements that would make it true. For example, “\(x\) is doubly-even” is stronger than “\(x\) is (merely) even.” Now, the stronger statement implies the weaker (assuming of course that they are stronger and weaker versions of the same idea). If a number is doubly-even (i.e. divisible by 4) then it is certainly even — but the converse is certainly not true, \(6\) is even but not doubly-even. Think of all this in terms of sets now. Which set contains the other, the set of doubly-even numbers or the set of even numbers? Clearly the set that corresponds to more stringent membership criteria is smaller than the set that corresponds to less restrictive criteria, thus the set defined by a weak membership criterion contains the one having a stronger criterion.
If we are asked to prove that one set is contained in another as a subset, \(A \subseteq B\), there are two ways to proceed. We may either argue by thinking about elements, or (although this amounts to the same thing) we can show that \(A\)'s membership criterion implies \(B\)'s membership criterion.
Consider \(S\), the set of perfect squares and \(F\), the set of perfect fourth powers. Which is contained in the other? Can you prove it?
We'll end this section with a fairly elementary proof — mainly just to illustrate how one should proceed in proving that one set is contained in another.
Let \(D\) represent the set of all integers that are divisible by 9, \begin{equation*} D = \{ x \in \Integers \suchthat \exists k \in \Integers, \; x=9k \}. \end{equation*}
Let \(C\) represent the set of all integers that are divisible by 3, \begin{equation*} C = \{ x \in \Integers \suchthat \exists k \in \Integers, \; x=3k \}. \end{equation*}
The set \(D\) is contained in \(C\). Let's prove it!
Insert either \(\in\) or \(\subseteq\) in the blanks in the following sentences (in order to produce true sentences).
| i) \(1\) \(\{3, 2, 1, \{a, b\}\}\) | iii) \(\{a, b\}\) \(\{3, 2, 1, \{a, b\}\}\) | |
| ii) \(\{a\}\) \(\{a, \{a, b\}\}\) | iv) \(\{\{a, b\}\}\) \(\{a, \{a, b\}\}\) |
Suppose that \(p\) is a prime, for each \(n\) in \(\Integers^+\), define the set \(P_n = \{ x \in \Integers^+ \suchthat \, p^n \divides x \}\). Conjecture and prove a statement about the containments between these sets. \hint{When \(p=2\) we have seen these sets. \(P_1\) is the even numbers, \(P_2\) is the doubly-even numbers, etc.}
Provide a counterexample to dispel the notion that a subset must have fewer elements than its superset. \hint{A subset is called proper if it is neither empty nor equal to the superset. If we are talking about finite sets then the proper subsets do indeed have fewer elements than the supersets. Among infinite sets it is possible to have proper subsets having the same number of elements as their superset, for example there are just as many even natural numbers as there are natural numbers all told.}
We have seen that \(A \subseteq B\) corresponds to \(M_A \implies M_B\). What corresponds to the contrapositive statement? \hint{Turn “logical negation” into “set complement” and reverse the direction of the inclusion.}
Determine two sets \(A\) and \(B\) such that both of the sentences \(A \in B\) and \(A \subseteq B\) are true. \hint{The smallest example I can think of would be \(A=\emptyset\) and \(B=\{\emptyset\}\). You should come up with a different example.}
Prove that the set of perfect fourth powers is contained in the set of perfect squares. \hint{It would probably be helpful to have precise definitions of the sets described in the problem. The fourth powers are \begin{equation*} F = \{x \suchthat \exists y \in \Integers, x=y^4 \}. \end{equation*} The squares are \begin{equation*} S = \{x \suchthat \exists z \in \Integers, x=z^2 \}. \end{equation*} To show that one set is contained in another, we need to show that the first set's membership criterion implies that of the second set.}