Cantor's theorem: $A \prec \mathcal{P}(A)$

Let $A$ be a set and $\mathcal{P}(A)$ its power set. Then there is no surjection $A \to \mathcal{P}(A)$ (Injection, surjection, bijection).

Consequently $A \not\approx \mathcal{P}(A)$ while $A \preceq \mathcal{P}(A)$, that is, $A \prec \mathcal{P}(A)$ (Equinumerous sets, $A \approx B$ and $A \preceq B$): the power set is strictly larger, for every set whatsoever.

This is Cantor's diagonal argument in its non-circular form. It uses nothing about $\mathbb{R}$, nothing about decimal or binary expansions, and no choice principle: only the Power Set axiom, to form $\mathcal{P}(A)$, and Separation, to form the diagonal set.

• Where the "diagonal" is. Reading $f$ as a table whose row $x$ lists which elements belong to $f(x)$, the set $D$ flips the diagonal entries: $x \in D$ exactly when the entry at position $(x,x)$ says "no". The resulting subset differs from every row in at least one place, namely on the diagonal, so it is no row at all.

• Why this is the diagonal argument that survives in this library. The familiar diagonal proof that $\mathbb{R}$ is uncountable alters the digits of a decimal expansion. Decimal expansions are infinite series, which this library has not built, so that proof would rest on machinery that is not yet available. Applied to power sets the argument needs nothing but Separation, and $\mathbb{R}$ is instead proved uncountable by Cantor's earlier nested-interval argument ($\mathbb{R}$ is uncountable (Cantor's nested intervals, 1874)).

• Taking $A = \mathbb{N}$ gives $\mathbb{N} \prec \mathcal{P}(\mathbb{N})$. It also gives that $\mathcal{P}(\mathbb{N})$ is uncountable, and by the shortest possible route: $\mathcal{P}(\mathbb{N})$ is nonempty, so if it were at most countable there would be a surjection $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ (A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$), which is exactly what the theorem forbids. No fact about finite sets is needed for this. Iterating gives $\mathbb{N} \prec \mathcal{P}(\mathbb{N}) \prec \mathcal{P}(\mathcal{P}(\mathbb{N})) \prec \cdots$, so there is no largest set and no "set of all sets": such a set would have its own power set as a subset, contradicting the theorem.

• The proof is the same argument as Russell's paradox, in a form where nothing goes wrong: the assumption refuted is not the existence of a set but the surjectivity of a function. See The continuum hypothesis, and what this page does not prove for what is, and is not, known about the gap between $\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$.