Power Set

🅟 Feb 17, 2026

  🅤 Jun 23, 2026

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. If $f : X \to \powerset(X)$ were a surjection, 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 $X$,

\[\lvert \powerset(X) \rvert = 2^{\lvert X \rvert}.\]

Proof.

\[\varphi : \powerset(X) \to \fun(X, 2), \, A \mapsto f_A\]

is a bijection, where

\[f_A : X\to 2, \, x \mapsto \begin{cases} 1, & \text{if $x\in A$}; \\ 0, & \text{if $x\notin A$}. \end{cases}\]

As a corollary of Cantor’s Theorem and Proposition 3:

Proposition 4.

For any cardinal $\kappa$,

\[\kappa < 2^\kappa.\]