 Cantor's theorem

There is no surjection from a set $X$ onto its power set $\mathcal{P}(X)$. Consequently $\mathcal{P}(X)$ has strictly greater cardinality than $X$.

For any candidate function $f:X\to \mathcal{P}(X)$, form $D=\{x\in X:x\notin f(x)\}$. This is a subset of $X$ by set comprehension. If $f(d)=D$, then $d\in D$ holds exactly when $d\notin D$, a contradiction. Thus $D$ is missing from the image of $f$. On the other hand, $x\mapsto \{x\}$ is an injection from $X$ into its power set, establishing the strict comparison of cardinalities. For $X=\mathbb{N}$, the omitted selection is the subset version of Cantor's diagonal argument.

Cantor's theorem is a fundamental result in set theory proposed by the mathematician Georg Cantor. It states that for any set \( S \), the set of all subsets of \( S \), known as the power set of \( S \) (denoted as \( \mathcal{P}(S) \)), has a strictly greater cardinality (size) than the set \( S \) itself.