2.11: Power sets

Last updated
Save as PDF

Page ID: 95473

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Power set is a curious name for a simple concept. We talk about the power set “of" another set, which is the set of all subsets of that other set. Example: suppose \(A\) = { Dad, Lizzy }. Then the power set of \(A\), which is written as “\(\mathbb{P}(A)\)" is: { { Dad, Lizzy }, { Dad }, { Lizzy }, \(\varnothing\) }. Take a good look at all those curly braces, and don’t lose any. There are four elements to the power set of \(A\), each of which is one of the possible subsets. It might seem strange to talk about “all of the possible subsets" — when I first learned this stuff, I remember thinking at first that there would be no limit to the number of subsets you could make from a set. But of course there is. To create a subset, you can either include, or exclude, each one of the original set’s members. In \(A\)’s case, you can either (1) include both Dad and Lizzy, or (2) include Dad but not Lizzy, or (3) include Lizzy but not Dad, or (4) exclude both, in which case your subset is \(\varnothing\). Therefore, \(\mathbb{P}(A)\) includes all four of those subsets.

Now what’s the cardinality of \(\mathbb{P}(X)\) for some set \(X\)? That’s an interesting question, and one well worth pondering. The answer ripples through the heart of a lot of combinatorics and the binary number system, topics we’ll cover later. And the answer is right at our fingertips, if we just extrapolate from the previous example. To form a subset of \(X\), we have a choice to either include, or else exclude, each of its elements. So there’s two choices for the first element¹, and then whether we choose to include or exclude that first element, there are two choices for the second. Regardless of what we choose for those first two, there are two choices for the third, etc. So if \(|X|=2\) (recall that this notation means “\(X\) has two elements" or “\(X\) has a cardinality of 2"), then its power set has \(2 \times 2\) members. If \(|X|=3\), then its power set has \(2 \times 2 \times 2\) members. In general:

\[|\mathbb{P}(X)| = 2^{|X|}.\]

As a limiting case (and a brain-bender) notice that if \(X\) is the empty set, then \(\mathbb{P}(X)\) has one (not zero) members, because there is in fact one subset of the empty set: namely, the empty set itself. So \(|X|=0\), and \(|\mathbb{P}(X)|=1\). And that jives with the above formula.

I know there’s really no “first” element, but work with me here.