Definition 1. The power set of a set $X$ is
\[\powerset(X) = \{Y : Y \subseteq X\}.\]This is a set by Axiom of Power Set.
Proposition 2. Cantor’s Theorem. For any set $X$,
\[\lvert X \rvert < \lvert \powerset(X) \rvert.\]Proof
For any surjection $f : X \to \powerset(X)$, there would be an $a \in X$ such that
\[f(a) = \{x \in X : x \notin f(x)\}.\]Consider whether $a \in f(a)$.
Proposition 3. For any set $X$,
\[\lvert \powerset(X) \rvert = 2^{\lvert X \rvert}.\]Proof
For every $A \subseteq X$ define
\[f_A : X\to 2, \, x \mapsto \begin{cases} 1, & \text{if $x\in A$}; \\ 0, & \text{if $x\notin A$}, \end{cases}\]then
\[\varphi : \powerset(X) \to \fun(X, 2), \, A \mapsto f_A\]defines a bijection.
As a corollary of Cantor’s Theorem and Proposition 3:
Proposition 4. For any cardinal $\kappa$,
\[\kappa < 2^\kappa.\]References
- [1]
- Wikipedia contributors. Power set. Wikipedia, The Free Encyclopedia.
- [2]
- Thomas Jech. Set Theory. 3rd Millennium ed, rev. and expanded. Springer, 2002. pp. 9; 27–29.