Definition 2.1.4.1.
Let \(A\) be a set. The power set of \(A\text{,}\) denoted \(\cP(A)\text{,}\) is the set of all subsets of \(A\text{.}\)
Subsection 2.1.4 Power sets
Example 2.1.4.2. Powerset of a set with cardinality three.
Suppose \(A = \set{2, x, \pi}\text{.}\) The power set of \(A\) is the set of all subsets of \(A\text{.}\) Let’s work out the subsets systematically, ordered by size.
- Size \(0\)
- Size \(1\)
- These singleton sets each contain one element of \(A\text{.}\) Since there are \(3\) elements in \(A\text{,}\) there are \(3\) subsets of size \(1\text{:}\) \(\set{2}\text{,}\) \(\set{x}\text{,}\) and \(\set{\pi}\text{.}\)
- Size \(2\)
- Subsets of \(A\) of size \(2\) can be constructed by omitting one element. Since there are \(3\) elements in \(A\text{,}\) there are \(3\) subsets of size \(2\text{:}\) \(\set{2, x}\text{,}\) \(\set{2, \pi}\text{,}\) and \(\set{x, \pi}\text{.}\)
- Size \(3\)
- There is only \(1\) subset of size \(3\text{.}\) It is the set \(A\) itself: \(\set{2, x, \pi}\text{.}\)
- Size \(> 3\)
- Since \(\size{A} = 3\text{,}\) there are no subsets of \(A\) that have size larger than \(3\text{.}\)
Thus the power set of \(A\) is
\begin{equation*}
\cP(A)= \set{\emptyset, \set{2}, \set{x}, \set{\pi}, \set{2, x},
\set{2, \pi}, \set{x, \pi}, \set{2, x, \pi}}.
\end{equation*}
Example 2.1.4.3. What adding one element does to the power set.
Because \(\set{1}\subseteq\set{1,2}\) the subsets of \(\set{1}\) are also subsets of \(\set{1,2}\text{.}\)
In addition \(\set{1,2}\) also has subsets that contain \(2\text{.}\) We obtain these by adding the element \(2\) to the subsets of \(\set{1}\) and obtain \(\color{blue}\set{2}\) and \(\color{blue}\set{1,2}\text{.}\) Together the subsets that do not contain \(2\) and the subsets that contain \(2\) are all the subsets of \(\set{1,2}\text{.}\) We get
\(\cP(\set{1,2})=\set{\emptyset,\set{1},{\color{blue}\set{2},\set{1,2}}} \) with \(\size\cP(\set{1,2})=4\text{.}\)
Because \(\set{1,2}\subseteq\set{1,2,3}\) the subsets of \(\set{1,2}\) are also subsets of \(\set{1,2,3}\text{.}\) In addition \(\set{1,2,3}\) also has subsets that contain \(3\text{.}\) We obtain these by adding the element \(3\) to \(\emptyset\) and \(\set{1}\) and \(\{1,2\}\text{.}\) We get
\(\cP(\set{1,2,3})=\set{\emptyset,\set{1},\set{2},\set{1,2},{\color{blue}\set{3},\set{1,3},\set{2,3},\set{1,2,3}}}\) with \(\size\cP(\set{1,2,3})=8.\)
In Example 2.1.4.3 we observe that adding an element to a set, doubles the number of sets in the powerset. Since \(\size{\cP(\emptyset)}=1\) this yields the following theorem.
Theorem 2.1.4.4.
If a set \(A\) has cardinality \(n\text{,}\) then the cardinality of the power set of \(A\) is \(\size{\cP(A)} = 2^n\text{.}\)
We revisit this result as Theorem 4.1.2.8 in Chapter 4 after we develop techniques on counting and give another proof.
