写像と濃度

これは「最大の無限」というものが存在しないことを示している——どんなに大きな集合からでも、そのべき集合を取るだけで真に大きな集合を作ることができる。この定理によって無限の階層が無限に続くことが避けられなくなり、その対角線論法という証明技法は、ある種の問題が計算不可能であることを示す議論の直接の祖先である。

矛盾を導くために、全射 $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)|$ が得られる。

単射だけで濃度を比較すること(それぞれの集合がもう一方に収まること)だけで、有限集合の場合と同じく、両者はまったく同じ大きさになることが強制される。これにより、1つの難しい直接的全単射を作る代わりに、2つの易しい一方向の埋め込みを作ることで $|A|=|B|$ を証明できる——これはまさに、区間 $[0,1]$ と $(0,1)$ が同じ濃度を持つことを以下の例で示す方法である。

与えられた2つの単射を $f : A \to B$、$g : B \to A$ とする。考え方は、各元について $f$ と $g$ を交互に逆にたどって得られる祖先の連鎖を追跡し、各連鎖が「どこから始まるか」に応じて最終的な全単射を部分ごとに組み立てることである。

$a \in A$ に対して、後退連鎖 $a, g^{-1}(a), f^{-1}(g^{-1}(a)), \ldots$ を、必要な逆写像が定義されている限り続けて定義し、$b \in B$ についても同様にする。各元の連鎖は、永遠に続くか、$g$ による原像を持たない $A$ の元で止まるか、$f$ による原像を持たない $B$ の元で止まるかのいずれかである。これにより $A$ は3つの部分 $A_A$(連鎖が $A$ で止まる)、$A_B$(連鎖が $B$ で止まる)、$A_\infty$(連鎖が止まらない)に分割され、同様に $B$ も $B_A, B_B, B_\infty$ に分割される。

$A$ で止まる連鎖、または止まらない連鎖の上では、$f$ 自身がすでにその部分の $A$ から対応する部分の $B$ への全単射を与えている(これらの元は単射によって到達され、$B$ 側で先に「尽きる」ことがないため)。$B$ で止まる連鎖の上では、$g$ がその部分の $B$ から対応する部分の $A$ への全単射を与えるので、その逆写像 $g^{-1}$ がその部分の $A$ からその部分の $B$ への全単射を与える。

$h : A \to B$ を、$a \in A_A \cup A_\infty$ のとき $h(a) = f(a)$、$a \in A_B$ のとき $h(a) = g^{-1}(a)$ と定義する。3つの部分は互いに素であり、それぞれが $B$ の対応する部分へ全単射で写る($f$ は $B_A \cup B_\infty$ へ、$g^{-1}$ は $B_B$ へ)ので、統合された写像 $h$ は $A$ 全体から $B$ 全体への全単射となり、$|A|=|B|$ が証明される。