The Powerset

  • sets (notation, operations, cardinality)

Sometimes it is useful to take a set and consider all sets one could build from its elements. For example, each one of the following sets can be built from the elements of \(\left \{ 1,2,3 \right \}\):

  1. \(\emptyset\)
  2. \(\left \{ 1 \right \}\)
  3. \(\left \{ 2 \right \}\)
  4. \(\left \{ 3 \right \}\)
  5. \(\left \{ 1,2 \right \}\)
  6. \(\left \{ 1,3 \right \}\)
  7. \(\left \{ 2,3 \right \}\)
  8. \(\left \{ 1,2,3 \right \}\)

Note that each one of the sets in this list is a subset of \(\left \{ 1,2,3 \right \}\), and every subset of \(\left \{ 1,2,3 \right \}\) is on this list. So the above is the list of all subsets of \(\left \{ 1,2,3 \right \}\). The set of all these sets is called the powerset of \(\left \{ 1,2,3 \right \}\).

For \(A\) a set, the powerset of \(A\) is \(\wp(A) \mathrel{\mathop:}=\left \{ S \mid S \subseteq A \right \}\).

Suppose we have the set \(\left \{ a \right \}\) and want to compute \(\wp(\left \{ a \right \})\). This can be done in many ways, but here is one that’s easy for beginners.

  1. First, we write down the set itself: \(\left \{ a \right \}\)
  2. Next, we write down all proper subsets of the set. In this case, there’s only one: \(\emptyset\)
  3. Finally, we put set brackets around the list of sets we wrote down: \(\wp(\left \{ a \right \}, \emptyset)\).

And that’s it. As long as the set in question isn’t too large, you can always follow this mechanical procedure when you aren’t sure how to compute the set’s powerset.

For each one of the following sets, compute its powerset.

  1. \(\left \{ a,b \right \}\)
  2. \(\left \{ a,b,c,d \right \}\)
  3. \(\left \{ \left \{ a \right \} \right \}\)
  4. \(\emptyset\)
  5. \(\left \{ \emptyset \right \}\)
  6. \(\wp(\left \{ \left \{ a \right \} \right \})\)
  7. \(\wp(\wp(\emptyset))\)

Powerset notation

There are many alternative notations for the powerset. A particularly common one is \(2^A\) as it highlights two interesting aspects of the powerset. Remember that the cardinality of a set \(A\) measures the number elements it contains, and we denote it by \(\left | A \right |\). For example, \(\left | \left \{ 1,2,3 \right \} \right | = 3\). Now we can state a universal truth for the cardinality of powersets.

For every set \(A\) with \(\left | A \right | = n\), it holds that \(\left | \wp(A) \right | = \left | 2^A \right | = 2^{\left | A \right |} = 2^n\).

This is witnessed by our example set \(\left \{ 1,2,3 \right \}\), the powerset of which has \(8\) members (see the list at the beginning of this unit).

For each set \(A\) in the previous exercise, verify that \(\left | \wp(A) \right | = 2^{\left | A \right |}\).

Recap