カントールの定理

矛盾を導くために、全射 $f : A \to \mathcal{P}(A)$ が存在すると仮定する;矛盾を導き、そのような全射が存在し得ないことを示す。

「対角線」集合 $D = \{x \in A : x \notin f(x)\}$ を定義する:これは $f$ による自分自身の像に属さない $A$ のすべての元を集めたものである。$D$ は $A$ の部分集合なので、$\mathcal{P}(A)$ の元である。

$f$ が全射だと仮定しているので、$f(a_0) = D$ となる $a_0 \in A$ が存在するはずである。ここで決定的な問いを立てる:$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)|$ が得られる。