康托尔定理

为导出矛盾,假设存在满射 $f : A \to \mathcal{P}(A)$;下面推出矛盾,从而说明这样的满射不可能存在。

定义"对角线"集合 $D = \{x \in A : x \notin f(x)\}$:它收集了 $A$ 中所有不属于自身在 $f$ 下的像的元素。由于 $D$ 是 $A$ 的子集,它是 $\mathcal{P}(A)$ 的一个元素。

由于假设 $f$ 是满射,必存在 $a_0 \in A$ 使得 $f(a_0) = D$。现在提出关键问题:$a_0 \in D$ 吗?

若 $a_0 \in D$,则由 $D$ 的定义,$a_0 \notin f(a_0)$;但 $f(a_0) = D$,这就说明 $a_0 \notin D$——矛盾。若 $a_0 \notin D$,则由 $D$ 的定义(恰好排除满足 $a_0 \in f(a_0)$ 的元素),这迫使 $a_0 \in f(a_0) = D$——同样矛盾。

无论哪种情况都得到矛盾,故满射 $f : A \to \mathcal{P}(A)$ 不可能存在。结合从 $A$ 到 $\mathcal{P}(A)$ 的单射 $x \mapsto \{x\}$,即得 $|A| < |\mathcal{P}(A)|$。