Cardinality of Power Set of Finite Set

From ProofWiki
Jump to navigation Jump to search

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$.


Thus it can be seen that the power set's alternative notation $2^S$ is indeed appropriate.

However, because of possible confusion over the conventional meaning of $2^n$, its use is deprecated.


Proof 1

Let $T = \set {0, 1}$.

For each $A \in \powerset S$, we consider the characteristic function $\chi_A: S \to T$ defined as:

$\forall x \in S: \map {\chi_A} x = \begin{cases} 1 & : x \in A \\ 0 & : x \notin A \end{cases}$


Now consider the mapping $f: \powerset S \to T^S$:

$\forall A \in \powerset S: \map f A = \chi_A$

where $T^S$ is the set of all mappings from $S$ to $T$.


Also, consider the mapping $g: T^S \to \powerset S$:

$\forall \phi \in T^S: \map g \phi = \phi^{-1} \sqbrk {\set 1}$

where $\phi^{-1} \sqbrk {\set 1}$ is the preimage of $\set 1$ under $\phi$.


Consider the characteristic function of $\phi^{-1} \sqbrk {\set 1}$, denoted $\chi_{\phi^{-1} \sqbrk {\set 1} }$.


We have:

\(\displaystyle \forall x \in S: \map {\chi_{\phi^{-1} \sqbrk {\set 1} } } x\) \(=\) \(\displaystyle \begin{cases} 1 & : x \in \phi^{-1} \sqbrk {\set 1} \\ 0 & : x \notin \phi^{-1} \sqbrk {\set 1} \end{cases}\)
\(\displaystyle \) \(=\) \(\displaystyle \begin{cases} 1 & : \map \phi x = 1 \\ 0 & : \map \phi x = 0 \end{cases}\)
\(\displaystyle \) \(=\) \(\displaystyle \map \phi x\)


So:

\(\displaystyle \forall \phi \in T^S: \map {\paren {f \circ g} } \phi\) \(=\) \(\displaystyle \map f {\phi^{-1} } {\sqbrk {\set 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \chi_{\phi^{-1} \sqbrk {\set 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \phi\)

So $f \circ g = I_{T^S}$, that is, the identity mapping on $T^S$.


So far so good. Now we consider the preimage of $\set 1$ under $\chi_A$:

$\chi_A^{-1} \sqbrk {\set 1} = A$

from the definition of the characteristic function $\chi_A$ above.

Thus:

\(\displaystyle \forall A \in \powerset S: \map {\paren {g \circ f} } A\) \(=\) \(\displaystyle \map g {\map f A}\)
\(\displaystyle \) \(=\) \(\displaystyle \map g {\chi_A}\)
\(\displaystyle \) \(=\) \(\displaystyle \chi_A^{-1} \sqbrk {\set 1}\)
\(\displaystyle \) \(=\) \(\displaystyle A\)

So $g \circ f = I_{\powerset S}$, that is, the identity mapping on $\powerset S$.


It follows from Bijection iff Left and Right Inverse that $f$ and $g$ are bijections.


Thus by Cardinality of Set of All Mappings the result follows.

$\blacksquare$


Proof 2

Enumerating the subsets of $S$ is equivalent to counting all of the ways of selecting $k$ out of the $n$ elements of $S$ with $k = 0, 1, \ldots, n$.

So, from Cardinality of Set of Subsets, the number we are looking for is:

$\displaystyle \card {\powerset S} = \sum_{k \mathop = 0}^n \binom n k$

But from the binomial theorem:

$\displaystyle \paren {x + y}^n = \sum_{k \mathop = 0}^n \binom n k x^{n - k} y^k$

It follows that:

$2^n = \displaystyle \paren {1 + 1}^n = \sum_{k \mathop = 0}^n \binom n k \paren 1^{n - k} \paren 1^k = \sum_{k \mathop = 0}^n \binom n k = \card {\powerset S}$

$\blacksquare$


Proof 3

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$


Informal Proof

Given an element $x$ of $S$, each subset of $S$ either includes $x$ or does not include $x$ (this follows directly from the definition of a set), which gives us two possibilities.

The same reasoning holds for any element of $S$.

One can intuitively see that this means that there are $\displaystyle \underbrace {2 \times 2 \times \ldots \times 2}_{\card S} = 2^{\card S}$ total possible combinations of elements of $S$.

This is exactly $\card {\powerset S}$.

$\blacksquare$


Sources