The Power Set: Definition, Cardinality, and Combinatorics
In set theory, the power set $\mathcal{P}(S)$ of a set $S$ is defined as the set of all subsets of $S$, including the empty set $\emptyset$ and the set $S$ itself.
The Power Set Cardinality Theorem
For any finite set $S$ containing $n$ elements:
|\mathcal{P}(S)| = 2^n
Proof via Binary Selection
For every element in the set $S$, there are exactly two independent choices when constructing a subset: either include the element or exclude it. By the multiplication rule of combinatorics:
\underbrace{2 \times 2 \times 2 \times \dots \times 2}_{n \text{ times}} = 2^n
Binomial Distribution of Subsets by Cardinality
The total count $2^n$ is partitioned across subset sizes $k$ according to Pascal's triangle and the binomial theorem:
2^n = \sum_{k=0}^n \binom{n}{k}
- Subsets of size 0: $\binom{n}{0} = 1$ (the empty set $\emptyset$).
- Subsets of size 1: $\binom{n}{1} = n$ (singletons).
- Subsets of size $n$: $\binom{n}{n} = 1$ (the entire set $S$).
Power Set Enumeration for Small Sets
| Set Elements | Set Size $n$ | Total Subsets $2^n$ | Complete Subset Enumeration $\mathcal{P}(S)$ |
|---|---|---|---|
| $\emptyset$ | 0 | $2^0 = 1$ | $\{\emptyset\}$ |
| $\{A\}$ | 1 | $2^1 = 2$ | $\{\emptyset, \{A\}\}$ |
| $\{A, B\}$ | 2 | $2^2 = 4$ | $\{\emptyset, \{A\}, \{B\}, \{A, B\}\}$ |
| $\{A, B, C\}$ | 3 | $2^3 = 8$ | $\{\emptyset, \{A\}, \{B\}, \{C\}, \{A, B\}, \{A, C\}, \{B, C\}, \{A, B, C\}\}$ |