# Cardinality of Power Set of Finite Set/Proof 3

## Contents

## Theorem

Let $S$ be a set such that:

- $\card S = n$

where $\card S$ denotes the cardinality of $S$,

Then:

- $\card {\powerset S} = 2^n$

where $\powerset S$ denotes the power set of $S$.

## Proof

Proof by induction:

For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

- $\left|{S}\right| = n \implies \left|{\mathcal P \left({S}\right)}\right| = 2^n$

Do not confuse $P \left({n}\right)$, which is a propositional function on $\N$, with $\mathcal P \left({S}\right)$, the power set of $S$.

### Basis for the Induction

From Cardinality of Empty Set, we have:

- $S = \varnothing \iff \left|{S}\right| = 0$

Then:

- $\mathcal P \left({\varnothing}\right) = \left\{{\varnothing}\right\}$

has one element, that is, $\varnothing$.

So:

- $\left|{\mathcal P \left({\varnothing}\right)}\right| = \left|{\left\{{\varnothing}\right\}}\right| = 1 = 2^0$

thus confirming that $P \left({0}\right)$ holds.

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

- $\left|{S}\right| = k \implies \left|{\mathcal P \left({S}\right)}\right| = 2^k$

Then we need to show:

- $\left|{S}\right| = k + 1 \implies \left|{\mathcal P \left({S}\right)}\right| = 2^{k + 1}$

### Induction Step

This is our induction step:

Let $\left|{S}\right| = k + 1$.

Let $x \in S$.

Consider the set $S' = S \setminus \left\{{x}\right\}$ where $x$ is any element of $S$.

We see that $\left|{S'}\right| = k$.

Now adjoin $x$ to all the subsets of $S'$.

Counting the subsets of $S$, we have:

- all the subsets of $S'$

and:

- all the subsets of $S'$ with $x$ adjoined to them.

From the induction hypothesis, there are $2^k$ subsets of $S'$.

Adding $x$ to each of these does not change their number, so there are another $2^k$ subsets of $S$ consisting of all the subsets of $S'$ with $x$ adjoined to them.

In total that makes $2^k + 2^k = 2 \times 2^k = 2^{k + 1}$ subsets of $S$.

So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore:

- $\forall n \in \N: \left|{S}\right| = n \implies \left|{\mathcal P \left({S}\right)}\right| = 2^n$

$\blacksquare$

## Sources

- 1966: Richard A. Dean:
*Elements of Abstract Algebra*... (previous) ... (next): $\S 0.6$: Theorem $8: \ 1$