4.2 Containment

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\).

Exercise 4.4 Let \(A = \left\{ 1, 2, \{ 1 \}, \{ a, b \} \right\}\). Which of the following are true?

1. \(\{ a, b \} \subseteq A\).
2. \(\{ a, b \} \in A\).
3. \(a \in A\).
4. \(1 \in A\).
5. \(1 \subseteq A\).
6. \(\{ 1 \} \subseteq A\)
7. \(\{ 1 \} \in A\).
8. \(\{ 2 \} \in A\).
9. \(\{ 2 \} \subseteq A\).
10. \(\{\{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.

\[ T = \{10, 20, 30, 40, 50 \} \] \[ F = \{5, 10, 15, 20, 25, 30, 35, 40, 45, 50 \} \]

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.

\[ T = \{ x \in U \; {\,:\,}\; 10 \mid x \} \] \[ F = \{ x \in U \; {\,:\,}\; 5 \mid x \} \]

What logical operator fits nicely between \(10 \mid x\) and \(5 \mid x\)? Well, of course, it’s the implication arrow. It’s easy to verify that \(10 \mid x \, \implies \, 5 \mid x\), and it’s equally easy to note that the other direction doesn’t work, \(5 \mid x \, \nRightarrow \, 10 \mid 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.

Exercise 4.5 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,

\[ D = \{ x \in {\mathbb Z}{\,:\,}\exists k \in {\mathbb Z}, \; x=9k \}. \]

Let \(C\) represent the set of all integers that are divisible by 3,

\[ C = \{ x \in {\mathbb Z}{\,:\,}\exists k \in {\mathbb Z}, \; x=3k \}. \]

The set \(D\) is contained in \(C\). Let’s prove it!

Proof. Suppose that \(x\) is an arbitrary element of \(D\). From the definition of \(D\) it follows that there is an integer \(k\) such that \(x=9k\). We want to show that \(x \in C\), but since \(x=9k\) it is easy to see that \(x = 3(3k)\) which shows (since \(3k\) is clearly an integer) that \(x\) is in \(C\).

4.2.1 Exercises

1. Insert either \(\in\) or \(\subseteq\) in the blanks in the following sentences (in order to produce true sentences).
   1. \(1 \;\underline{~~~~~}\;\{3, 2, 1, \{a, b\}\}\)
   2. \(\{a\} \;\underline{~~~~~}\; \{a, \{a, b\}\}\)
   3. \(\{a, b\} \;\underline{~~~~~}\; \{3, 2, 1, \{a, b\}\}\)
   4. \(\{\{a, b\}\} \;\underline{~~~~~}\; \{a, \{a, b\}\}\)

2. Suppose that \(p\) is a prime, for each \(n\) in \({\mathbb Z}_{> 0}\), define the set \(P_n = \{ x \in {\mathbb Z}_{> 0}{\,:\,}\, p^n \mid x \}\).
   Conjecture and prove a statement about the containments between these sets.

3. Provide a counterexample to dispel the notion that a subset must have fewer elements than its superset.

4. We have seen that \(A \subseteq B\) corresponds to \(M_A \implies M_B\). What corresponds to the contrapositive statement?

5. Determine two sets \(A\) and \(B\) such that both of the sentences \(A \in B\) and \(A \subseteq B\) are true.

6. Prove that the set of perfect fourth powers is contained in the set of perfect squares.