3.3: Power Sets

We have already seen that using union, intersection, set difference, and complement we can create new sets (in the same universe) from existing sets. In this section, we will describe another way to generate new sets; however, the new sets will not “live" in the same universe this time. The following set is always a set of subsets. That is, its elements are themselves sets.

Definition 3.27. If \(S\) is a set, then the power set of \(S\) is the set of subsets of \(S\). The power set of \(S\) is denoted \(\tcboxmath{\mathcal{P}(S)}\).

You can see that a power set of \(S\) is not composed of elements of \(S\), but rather it is composed of subsets of \(S\), and none of these subsets are elements of \(S\).

For example, if \(S=\{a,b\}\), then \(\mathcal{P}(S)=\{\emptyset, \{a\}, \{b\}, S\}\). It follows immediately from the definition that \(A\subseteq S\) if and only if \(A\in\mathcal{P}(S)\).

Problem 3.28. For each of the following sets, find the power set.

1. \(A=\{\circ, \triangle, \square\}\)
2. \(B=\{a,\{a\}\}\)
3. \(C=\emptyset\)
4. \(D=\{\emptyset\}\)

Problem 3.29. How many subsets do you think that a set with \(n\) elements has? What if \(n=0\)? You do not need to prove your conjecture at this time. We will prove this later using mathematical induction.

It is important to realize that the concepts of element and subset need to be carefully delineated. For example, consider the set \(A=\{x,y\}\). The object \(x\) is an element of \(A\), but the object \(\{x\}\) is both a subset of \(A\) and an element of \(\mathcal{P}(A)\). This can get confusing rather quickly. Consider the set \(B\) from Problem 3.28. The set \(\{a\}\) happens to be an element of \(B\), a subset of \(B\), and an element of \(\mathcal{P}(B)\). The upshot is that it is important to pay close attention to whether “\(\subseteq\)" or “\(\in\)" is the proper symbol to use.

Since the next theorem is a biconditional proposition, you need to write two distinct subproofs, one for “\(S\subseteq T\) implies \(\mathcal{P}(S)\subseteq \mathcal{P}(T)\)", and another for “\(\mathcal{P}(S)\subseteq \mathcal{P}(T)\) implies \(S\subseteq T\)".

Theorem 3.30. Let \(S\) and \(T\) be sets. Then \(S\subseteq T\) if and only if \(\mathcal{P}(S)\subseteq \mathcal{P}(T)\).

Problem 3.31. Let \(S\) and \(T\) be sets. Determine whether each of the following statements is true or false. If the statement is true, prove it. If the statement is false, provide a counterexample.

1. \(\mathcal{P}(S\cap T) \subseteq \mathcal{P}(S)\cap\mathcal{P}(T)\)
2. \(\mathcal{P}(S)\cap\mathcal{P}(T)\subseteq \mathcal{P}(S\cap T)\)
3. \(\mathcal{P}(S\cup T)\subseteq \mathcal{P}(S)\cup\mathcal{P}(T)\)
4. \(\mathcal{P}(S)\cup\mathcal{P}(T)\subseteq \mathcal{P}(S\cup T)\)

While power sets provide a useful way of generating new sets, they also play a key role in Georg Cantor’s (1845–1918) investigation into the “size" of sets. Cantor’s Theorem (see Theorem 9.64) states that the power set of a set—even if the set is infinite—is always “larger" than the original set. One consequence of this is that there are different sizes of infinity and no largest infinity. Mathematics is awesome.