Power Set of a Set

Definition: If $A$ is a set, then denote the power set of $A$ as $P(A) = \{ B : B \subseteq A \}$, that is, $P(A)$ is the set of subsets of $A$.

For example, consider the set $A = \{ x, y, z \}$. The table below lists all $B \subseteq A$:

#	Subset of $A$
1	$\emptyset = \{ \}$
2	$\{ x \}$
3	$\{ y \}$
4	$\{ z \}$
5	$\{ x, y \}$
6	$\{ x, z \}$
7	$\{ y, z \}$
8	$\{x, y, z \}$

Therefore $P(A) = \{ \emptyset, \{ x \}, \{ y \}, \{ z \}, \{ x, y \}, \{ x, z \}, \{ y, z \}, \{x, y, z \} \}$

Theorem 1: If $A$ is a finite set with $n$ elements then $A$ has $2^n$ distinct subsets, that is $P(A)$ has $2^n$ elements.

• Proof: We will carry out this proof by mathematical induction. For $n \in \mathbb{N}$ let $S(n)$ be the statement that if $A$ has $n$ elements then $P(A)$ has $2^n$ elements.

• $S(1)$ says that for some arbitrary set $A$ containing $1$ element then $P(A)$ has $2$ elements. The only two subsets of $A$ are $\emptyset$ and $A$, so $S(1)$ is true.

• Suppose now that for some $k \in \mathbb{N}$, $k ≥ 1$ that $S(k)$ is true, that is for some arbitrary set $B$ containing $k$ elements then $P(B)$ has $2^k$ elements. We want to then show that $S(k+1)$ is true, that is for some arbitrary set $C$ containing $k + 1$ elements then $P(C)$ contains $2^{k+1}$ elements.

• Suppose that $C$ contains $k + 1$ elements. Let $c \in C$ be any element from $C$, and look at the set $C \setminus \{ c \}$ which contains $k$ elements. By the induction hypothesis since $C \setminus \{ c \}$ contains $k$ elements then $P(C \setminus \{ c \})$ contains $2^k$ elements. If we now add the element $c$ back into this set, i.e, look at the set $C$ itself, notice that we will have twice as many subsets. We will have $2^k$ subsets which do not contain $c$, and we will have $2^k$ subsets that do contain $c$. Therefore $P(C)$ contains $2^k + 2^k = 2(2^k) = 2^{k+1}$ elements, and so $S(k+1)$ is true.

• Therefore by Principle of Mathematical Induction, since the truth of $S(k)$ implies the truth of $S(k+1)$ then $S(n)$ is true for all $n \in \mathbb{N}$.