順序数と基数

これにより、有限、$\omega$、そしてそれ以降のすべての順序数について、「それより小さいすべてで成り立つと仮定する」という一つの扱いだけで命題を証明できる。原理自体の記述には基底段階や極限段階を別立てにする必要がない。

背理法で、$C$ がすべての順序数を含まないと仮定する。すると $C$ に属さない順序数からなる類 $D$ は空でない。順序数自身は整列している(順序数からなる空でない類は必ず最小元を持つ——これは順序数の定義的性質である)ので、$D$ には最小元が存在する。それを $\alpha$ とする。

$\alpha$ の最小性により、$\beta<\alpha$ を満たす順序数はすべて $D$ に属さない、すなわちすべての $\beta<\alpha$ について $\beta \in C$ が成り立つ。

しかしこれはまさに定理の仮定を $\alpha$ に適用したものである:「すべての $\beta<\alpha$ で $\beta \in C$」ならば $\alpha \in C$。したがって $\alpha \in C$。

これは $\alpha \in D$(すなわち $\alpha \notin C$)と矛盾する。この矛盾により、そのような最小の反例 $\alpha$ は存在し得ないので $D=\emptyset$:$C$ はすべての順序数を含む。$\blacksquare$

ZFC だけからは $2^{\aleph_0}$ の正確な値を知ることはできないが(コーエンの独立性の結果)、この定理はそれについて無条件に証明できる数少ない事実の一つである:それが何であれ、真に小さい基数からなる $\omega$ 列を下から近づけていくことはできない。

まず一般的なケーニヒの不等式を証明する:添字集合 $I$ 上のすべての $i$ について $\kappa_i < \lambda_i$ ならば、$\sum_{i\in I}\kappa_i < \prod_{i\in I}\lambda_i$ である。$|B_i|=\lambda_i$ となる集合 $B_i$ と、$|A_i|=\kappa_i$ となる部分集合 $A_i \subsetneq B_i$ を固定する。不等式 $\sum_i \kappa_i \le \prod_i \lambda_i$ は容易である(各 $a\in A_i$ を、座標 $i$ では $a$、他の座標では固定の既定値であるようなタプルへ送る)。したがって本質は等しくないことを示すことにある。

背理法で、ある全射 $h : \bigsqcup_{i\in I} A_i \to \prod_{i\in I} B_i$ が存在すると仮定する。各 $i$ について $h_i:A_i\to B_i$、$a \mapsto h(a)(i)$($h(a)$ の第 $i$ 座標)とする。$|A_i|=\kappa_i<\lambda_i=|B_i|$ なので、$h_i$ は $B_i$ への全射になり得ない(もしそうなら、$B_i$ の各元に原像を一つ選ぶことで $B_i$ から $A_i$ への単射が得られ、$\lambda_i\le\kappa_i$ を強制し矛盾する)。そこで各 $i$ について $d_i \in B_i \setminus \operatorname{ran}(h_i)$ を選び、$g(i)=d_i$ であるタプル $g \in \prod_i B_i$ を作る。

$h$ が全射なので、ある $a$(例えば $a \in A_j$)について $g=h(a)$。すると $g(j)=h(a)(j)=h_j(a) \in \operatorname{ran}(h_j)$。しかし構成により $g(j)=d_j \notin \operatorname{ran}(h_j)$——直接の矛盾である。したがって全射 $h$ は存在せず、$\sum_i\kappa_i < \prod_i\lambda_i$ が得られる。($I=X$、$\kappa_i=1$、$\lambda_i=2$ とおけば、特別な場合としてカントールの古典的対角線論法 $|X|<2^{|X|}$ が再現される。)

次に背理法で $\operatorname{cf}(2^{\aleph_0})=\aleph_0$ と仮定する。すると $2^{\aleph_0}$ は真に小さい基数の狭義増加 $\omega$ 列 $\kappa_0<\kappa_1<\kappa_2<\cdots$ の和である、すなわち $2^{\aleph_0}=\sum_{n<\omega}\kappa_n$ かつ $\kappa_n < 2^{\aleph_0}$ がすべての添字で成り立つ。ケーニヒの不等式を、すべての $n$ について $\lambda_n := 2^{\aleph_0}$ を一定として適用する(すべての $n$ で $\kappa_n < 2^{\aleph_0} = \lambda_n$ なので有効):

$$2^{\aleph_0} = \sum_{n<\omega}\kappa_n \;<\; \prod_{n<\omega}\lambda_n = \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0\cdot\aleph_0} = 2^{\aleph_0}.$$

これは $2^{\aleph_0}<2^{\aleph_0}$ を意味し、不合理である。よって $\operatorname{cf}(2^{\aleph_0})\neq\aleph_0$。共終数はそれより小さくなることは決してない(任意の無限基数について少なくとも $\aleph_0$ であり有限にはなり得ない)ので、$\operatorname{cf}(2^{\aleph_0})>\aleph_0$ と結論できる。$\blacksquare$