Cardinality of Power Set

Theorem

Let $S$ be a set such that:

$\left|{S}\right| = n$

where $\left|{S}\right|$ denotes the cardinality of $S$,

Then:

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

where $\mathcal P \left({S}\right)$ denotes the power set of $S$.

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

Proof 1

Let $T = \left\{{0, 1}\right\}$.

For each $A \in \mathcal P \left({S}\right)$, we consider the characteristic function $\chi_A: S \to T$ defined as:

$\forall x \in S: \chi_A \left({x}\right) = \begin{cases} 1 & : x \in A \\ 0 & : x \notin A \end{cases}$

Now consider the mapping $f: \mathcal P \left({S}\right) \to T^S$:

$\forall A \in \mathcal P \left({S}\right): f \left({A}\right) = \chi_A$

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

Also, consider the mapping $g: T^S \to P \left({S}\right)$:

$\forall \phi \in T^S: g \left({\phi}\right) = \phi^{-1} \left({\left\{{1}\right\}}\right)$

Note that $g$ is itself a mapping from a set of mappings: $\phi: S \to T$ is itself a mapping.

Consider the characteristic function of $\phi^{-1} \left({\left\{{1}\right\}}\right)$, denoted $\chi_{\phi^{-1} \left({\left\{{1}\right\}}\right)} \left({x}\right)$.

We have:

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

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \forall \phi \in T^S: \left({f \circ g}\right) \left({\phi}\right)\)	\(=\)	\(\displaystyle f \left({\phi^{-1} \left({\left\{ {1}\right\} }\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \chi_{\phi^{-1} \left({\left\{ {1}\right\} }\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \phi\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

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

So far so good. Now we consider:

$\chi_A^{-1} \left({\left\{{1}\right\}}\right) = A$

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

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \forall A \in \mathcal P \left({S}\right): \left({g \circ f}\right) \left({A}\right)\)	\(=\)	\(\displaystyle g \left({f \left({A}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g \left({\chi_A}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \chi_A^{-1} \left({\left\{ {1}\right\} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle A\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

So $g \circ f = I_{\mathcal P \left({S}\right)}$, that is, the identity mapping on $\mathcal P \left({S}\right)$.

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

We can see that 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 \left|{\mathcal P \left({S}\right)}\right| = \sum_{k=0}^n \binom n k$

But from the binomial theorem:

$\displaystyle \left({x + y}\right)^n = \sum_{k=0}^n \binom n k x^{n-k} y^k$

It follows that:

$2^n = \displaystyle \left({1 + 1}\right)^n = \sum_{k=0}^n \binom n k \left({1}\right)^{n-k} \left({1}\right)^k = \sum_{k=0}^n \binom n k = \left|{\mathcal P \left({S}\right)}\right|$

$\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 the set.

One can intuitively see that this means that there are $\displaystyle\underbrace{2 \times 2 \times \ldots \times 2}_{\vert S \vert} = 2^{\vert S \vert}$ total possible combinations of elements of $S$, which is exactly $\vert\mathcal{P}(S)\vert$.

$\blacksquare$

Note

The formal mathematical backing for the intuitive leap made in this "proof" is non-trivial, so while this it serves as an excellent demonstration of why this result holds true, it does not constitute a fully rigorous proof of this theorem.

Special Case

This formula even works when $S = \varnothing$.

Clearly:

$\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 the main result still holds when $\left|{S}\right| = 0$.

Sources

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 1$
• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 5$: Complements and Powers
• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 13$: Arithmetic
• J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $1.13$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $1.8$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.6$: Theorem $8: \ 1$
• B. Hartley and T.O. Hawkes: Rings, Modules and Linear Algebra (1970): $\S 1.2$: Ring Example $6$ (in passing)
• George E. Andrews: Number Theory (1971): $\S 3.1$: Exercise $1$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 15 \alpha$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.6$: Problem $41$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 6.8$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.6$ (in passing)