8 无穷集合

\[ \newcommand\surj{\text{ surj }} \newcommand\bij{\text{ bij }} \newcommand\inj{\text{ inj }} \newcommand\strict{\text{ strict }} \]

这章是关于无限集合以及证明关于它们的某些挑战.

等一下！为什么在这本《计算机科学中的数学》教科书里面要提到无限呢？毕竟, 计算机中的任何数据都受限于它的内存大小的, 而计算机内存的可不是无限大的, 因为宇宙（或至少被认为是）是有界的. 那么为什么不坚持使用一些大的但有限的集合呢？这是一个好问题, 但让我们看看能否说服你处理无限集合是不可避免的.

你可能没有注意到, 但到目前为止你已经习以为常地接受了使用整数、有理数、无理数及其他们构成的序列. 这些都是无限集合. 此外, 你真的希望物理学或其他科学因为宇宙是有限的, 从而使用有限的测量结果, 放弃使用实数吗？这非常有说服力——而且简单得多——忽略这些大而不确定的界限（宇宙似乎一直在变大）实数理论也是不可或缺的.

同样在计算机科学中, 我们认为编写一个程序把两个最多是 \(n\) 位非负整数相加(这个整数的位数 \(n\) 可以像天上的星星一样多), 与编写一个程序来把任意两个整数相加, 无论它们的位数是多少, 没有什么不同. 同样的道理也适用于编写编译器: 利用有界宇宙的事实, 即只有有限数量的程序将会被编译, 我们还是把整个无穷的集合纳入考虑之中.

无限集合还提供了一个很好的环境来练习证明方法, 因为单凭直觉, 在不加证明的步骤中很容易混入不正当的步骤. 研究无限集合的一个真正令人震惊的结果是: 这导致了对计算机可能做什么的基本逻辑极限的发现. 例如, 在第 8.2 节中, 我们将使用无限集合推导出的推理来证明对于编程语言来说, 不可能有一个完美的类型检查器.

所以在本章中, 我们要求你咬紧牙关, 开始学习应对无限.

8.1 无限基数

在十九世纪晚期, 数学家乔治·康托尔正研究傅里叶级数的收敛性, 康托尔发现了一些“在大多数情况下”收敛的级数, 虽然这些级数在无限多个点上面没有收敛. 因此, 康托尔需要一种方法来比较无限集合的大小. 为了理解这一点, 他得到了将映射规则定理 4.5.4 扩展到无限集合的想法: 他认为两个无限集合在它们之间存在双射时具有“相同的大小”. 同样, 当 \(A \surj B\) 时, 一个无限集合 \(A\) 应被认为“与集合 \(B\) 一样大”. 因此, 当 \(A\) “不像” \(B\) 一样大时, 我们可以认为 \(A\) 严格小于 \(B\), 即 \(A \strict B\).

定义 8.1.1.

当且仅当 NOT(\(A\) surj \(B\)) 时, \(A\) 严格小于 \(B\).

在有限集合上, 这一严格关系确实意味着“严格更小”. 这直接由映射规则定理 4.5.4 得出.

推论 8.1.2.

对于有限集合 \(A, B\),

\[ A \strict B \iff |A| < |B|. \]

\[ \begin{array}{lllr} A \text { strict } B & \text { iff } & \operatorname{NOT}(A \operatorname{surj} B) & \text { (Def 8.1.1) } \\ & \text { iff } & \operatorname{NOT}(|A| \geq|B|) & \text { (Theorem 4.5.4.(4.5)) } \\ & \text { iff } & |A|<|B| . & \end{array} \]

康托尔虽然偏离了傅里叶级数的研究, 但他努力基于这些想法发明出一套无限集合理论. 他的理论最终对数学和计算机科学的基础产生了深远的影响. 但康托尔在他那个时代树敌众多, 因为他的工作, 数学界普遍怀疑他们所谓的“康托尔乐园”的合理性.

康托尔思想的一个很好的技术特征是, 它避免了对无限集合“大小”的定义——所需要的只是比较“大小”.

警告! 我们还没有, 也不会, 定义无限集合的“大小”. 定义无限“大小”需要定义一些称为序数(ordinal) 的特殊无限集合, 这些序数具有特殊的良好序性质. 序数理论需要比我们需要深入得多的集合论, 但我们可以不定义无限大小就很好地理解这些内容. 我们所需要的只是集合之间的“同样大”和“同样大小”的关系, surj 和 bij.

但是还有一点需要注意: 我们已经将 surj 称为“同样大”关系, 并将 bij 称为集合上的“同样大小”关系. 当然, 大多数关于有限集合的“同样大”和“同样大小”性质的 surj 和 bij 的性质确实可以完全适用于无限集合, 但一些重要的性质却不能——正如我们将要展示的. 所以你必须小心: 不要假设 surj 在无限集合上有任何特定的“同样大”性质, 直到它被证明.

让我们从一些有限集合上适用于无限集合的“同样大”和“同样大小”关系的熟悉性质开始:

引理 8.1.3.

对于任何集合 \(A, B, C\),

\(A \surj B \iff B \inj A\).
如果 \(A \surj B\) 且 \(B \surj C\), 那么 \(A \surj C\).
如果 \(A \bij B\) 且 \(B \bij C\), 那么 \(A \bij C\).
\(A \bij B \iff B \bij A\).

第1部分根据 \(R\) 具有 \([≤ 1 \text{出}, ≥ 1 \text{入]\) 满射函数性质得出, 第2部分根据满射的合成是满射得出, 第3和4部分根据前两部分得出, 因为如果 \(R\) 是双射, 那么 \(R\) 和 \(R^{-1}\) 是满射函数.

定理 8.1.4. (Schröder-Bernstein)

对于任何集合 \(A, B\), 如果 \(A \surj B\) 且 \(B \surj A\), 那么 \(A \bij B\).

也就是说, Schröder-Bernstein 定理表明, 如果 \(A\) 至少和 \(B\) 一样大且反之亦然, \(B\) 至少和 \(A\) 一样大, 那么 \(A\) 和 \(B\) 是同一大小的集合. 这种方式表述, 你可能会认为这一定理是理所当然的, 但你错了. 对于无限集合 \(A\) 和 \(B\), Schröder-Bernstein 定理的证明实际上相当具有挑战: 这是因为存在一个满射函数 \(f: A \to B\) —— 这不一定是一个双射 —— 和一个满射函数 \(g: B \to A\) —— 这也不一定是一个双射 —— 并不意味着一定存在一个双射 \(e: A \to B\). 这里的思路是通过函数 \(f\) 和 \(g\) 的一部分来构造 \(e\). 我们将把实际的构造留给问题 8.12.

另一个熟悉的集合性质是，对于任意两个集合，要么第一个集合至少和第二个集合一样大，要么第二个集合至少和第一个集合一样大。对于有限集合，这可以从映射规则中简单地推导出来。实际上，这对于无限集合仍然成立，这同样不是显而易见的.

定理 8.1.5.

对于所有集合 \(A, B\),

\[ A \surj B \quad \text{或} \quad B \surj A. \]

定理 8.1.5 让我们可以证明, 有限集合的另一个基本性质可以延续到无限集合:

引理 8.1.6.

\[ A \strict B \quad \text{且} \quad B \strict C \quad \text{蕴含} \quad A \strict C. \tag{8.1} \]

假设 8.1 成立, 并且为了反证假设 \(A \strict C\) 不成立, 这意味着 \(A \surj C\). 现在因为 \(B \strict C\), 定理 8.1.5 让我们得出 \(C \surj B\). 所以我们有

\[ A \surj C \quad \text{且} \quad C \surj B, \]

并且引理 8.1.3.2 让我们得出 \(A \surj B\), 这与 \(A \strict B\) 的事实相矛盾.

我们省略了定理 8.1.5 的证明, 因为证明它涉及技术性的集合论（通常是序数理论）, 而我们不打算详细讨论. 但由于证明引理 8.1.6 是我们将要用到的唯一结论, 我们希望你不会觉得看不到证明而感到自己被骗了.

8.1.1 无限不同

有限集合的一条基本性质不能延续到无限集合, 即添加新元素会使集合变大. 也就是说, 如果 \(A\) 是有限集合而 \(b \notin A\), 那么 \(|A \cup \{b\}| = |A| + 1\), 因此 \(A\) 和 \(A \cup \{b\}\) 不是同一大小. 但是如果 \(A\) 是无限的, 那么这两个集合是同一大小！

引理 8.1.7.

设 \(A\) 是集合且 \(b \notin A\). 那么 \(A\) 是无限的当且仅当 \(A \bij A \cup \{b\}\).

证明

由于 \(A\) 是有限集合时 \(A\) 与 \(A \cup \{b\}\) 不同大小, 我们只需要证明 \(A\) 是无限集合时 \(A\) 与 \(A \cup \{b\}\) 相同大小.

也就是说, 我们必须找到 \(A \cup \{b\}\) 和 \(A\) 之间的双射. 方法如下: 由于 \(A\) 是无限的, 它肯定至少有一个元素；称它为 \(a_0\). 但由于 \(A\) 是无限的, 它至少有两个元素, 并且其中一个元素不能等于 \(a_0\)；称这个新元素为 \(a_1\). 但由于 \(A\) 是无限的, 它至少有三个元素, 其中一个元素不能等于 \(a_0\) 和 \(a_1\)；称这个新元素为 \(a_2\). 继续这样, 我们得出 \(a_0, a_1, a_2, \ldots, a_n, \ldots\) 的无限序列, 这些都是 \(A\) 的不同元素. 现在很容易定义一个从 \(A \cup \{b\}\) 到 \(A\) 的双射 \(e\):

\[ \begin{align*} e(b) & := a_0, \\ e(a_n) & := a_{n+1} \quad \text{对于 } n \in \mathbb{N}, \\ e(a) & := a \quad \text{对于 } a \in A - \{b, a_0, a_1, \ldots\}. \end{align*} \]

8.1.2 可数集

集合 \(C\) 是可数的当且仅当它的元素可以按顺序列出, 即序列中的元素正好是集合 \(C\) 的元素:

\[ c_0, c_1, \ldots, c_n, \ldots \]

假设列表中没有重复元素, 这样说集合 \(C\) 可以按这种方式列出, 相当于说函数 \(f: \mathbb{N} \to C\) 由规则 \(f(i) := c_i\) 定义是一个双射.

定义 8.1.8.

集合 \(C\) 是可数无穷的当且仅当 \(\mathbb{N} \bij C\). 集合是可数的当且仅当它是有限或可数无穷的. 集合是不可数的当且仅当它不是可数的.

我们还可以使用有限元素集来构造一个无限列表, 如果允许重复. 例如, 我们可以将三元素集 \(\{2, 4, 6\}\) 的元素列为:

\[ 2, 4, 6, 6, 6, \ldots \]

这个简单的观察导致了可数集的另一种表述, 不区分有限和无限集合的情况. 也就是说, 如果存在一个列表:

\[ c_0, c_1, \ldots, c_n, \ldots \]

列出集合 \(C\) 的元素, 可能有重复, 则集合 \(C\) 是可数的.

引理 8.1.9.

集合 \(C\) 是可数的当且仅当 \(\mathbb{N} \surj C\). 事实上, 非空集合 \(C\) 是可数的当且仅当存在一个从 \(\mathbb{N}\) 到 \(C\) 的满射函数 \(g\).

证明留作问题 8.13.

最基本的可数无穷集合是集合 \(\mathbb{N}\) 本身. 但整数集 \(\mathbb{Z}\) 也是可数无穷的, 因为整数可以按以下顺序列出:

\[ 0, -1, 1, -2, 2, -3, 3, \ldots \tag{8.2} \]

在这种情况下, 列表中第 \(n\) 个元素的简单公式如下. 即, 双射 \(f: \mathbb{N} \to \mathbb{Z}\) 使得 \(f(n)\) 是列表中的第 \(n\) 个元素可以定义为:

\[ f(n) := \begin{cases} n / 2 & \text{如果 } n \text{ 是偶数}, \\ -(n + 1) / 2 & \text{如果 } n \text{ 是奇数}. \end{cases} \]

还有一种简单的方法可以列出所有非负整数对(这表明 \(\mathbb{N} \times \mathbb{N}\) 也是可数无穷的(问题 8.23)). 从这个结论出发, 很容易得出非负有理数集合 \(\mathbb{Q}_{\geq 0}\) 是可数的. 这可能有些惊讶——毕竟, 有理数在整数之间填满了整个空间, 对于任何两个有理数之间都有另一个有理数. 因此, 虽然你不能将所有有理数按顺序列出, 但问题 8.11 说明了如何做到这一点. 更一般地, 很容易表明可数集在并集和积下是封闭的（问题 8.22 和 8.23）, 这意味着许多熟悉的集合是可数的:

推论 8.1.10.

以下集合是可数无穷的:

\[ \mathbb{Z}^+, \mathbb{Z}, \mathbb{N} \times \mathbb{N}, \mathbb{Q}^+, \mathbb{Z} \times \mathbb{Z}, \mathbb{Q}. \]

对引理 8.1.7 的证明进行小修改表明可数无穷集合是“最小”的无限集合. 即:

引理 8.1.11.

如果 \(A\) 是无限集合, 且 \(B\) 是可数的, 那么 \(A \surj B\).

我们将证明留作问题 8.10.

此外, 添加一个新元素到无限集合不会改变它的大小, 你可以通过一次添加一个元素, 添加任意有限数量的元素而不改变大小. 更强的命题是: 你可以向无限集合添加可数无穷数量的新元素, 并且仍然得到相同大小的集合（问题 8.15）.

顺便提一句, 一个常见的错误是认为, 由于你可以向无限集合添加任意有限数量的元素, 并且与原始集合有双射关系, 所以你也可以无限地添加新元素. 一般来说, 这并不是真的, 仅仅因为你可以做某事有限次, 也可以无限次. 例如, 从3开始, 如果你只增加任意多但是有限次, 结果将是大于或等于3的某个整数. 但如果你增加无限次, 你根本得不到一个整数.

8.1.3 幂集严格更大

康托尔令人惊讶的发现是, 并非所有的无限集合都是同样大小. 特别地, 他证明了对于任意集合 \(A\), 幂集 \(\text{pow}(A)\) 比 \(A\) “严格更大”. 即:

定理 8.1.12. [康托尔]

对于任意集合 \(A\),

\[ A \strict \text{pow}(A). \]

证明

为了证明 \(A\) 严格小于 \(\text{pow}(A)\), 我们必须证明如果 \(g\) 是一个从 \(A\) 到 \(\text{pow}(A)\) 的函数, 那么 \(g\) 不是一个满射. 由于任何非空陪域的部分函数都可以扩展为具有相同范围的满射函数（读者: 问自己如何实现）, 我们可以安全地假设 \(g\) 是全函数.

为了证明 \(g\) 不是满射, 我们将简单地找到一个 \(A_g \subseteq A\) 的子集不在 \(g\) 的值域中. 这个想法是, 对于任意元素 \(a \in A\), 查看集合 \(g(a) \subseteq A\) 并问 \(a\) 是否在 \(g(a)\) 中. 首先, 定义

\[ A_g := \{a \in A \mid a \notin g(a)\}. \]

\(A_g\) 是 \(A\) 的一个良定义的子集, 这就这意味着它是 \(\text{pow}(A)\) 的一个成员. 但 \(A_g\) 不可能在 \(g\) 的值域中, 因为它在 \(a\) 上与 \(g(a)\) 的每个集合 \(g(a)\) 都不同.

更详细地说, 假设不是这样, 即 \(A_g\) 在 \(g\) 的值域中, 即:

\[ A_g = g(a_0) \]

对于某个 \(a_0 \in A\). 现在根据 \(A_g\) 的定义,

\[ a \in g(a_0) \iff a \in A_g \iff a \notin g(a) \]

对于所有 \(a \in A\). 现在令 \(a = a_0\) 得出矛盾:

\[ a_0 \in g(a_0) \iff a_0 \notin g(a_0). \]

所以 \(g\) 不是满射, 因为在 \(A\) 的幂集中有一个元素, 特别是集合 \(A_g\), 不在 \(g\) 的值域中.

康托尔定理立即意味着:

推论 8.1.13.

\(\text{pow}(\mathbb{N})\) 是不可数的.

证明

根据引理 8.1.9, \(U\) 是不可数的当且仅当 \(\mathbb{N} \strict U\).

集合的子集与长度为 \(n\) 的比特串 \(\{0,1\}^n\) 之间的双射用于证明定理 4.5.5, 也适用于可数无穷集合的子集与无限比特串 \(\{0,1\}^\omega\) 之间的双射. 即,

\[ \text{pow}(\mathbb{N}) \bij \{0,1\}^\omega. \]

这立即意味着:

推论 8.1.14.

\(\{0,1\}^\omega\) 是不可数的.

更大的无穷

有很多不同大小的无限集合. 例如, 从非负整数的无限集合 \(\mathbb{N}\) 开始, 我们可以构建以下无限序列的集合:

\[ \mathbb{N} \strict \text{pow}(\mathbb{N}) \strict \text{pow}(\text{pow}(\mathbb{N})) \strict \text{pow}(\text{pow}(\text{pow}(\mathbb{N}))) \strict \ldots \]

根据康托尔定理 8.1.12, 这些集合中的每一个都比前一个严格更大. 但不仅如此: 所有集合的并集比序列中的每个集合都大（见问题 8.14）. 通过这种方式, 你可以无限地继续下去, 构建“更大”的无穷.

8.1.4 对角线论证

定理 8.1.12 和类似的证明统称为“对角线论证”, 因为这种证明的更直观的版本是用一个无限的方阵来描述的. 也就是说, 假设 \(\mathbb{N}\) 和 \(\{0, 1\}^\omega\) 之间存在一个双射. 如果这种关系存在, 我们可以将其显示为按某种可数顺序排列的无限比特串列表. 一旦找到一种可行的方式来组织这个列表, \(\{0, 1\}^\omega\) 中的任意字符串将会在有限步内出现, 就像你可以命名的任意整数都会在有限步内从 0 出现一样. 这个假设的列表看起来像下面这样, 垂直和水平都延伸到无穷大:

\[ \begin{matrix} A_0 & = & 1 & 0 & 0 & 0 & 0 & 1 & 1 & \cdots \\ A_1 & = & 0 & 1 & 1 & 1 & 0 & 1 & \cdots \\ A_2 & = & 1 & 1 & 1 & 1 & 1 & \cdots \\ A_3 & = & 0 & 1 & 0 & 0 & 1 & 0 & \cdots \\ A_4 & = & 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ A_5 & = & 1 & 0 & 0 & 1 & 1 & \cdots \\ & \vdots & & \vdots & & \vdots & & \vdots & & \ddots \\ \end{matrix} \]

但现在我们可以展示一个在我们所谓的完整列表中缺失的序列. 看一下我们的样例列表中的对角线:

\[ \begin{matrix} A_0 & = & \color{blue}{1} & 0 & 0 & 0 & 0 & 1 & 1 & \cdots \\ A_1 & = & 0 & \color{blue}{1} & 1 & 1 & 0 & 1 & \cdots \\ A_2 & = & 1 & 1 & \color{blue}{1} & 1 & 1 & \cdots \\ A_3 & = & 0 & 1 & 0 & \color{blue}{0} & 0 & 1 & 0 & \cdots \\ A_4 & = & 0 & 0 & 1 & 0 & \color{blue}{0} & 0 & \cdots \\ A_5 & = & 1 & 0 & 0 & 1 & 1 & \color{blue}{1} & \cdots \\ & \vdots & & \vdots & & \vdots & & \vdots & & \ddots \\ \end{matrix} \]

这就是对角线论证名称的由来: 我们可以形成一个由对角线上比特组成的序列 \(D\).

\[ D = \color{blue}{1} \color{blue}{1} \color{blue}{1} \color{blue}{0} \color{blue}{0} \color{blue}{1} \cdots \]

然后, 我们可以通过将对角线上的 1 和 0 互换来形成另一个序列. 称这个序列为 \(C\):

\[ C = \color{red}{0} \color{red}{0} \color{red}{0} \color{red}{1} \color{red}{1} \color{red}{0} \cdots \]

现在, 如果 \(A_n\) 的第 \(n\) 项是 1, 那么 \(C\) 的第 \(n\) 项是 0, 反之亦然, 这保证了 \(C\) 与 \(A_n\) 不同. 换句话说, \(C\) 至少有一位比我们列表中的每个序列都不同. 所以 \(C\) 是 \(\{0, 1\}^\omega\) 的一个元素, 但它没有出现在我们的列表中——我们的列表不可能完整！

这个对角线序列 \(C\) 对应于定理 8.1.12 证明中的集合 \(\{a \in A \mid a \notin g(a)\}\). 两者都是根据可数子集定义的, 以这种方式将它们排除在该子集之外, 从而证明没有可数子集可以与不可数集合一样大.

8.2 停机问题

尽管越来越大的无限集合对计算机科学家来说顶多听起来很浪漫, 但推出的这些结论的推理在计算理论中起着至关重要的作用. 对角线论证用于证明许多问题无法通过计算解决, 而且这是无法绕过的.

这个故事开始时提醒我们, 程序操作程序是计算机科学技术的基本部分. 例如, 编译（compilation）指的是将用某种“高级”编程语言（如 Java、C++、Python 等）编写的任何给定程序文本, 生成一组低级指令, 该指令执行相同的任务, 但针对可用硬件进行优化. 同样, 解释器（interpreters）或虚拟机（virtual machines）是将设计用于在一种计算机上运行的程序文本并在另一种计算机上模拟它的程序. 编译器的常规功能包括“类型检查”（type-checking）程序, 以确保不会发生某些类型的运行时错误, 并“优化”生成的程序, 使它们运行得更快或使用更少的内存.

根本无法通过计算完成的基本任务是对程序进行完美的类型检查、优化或任何形式的整体运行时行为分析. 在本节中, 我们将通过一个称为停机问题（Halting Problem）的基本示例来说明这一点. 选择你喜欢的编程语言——Python、Java、C++ 等——并假设“程序”指的是用你的语言编写的程序.

一旦程序开始运行, 如果其初始计算因某种原因停止——例如产生一个最终值、等待输入、遇到错误中断或简单地冻结——该程序被称为停机（halt）. 因此, 不停机的程序将无限期运行, 占用周期和能量（除非它被外部操作系统命令中断）. 停机问题是确定给定任意程序, 程序是否停机的总体问题.

有一种简单的方法可以确定任意程序是否停机, 至少在理论上: 只需运行它直到停止. 好吧, 不完全是. 以通常的方式运行程序不会检测到它在没有警告的情况下冻结. 真正需要做的是使用解释器或虚拟机模拟程序, 该解释器或虚拟机会识别任何类型的停机, 包括冻结. 但是能够模拟任何程序的解释器和虚拟机是熟悉的技术. 因此, 有一种通用方法可以检测程序何时停机.

困难在于确定程序何时不停机. 在模拟程序时, 你通常不知道是否应该继续模拟, 因为程序稍后可能会停机, 或者是否应该中止模拟, 因为它不会停止.

那么, 有没有其他方法可以检测程序何时不停机？是否有某种程序分析工具可以检查任何程序并正确报告程序何时不停机？答案是: “不可能.”使用标准的对角线论证, 我们将证明拥有这样的不停机分析工具是不可能的. 任何检测不停机的方法都将出错. 它要么错误地报告某些停机程序没有停机, 要么无法报告任何程序的情况. 也就是说, 将会有一个程序, 分析器在该程序上永远运行而不停机.

为了建立对角线论证, 我们将关注字符串程序（string procedures）. 字符串程序是指接受单个参数（假设是ASCII字母表列出来构成的字符串）并返回布尔值的程序. 为了设置停机问题的对角线论证, 考虑如何编写字符串程序, 该程序在应用于双字母字符串时停机, 双字母字符串中的每个字符恰好连续出现两次. 例如, aaCC33 和 zz++ccBB 是双字母字符串, 而 aa;bb ,bbb33和 AAAA 不是. 我们把双字母字符串构成的集合称为ASCII\(^*\) .

当字符串程序在字符串上计算停机时, 该程序被认为“识别”该字符串. 在这种情况下, 一组字符串通常称为（正式的）语言（language）. 我们令 \(\text{lang}(P)\) 表示由程序 \(P\) 识别的语言:

\[ \text{lang}(P) := \{s \in \text{ASCII}^* \mid P \text{ applied to } s \text{ halts}\}. \]

当集合等于 \(\text{lang}(P)\) 时, 该集合被称为可识别的（recognizable）. 例如, 我们已经同意双字母字符串集是可识别的.

假设每个程序都可以写成 ASCII\(^*\) 中的字符串是没有害处的——这通常是我们最初将它们输入计算机的方式. 当字符串 \(s \in \text{ASCII}^*\) 实际上是某些字符串程序的 ASCII 描述时, 我们将其称为字符串程序 \(P_s\). 你可以将 \(P_s\) 视为将 \(s\) 编译为可执行程序的结果. 技术上有助于将 ASCII\(^*\) 中的每个字符串视为字符串程序的程序. 因此, 当字符串 \(s \in \text{ASCII}^*\) 无法解析为正确的字符串程序时, 我们将 \(P_s\) 定义为某些默认字符串程序——例如, 从不在任何应用上停机的程序.

仅仅关注字符串程序, 广义的停机问题是确定给定字符串 \(s\) 和 \(t\), 程序 \(P_s\) 是否识别 \(t\). 遵循通常的对角线方法, 我们定义语言不停机(No-halt):

定义 8.2.1.

\[ \text{No-halt} ::= \{s \mid P_s \text{ 应用于 } s \text{ 不停机}\} = \{s \mid s \notin \text{lang}(P_s)\}. \tag{8.3} \]

所以如果 \(P_s\) 是某种语言的识别器, 那么 No-halt 与该语言在字符串 \(s\) 上不同. 这表明 No-halt 无法有识别器:

定理 8.2.2.

No-halt 是不可识别的.

让我们更充分地解释一下这一定理背后的推理. 根据定义, 我们有:

\[ s \in \text{No-halt} \iff s \notin \text{lang}(P_s). \tag{8.4} \]

现在假设相反, No-halt 是可识别的. 这意味着存在某个程序 \(P_{s_0}\) 识别 No-halt, 即,

\[ \text{No-halt} = \text{lang}(P_{s_0}). \]

结合 (8.4), 我们有:

\[ s \in \text{lang}(P_{s_0}) \iff s \notin \text{lang}(P_s) \tag{8.5} \]

对于所有 \(s \in \text{ASCII}^*\). 现在让 \(s = s_0\) 在 (8.5) 中, 立即得到矛盾:

\[ s_0 \in \text{lang}(P_{s_0}) \iff s_0 \notin \text{lang}(P_{s_0}). \]

所以这就结束了: 上述推理适用于你选择的任何喜欢的编程语言. 对于 Java 程序来说, 不可能存在识别非停机 Java 程序的 Java 程序；对于 Python 程序来说, 不可能存在识别非停机 Python 程序的 Python 程序；对于其他喜欢的编程语言也是如此.

现在你可能会想, 是否存在通过在另一种语言中编写识别非停机程序的识别器来绕过这种逻辑限制的漏洞. 换句话说, 是否存在识别所有非停机 Java 程序的 C++ 程序？毕竟, C++ 确实允许比 Java 更加亲密地操作计算机内存. 但这里没有漏洞. 如果你学过编程语言实现, 你会意识到可以编写 Java 模拟器来运行 C++ 程序. 这意味着, 如果存在识别非停机 Java 程序的 C++ 程序, 那么 Java 程序也可以通过模拟 C++ 程序来做到这一点, 这是不可能的. 这种推理最终导致一个超然的见解. 没有任何程序可以编写在任何编程语言中识别你喜欢的语言中的 No-halt. 识别 No-halt 超出了计算能力.

但不仅仅是 No-halt. 如果存在某种性质的完美识别器, 它依赖于程序的完整运行时行为, 它可能会被改变为 No-halt 的识别器. 我们将把这个作为一个既定事实, 给出其在指定问题中的充分证明.

例如, 大多数编译器在编译时进行“静态”类型检查, 以确保程序不会产生运行时类型错误. 程序的类型检查意味着没有类型错误. 然而, 如果类型检查器认为没有类型错误, 它必须拒绝实际上不会导致类型错误的程序. 结论是没有类型检查器是完美的——你总是可以做得更好！

如果我们考虑编写程序分析器的实际可能性, 这又是另一个故事. 逻辑上无法分析完全任意的程序并不意味着你不能在实际中做非常好的工作来分析有趣的程序. 事实上, 这些“有趣的”程序通常有意被设计成可分析的, 以确认它们确实做了预期的事情.

最终, 这一理论限制在实践中意味着多大的障碍还不清楚. 但理论确实为关于程序的一般分析方法的声明提供了一些视角. 理论告诉我们, 提出此类声明的人要么:

夸大了他们方法的能力（如果有的话）, 可能是为了销售或获得资助,
尝试保持简单而不涉及他们知道的技术限制,
或者最常见的是, 对他们方法的一些有用实际成功如此兴奋, 以至于没有费心去考虑必须存在的限制.

因此, 从现在开始, 如果你听到人们声称拥有通用程序分析/验证/优化方法, 你会知道他们不可能在讲述整个故事.

8.3 集合逻辑

8.3.1 罗素悖论

朴素的集合结果是有风险的. 事实上, 十九世纪末逻辑学家哥特洛布·弗雷格尝试为集合提出精确公理的最早尝试之一, 被一个称为罗素悖论的三行论证击败, 该论证与康托尔定理 8.1.12 的证明几乎以同样的方式进行:

罗素悖论

设 \(S\) 是在所有集合中变动的变量, 定义

\[ W ::= \{S \mid S \notin S\}. \]

因此, 根据定义, 对于每个集合 \(S\),

\[ S \in W \iff S \notin S. \]

特别地, 我们可以让 \(S\) 等于 \(W\), 并得到矛盾结果

\[ W \in W \iff W \notin W. \]

简单的集合推理崩溃了数学！罗素和他的同事怀特黑德花了多年时间试图开发一个不矛盾的集合论, 但仍能作为所有数学的坚实逻辑基础.

实际上, 摆脱悖论的方法对罗素和其他人来说是显而易见的: 假设 \(W\) 是一个集合是不合理的. 证明中的这一步骤（我们让 \(S\) 为 \(W\)）没有正当理由, 因为 \(S\) 在集合中变动, 而 \(W\) 可能不是一个集合. 事实上, 悖论暗示 \(W\) 最好不要是一个集合！

但否定 \(W\) 是一个集合意味着我们必须拒绝一个非常自然的公理: 每个数学上定义良好的集合实际上是一个集合. 弗雷格、罗素和他们的逻辑学家同事面临的问题是如何指定哪些定义良好的集合是集合. 罗素和他的剑桥大学同事怀特黑德立即开始研究这个问题. 他们花了十二年时间开发了一个巨大的新公理系统, 并在更大的专著《数学原理》中进行了描述, 但实际上他们的方法失败了. 它太繁琐了, 没有人使用它, 并且被一个更简单、现在广泛接受的集合论公理化体系取代了, 由泽尔梅洛和弗兰克尔逻辑学家提出.

8.3.2 ZFC 集合公理

一个集合论公式是一个仅谈论集合成员资格的谓词公式. 也就是说, 集合论的一阶公式仅由逻辑连接词和量词构建, 完全从形式“\(x \in y\)”的表达式开始. 论域是集合的集合, “\(x \in y\)” 被解释为 \(x\) 和 \(y\) 是在集合范围内的变量, \(x\) 是 \(y\) 的一个元素.

集合论的公式甚至不允许有等号符号“=”, 但集合当且仅当它们具有相同的元素时才相等, 因此有一种简单的方法可以仅根据成员资格来表示集合的相等性:

\[ (x = y) ::= \forall z. (z \in x \iff z \in y). \tag{8.6} \]

类似地, 子集符号“\(\subseteq\)”在集合论的公式中不允许, 但我们也可以仅根据成员资格来表达子集:

\[ (x \subseteq y) ::= \forall z. (z \in x \implies z \in y). \tag{8.7} \]

因此, 使用符号“=, \(\subseteq\)”的公式, 除了使用“\(\in\)”外, 可以理解为仅使用“\(\in\)”的公式的简写. 我们不必担心公式与公式缩写之间的区别——我们现在将它们统称为“集合论公式”. 例如,

\[ x = y \iff [x \subseteq y \text{ 且 } y \subseteq x] \]

是一个集合论公式, 它解释了集合相等与集合包含之间的基本连接.

通常认为, 基本上所有数学都可以从称为选择公理的 Zermelo-Fraenkel 集合论公理（ZFC）的一些集合论公式推导出来, 使用一些简单的逻辑推理规则.

我们不会在本文中研究 ZFC 的公理, 但我们认为你可能希望看到它们——同时也进行一些练习, 阅读和书写量化公式:

外延性（Extensionality）. 两个集合在且仅在它们是相同集合的成员时相等:

\[ x = y \iff (\forall z. x \in z \iff y \in z). \]

配对（Pairing）. 对于任意两个集合 \(x\) 和 \(y\), 有一个集合 \(\{x, y\}\) 以 \(x\) 和 \(y\) 作为其唯一元素:

\[ \forall x, y \exists u \forall z. [z \in u \iff (z = x \text{ 或 } z = y)]. \]

并集（Union）. 一个集合的集合的并集也是一个集合:

\[ \forall z \exists u \forall x. (x \in u \iff \exists y. x \in y \text{ 且 } y \in z) \]

无穷（Infinity）. 存在一个无限集合. 具体来说, 存在一个非空集合 \(x\), 使得对于 \(x\) 中的任意元素 \(y\), 集合 \(\{y\}\) 也是 \(x\) 的一个元素:

子集（Subset）. 给定任意集合 \(x\) 和任意可定义的集合属性, 有一个集合 \(y\) 精确包含 \(x\) 中具有该属性的那些元素.

\[ \forall x \exists y \forall z. (z \in y \iff [z \in x \text{ 且 } \phi(z)]). \]

其中 \(\phi(z)\) 是一个集合论公式.

幂集（Power Set）. 所有子集形成另一个集合:

\[ \forall x \exists p \forall u. u \subseteq x \iff u \in p. \]

替换（Replacement）. 假设集合论公式 \(\phi\) 定义了一个集合上的函数的图, 那么该函数下的集合的像也是一个集合.

\[ \forall x \in s \forall y, z. [\phi(x, y) \text{ 且 } \phi(x, z)] \implies y = z. \]

那么该函数下的集合 \(s\) 的像也是集合 \(t\). 即,

\[ \exists t \forall y. y \in t \iff [\exists x \in s. \phi(x, y)]. \]

基础（Foundation）. 目的是禁止形式 \(\cdots \in x_n \in \cdots \in x_1 \in x_0\) 的无限序列, 其中每个集合是下一个集合的一个成员. 这可以通过说每个非空集合都有一个“成员最小”的元素来捕捉. 即, 定义:

\[ \text{member-minimal}(m, x) ::= [m \in x \text{ 且 } \forall y \in x. y \notin m]. \]

那么基础公理是:

\[ \forall x. x \ne \varnothing \implies \exists m. \text{member-minimal}(m, x). \]

选择（Choice）. 设 \(x\) 是非空、不相交集合的集合. 则存在一个集合 \(c\), 它由每个集合中的确切一个元素组成. 此公式来自于问题 8.35.

8.3.3 避免罗素悖论

这些现代 ZFC 集合论公理比罗素和怀特黑德最初提出的避免悖论的系统要简单得多. 事实上, ZFC 公理与弗雷格的原始公理一样简单和直观, 只有一个技术性的补充: 基础公理. 基础公理捕捉了集合必须以某些标准方式从“更简单”的集合构建的直观想法. 特别地, 基础公理避免了罗素集合 \(W ::= \{S \mid S \notin S\}\) 的“悖论”, 因为它暗示 \(W\) 不是一个集合. 即, 基础公理暗示 \(S \notin S\) 对于每个集合 \(S\) 成立, 因此 \(W\) 是所有集合的集合. 现在如果 \(W\) 是一个集合, 我们将有 \(W \in W\), 违反了基础公理.

8.4 这些真的有效吗？

这就是主流数学今天所处的境地: 有一小部分 ZFC 公理, 从中几乎可以逻辑地推导出数学中的所有其他内容. 这听起来像是一个美好的局面, 但有几个乌云笼罩, 表明数学中的真理本质并未完全解决.

ZFC 公理不是神所铭刻的. 相反, 它们主要是由泽尔梅洛编造的, 他可能是一位杰出的逻辑学家, 但也是一个可能会忘记家门钥匙的凡人. 也许泽尔梅洛就像弗雷格一样, 没有正确地设置他的公理, 并且会被罗素的某个继任者用他的公理证明命题 \(P\) 及其否定 \(\overline{P}\) 所击败. 那么我们所理解的数学将会崩溃——这可能听起来很疯狂, 但这确实发生过.

实际上, 虽然广泛认为 ZFC 公理能够证明所有标准数学, 但这些公理还有一些更远的后果, 听起来像是悖论. 例如, Banach-Tarski 定理表明, 作为选择公理的结果, 一个实心球可以被分成六个部分, 然后这些部分可以被严格重新排列成两个与原球大小相同的实心球！

关于这些公理的一些基本问题仍未解决. 例如, 康托尔提出的连续统假设（Continuum Hypothesis）询问是否存在一个集合, 其大小严格介于自然数的无限集合 \(\mathbb{N}\) 和严格更大的幂集 \(\text{pow}(\mathbb{N})\) 之间？康托尔未能解决:

康托尔的连续统假设: 不存在一个集合 \(A\) 使得

\[ \mathbb{N} \strict A \strict \text{pow}(\mathbb{N}). \]

连续统假设在一个世纪后仍然是一个未解问题. 其难度源于现代集合论中最深刻的结果之一——部分由哥德尔在1930年代和保罗·科恩在1960年代发现. 也就是说, ZFC 公理不足以解决连续统假设: 有两个集合集合, 每个都遵守 ZFC 的法则, 一个集合中连续统假设为真, 另一个集合中为假. 直到具有深刻集合理解的数学家能够用具有说服力的新公理扩展 ZFC, 连续统假设将保持未决.

但即使我们使用更多或不同的集合公理, 仍然存在一些不可避免的问题. 在1930年代, 哥德尔证明了, 假设像 ZFC 这样的公理系统是一致的——意味着你不能证明命题 \(P\) 及其否定 \(\overline{P}\)——那么系统一致性的命题本身（用逻辑公式表达并不难）不能在系统中得到证明. 换句话说, 没有一致的系统足够强大到能够验证自身.

8.4.1 计算机科学中的大无穷

如果不同大小的无穷和连续统假设的浪漫吸引力对你没有吸引力, 不了解它们不会限制你作为计算机科学家的发展. 这些关于无限集合的抽象问题很少出现在主流数学中, 它们根本不会出现在计算机科学中, 因为计算机科学主要关注“可数的”, 甚至只是有限的集合. 实际上, 只有逻辑学家和集合论学家才需要担心“太大”而无法成为集合的集合. 这就是为什么十九世纪数学界会拿康托尔的“乐园”中的晦涩无穷开玩笑. 但正确理解这一远离现实的东西直接导致了关于计算的逻辑极限的深刻发现, 如第 8.2 节所述, 这确实是每个计算机科学家都应该理解的.