The Power Set of a Set

Definition: Let $A$ be a set. Then the Power Set of $A$ denoted $\mathcal P (A)$ is defined to be the set of all subsets of $A$ including the empty set $\emptyset$ and the whole set $A$.

The notations $\wp (A)$, $P(A)$, $\mathbb{P}(A)$, and $2^A$ are sometimes used to refer to the power set of $A$.

For example, consider the set $A = \{x, y, z \}$. Then the power set of $A$ is given by:

(1)

\begin{align} \quad \mathcal P(A) = \{ \emptyset, \{x \}, \{y \}, \{ z \}, \{x, y \}, \{x, z \}, \{y, z \}, \{x, y, z \} \} \end{align}

Notice that $\lvert A \rvert = 3$ and $\lvert \mathcal P(A) \rvert = 8 = 2^3$. For a finite set $A$, this is always true and we prove this in the following theorem.

Theorem 1: Let $A$ be a finite set such that $\lvert A \rvert = n$. Then the size of the power set $\mathcal P(A)$ is given by the formula $\lvert \mathcal P(A) \rvert = 2^{\lvert A \rvert} = 2^n$.

• Proof: Let $A$ be a finite set such that $\lvert A \rvert = n$. Then the set $A$ assumes the form:

(2)

\begin{align} \quad A = \{x_1, x_2, ..., x_n \} \end{align}

• For each subset $B$ of $A$ assign a finite sequence of $n$-terms: $(a_1, a_2, ..., a_n)$ where for each $j \in \{1, 2, ..., n \}$ we have that $a_j = 0$ if $x_j \in B$ and $a_j = 1$ if $x_j \not \in B$. For example, the sequence $(0, 0, ..., 0)$ implies that $x_1, x_2, ..., x_n \not \in B$ so $B = \emptyset$. All subsets of $B$ are of this form, so we need to count the number of sequences $(a_1, a_2, ..., a_n)$ that exist. For each of the $n$ terms in the sequence we have $2$ choices (either we choose $0$ or we choose $1$). Therefore the number of these sequences is:

(3)

\begin{align} \quad \mathrm{number \: of \:sequences} = \underbrace{2 \cdot 2 \cdot ... \cdot 2}_{n \: \mathrm{many}} = 2^n \end{align}

• Therefore we conclude that:

(4)

\begin{align} \quad \lvert \mathcal P(A) \rvert = 2^{\lvert A \rvert} = 2^n \quad \blacksquare \end{align}

We will see later on that the method of showing that there are $2^n$ subsets of a finite $n$-element set $A$ will be useful later on when discuss an algorithm for listing all $2^n$ subsets of such a set.

We will now move onto a rather simply corollary which says that the number of elements in a set is always less than the number of elements in its power set.

Corollary 1: If $A$ is a finite set then $\lvert A \rvert < \lvert \mathcal P(A) \rvert$.

• Proof: Let $A$ be a set. Then $1 \leq \lvert A \rvert = n$, i.e., $n \geq 1$. We will show that $n < 2^n$ for all $n \in \{1, 2, ... \}$ by induction.

• Let $S(k)$ be the statement that $k < 2^k$. For the base steps we have that $S(0)$ says that $0 < 2^0 = 1$, which is true, so $S(0)$ is true. Also, $S(1)$ says that $1 < 2^1 = 2$, which is true, and so $S(1)$ is true. For $k > 1$ assume that $S(1)$ is true, that is assume that $k < 2^k$. We want to therefore show that $S(k+1)$ is true, that is show that $k+1 < 2^{k+1}$. We have that that since $k > 1$:

(5)

\begin{align} \quad 2^{k+1} = 2 \cdot 2^k \overset{IH} > 2k = k + k > k + 1 \end{align}

• Therefore $S(k+1)$ is true. By the principle of mathematical induction we have that $n < 2^n$ for all $n \in \{0, 1, 2, ... \}$. Therefore we conclude that:

(6)

\begin{align} \quad \lvert A \rvert = n < 2^n = \lvert \mathcal P(A) \rvert \quad \blacksquare \end{align}