Power Set of a Set
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}$.