Cardinality of Power Set of Finite Set/Proof 2
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$.
Proof
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:
- $\ds \card {\powerset S} = \sum_{k \mathop = 0}^n \binom n k$
But from the binomial theorem:
- $\ds \paren {x + y}^n = \sum_{k \mathop = 0}^n \binom n k x^{n - k} y^k$
It follows that:
- $2^n = \ds \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$
Sources
- 1951: Nathan Jacobson: Lectures in Abstract Algebra: Volume $\text { I }$: Basic Concepts ... (previous) ... (next): Introduction $\S 1$: Operations on Sets
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): $\S 2.3$. Partitions: Example $35$