序数与基数

这使我们只需处理"假设对所有更小的都成立"这一种情形,就能证明命题对每个序数——有限、$\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$ 满足 $|B_i|=\lambda_i$,子集 $A_i \subsetneq B_i$ 满足 $|A_i|=\kappa_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 \in \prod_i B_i$ 为满足 $g(i)=d_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$