映射与基数

这说明不存在"最大的无穷"——无论集合多大,只要取其幂集就总能得到一个严格更大的集合。正是这条定理使得无穷的层级不可避免地无限延伸,其对角线论证的证明技巧,正是用来证明某些问题不可计算的论证方法的直接源头。

为导出矛盾,假设存在满射 $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)|$。

仅通过单射来比较基数(每个集合都能嵌入另一个之中),就已经像有限集合那样迫使两个集合大小完全相同。这使得我们可以通过构造两个容易的单向嵌入,而不是一个困难的直接双射,来证明 $|A|=|B|$——下面的例子正是用这种方法说明区间 $[0,1]$ 与 $(0,1)$ 具有相同的基数。

设 $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$ 同理定义。每个元素的链要么无限地往回延伸,要么停在 $A$ 中某个没有 $g$-原像的元素处,要么停在 $B$ 中某个没有 $f$-原像的元素处。这把 $A$ 划分成三部分:$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)$。由于三部分两两不相交,且各自双射到 $B$ 中对应部分($f$ 映到 $B_A \cup B_\infty$,$g^{-1}$ 映到 $B_B$),合并后的映射 $h$ 就是从整个 $A$ 到整个 $B$ 的双射,证明了 $|A|=|B|$。