= Cantor's theorem
{c}
{wiki}
= Cantor theorem
{c}
{synonym}
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>.
Back to article page
