认识论概要/数学基础

数学可以被定义为对所有逻辑上可能的事物的科学，包括所有存在和所有可以在理论中研究的概念。对于一个数学存在来说，只要一个理论正确地确定了它的存在，就足以证明它的存在，而不需要它在有形的和可观察的现实中存在。

一阶逻辑提供了建立理论的手段，这些理论将有限数量的基本概念应用于一个域，这个域可以是有限的，也可以是无限的。为了用一阶逻辑原理推理关于可以应用于指定域的个体的所有概念，只需要将概念（属性和关系）视为新的个体，并给自己一个新的归属关系，该关系将属性（关系）与它们所归属的个体（个体的n元组）相关联。因此，我们可以建立二阶逻辑和更高阶逻辑。集合论是一种更简单的方法，可以在一阶逻辑框架内建立对所有逻辑上可能事物进行理论化的理论。由于这对初学者来说有点混乱，本章首先概述了一种更自然的方法来奠定数学基础，从自然数理论开始。

自然数和皮亚诺公理

戴德金 (1888) 和皮亚诺 (1889) 给出了足够证明其大部分定理的公理系统。皮亚诺算术可以被认为是最基本的数学理论。并且它足以证明大部分最重要的定理，甚至包括微积分中的定理，因为关于实数的定理可以转化为关于自然数的定理。

在目前的形式化中，所有自然数都从0和一个单一的运算符s（后继）开始命名

1=s0, 2=s1=ss0, 3=sss0, ...

皮亚诺公理:

0 是一个自然数。
一个自然数 n 总是有一个唯一的后继 sn，它也是一个自然数。
两个不同的自然数有不同的后继。
0 不是任何自然数的后继。

对于所有自然数 n 和 p

它们的和 n + p 存在且是唯一的，同样对于它们的唯一乘积 n.p
0 + 0 = 0
n + sp = sn + p = s (n + p)
0.0 = 0
n.sp = n.p + n
sn.p = n.p + p

无穷归纳原理

任何包含 0 并且始终包含其每个元素的后继的自然数集合都包含所有自然数。

为了进行算术，我们需要对自然数集合进行推理。因此，我们可以考虑用关于数字集合存在的公理来补充皮亚诺公理，但这并不是必需的。具有一个自由变量的算术公式足以命名数字集合。例如，由“存在 p 使得 n = 2.p”定义的公式 A(n) 命名了所有偶数的集合。用这样的算术公式，我们可以定义许多自然数集合，这对于大多数理论目的来说已经足够了，但不是全部。

皮亚诺算术既简单又非常强大。通过对数字进行推理，我们可以对所有可以计数的存在集合进行推理。当我们研究一个逻辑上可能的世界时，其个体是如何被识别的并不重要。它们是被编号还是以其他方式表示，都不会改变所研究的逻辑上可能的世界。重要的是对个体赋予的概念（属性和关系），而不是个体是如何被识别的。这就是为什么皮亚诺算术非常强大。它提供了对许多逻辑上可能的世界进行推理的手段。

策梅洛集合论

集合论使得能够对所有概念进行理论化，因为一个概念可以通过它的外延来表示，即对它为真的存在集合。偶数的概念可以由偶数的集合来表示。数字之间的大于关系可以用所有 (x, y) 数字对的集合来表示，其中 x 大于 y 。

为了建立集合论，最自然的方法是从不是集合的存在开始，例如自然数，或者其他存在，我们将其作为我们定义的集合的元素。

纯粹的集合论只研究集合。该理论假设存在的任何存在始终是集合。这对初学者来说有点混乱。我们如何从头开始建立集合？我们从空集 {} 开始，它不包含任何元素。然后，我们可以定义新的集合：{{}}, {{}, {{}}} ...

自然数可以用集合来表示。例如，我们可以将 0 识别为空集 {}，将 1 识别为 {0}，将 2 识别为 {0,1}，更一般地，将 n 识别为 {0 ... n-1}。所有其他数字都可以从自然数构建出来。

为了研究逻辑上可能的世界，个体是如何被识别的并不重要。它们可以用数字、数字系统或集合来表示。一个逻辑上可能的世界不是由其个体是如何被识别的来决定的，而是由它赋予它们的属性和关系来决定的。这就是为什么纯粹的集合论能够建立对所有逻辑上可能事物进行理论化的理论。

一个函数（一个运算符）f 可以用一个关系来表示：y=f(x)，或者 z=f(x,y) ...

一个关系可以用一对、三元组或 n 元组的集合来表示。

一对 (x,y) 可以用一个集合来表示，例如 {{x}, {x,y}}。一个三元组可以从对中表示：例如，(x,y,z) = ((x,y),z)。对于所有 n 元组也是如此。

由于纯粹的集合论提供了表示所有个体、所有属性、所有关系、所有函数的手段，因此它提供了对所有逻辑上可能事物进行推理的手段。

为了证明所有自然数的存在，只需要假设 0 是一个自然数，并且自然数的后继总是自然数。为了证明集合的存在，我们以类似的方式进行，我们从空集 {} 开始，并证明从我们已经证明存在的集合构建的新集合的存在。

策梅洛公理 (1908)

外延公理： 两个集合在它们具有相同元素时相等。
空集公理： 存在一个空集。
对公理： 如果两个集合存在，那么存在一个集合，它们是唯一的两个元素。
和集公理： 如果一个集合存在，那么其所有元素的元素的集合也存在。
无穷公理： 存在一个包含所有自然数的集合。
分离公理： 如果 E 是一个集合，并且 A(x) 是关于集合的定义明确的公式，那么 E 中所有使 A(x) 为真的 x 的集合存在。
幂集公理： 如果一个集合存在，那么它的所有部分或子集的集合也存在。
选择公理：将在下面介绍。

第一个公理是集合的本质特征。如果两个存在体在它们具有完全相同的元素时是不同的，那么它们就不是集合。

接下来的三个公理使得构造自然数成为可能。两个集合的并集是它们对的和集。集合 *x* 的后继是并集 *x U {x}*。然后我们定义：*0 = {}*，*1 = 0 U {0} = {0}*，*2 = 1 U {1} = {0,1}* ...

第五和第六公理证明了自然数集 *N* 的存在。这个集合包含所有自然数，并且被包含在包含所有自然数的所有集合中。因此，我们发现数学归纳原理是自然数集定义的结果。

由此，第七公理使得构建第一个无限集的层次结构成为可能：*N*，*N* 的所有子集的集合 *P(N)*，*P(P(N)) = P²(N)*，*P(P(P(N))) = P³(N)* ...

分离公理可以比作雕刻家的凿子。我们通过给自己提供大型集合，就像大型大理石块，然后用凿子，也就是分离公理，来切割它们，从而构建集合。

为了用一阶逻辑的方式表达这些公理，我们只需给自己两个基本关系，属于一个集合的关系，*是...的元素*，以及等于的关系 =，并假定所有个体的域是所有集合的域（或我们感兴趣的所有集合）。

**外延公理**: *对于所有 x 和所有 y，x = y 当且仅当对于所有 z（z 是 x 的元素当且仅当 z 是 y 的元素）*
**空集公理**: *存在 x 使得对于所有 y，y 不是 x 的元素*
**对公理**: *对于所有 x 和所有 y 存在 z 使得对于所有 w（w 是 z 的元素当且仅当 (w = x 或 w = y)）*
**和集公理**: *对于所有 x 存在 y 使得对于所有 z（z 是 y 的元素当且仅当 (存在 w 使得 (w 是 x 的元素并且 z 是 w 的元素)）*

为了表达无穷公理，我们首先定义集合之间的后继关系：*y 是 x 的后继当且仅当 y = xU {x}*

y = xU {x} 当且仅当对于所有 z（z 是 y 的元素当且仅当 (z 是 x 的元素或 z = x)）

对于任何集合 x，x 的后继的存在性由对公理和和公理保证。

**无穷公理**: *存在 x 使得 ({} 是 x 的元素并且对于所有 y，如果 y 是 x 的元素那么 yU {y} 是 x 的元素)*
**分离公理**: *对于任何定义良好的公式 A(x) 和所有 y 存在 z 使得对于所有 w（w 是 z 的元素当且仅当 (A(w) 并且 w 是 y 的元素)）*

为了表达幂集公理，我们首先定义集合之间的包含关系：*x 包含于 y，或者 x 是 y 的一部分，或者 y 的子集，当且仅当 x 的任何元素也是 y 的元素。*

x 包含于 y 当且仅当对于所有 z，如果 z 是 x 的元素那么 z 是 y 的元素

**幂集公理**: *对于所有 x 存在 y 使得对于所有 z（z 是 y 的元素当且仅当 z 包含于 x）*

这些公理并不能定义所有集合。特别是，集合 *{N, P(N), P(P(N)) ...}* 的存在，它包含所有 *Pⁿ(N)* 对于所有自然数 *n*，无法从 Zermelo 公理证明。它可以用一个新的公理，由 Fraenkel (1922) 提出的替换公理来证明，这个公理更强大，可以用来证明大型无限集合的存在。但即使有了这个新的公理，仍然有一些集合是该理论无法定义的。

对于普通数学，甚至对于非常高级的数学，Zermelo 理论足以构建我们想要构建的所有集合，并证明我们想要证明的所有内容。特别是，实数、从实数构造的空间、在其中定义的函数、这些函数的空间、函数的函数，以及因此微积分的所有对象，都可以通过限制自己到无限集层次结构的前几级来构造。Zermelo 理论不允许构造的较大无限集使用得少得多。

分离公理的解释带来一个困难。什么是定义良好的公式？根据 Fraenkel，任何从基本谓词 *是...的元素* 和 *等于*，以及逻辑连接词形成的良好格式的公式，都是定义良好的公式。分离公理总是可以应用于它们。但 Zermelo 并不认可这种方法，因为这些所谓的明智公式可能包含对所有集合的断言，就好像所有集合的宇宙具有客观存在一样。但我们不知道这样的宇宙是什么。因此，我们并不总是知道对用于在 ZFC 中定义集合的公式赋予什么意义。这个理论导致证明了存在非良好定义的集合。然而，非良好定义的集合不是集合，它不存在。所以 ZFC 是假的。

要纠正 Fraenkel 的错误，只需要求分离公理应用于定义良好的公式，它们只包含有界量词，也就是说它们不包含关于所有集合的陈述，而只包含关于已经定义集合的所有元素的陈述。有了这些限制，并且没有替换公理，我们拥有了当前数学所需的足够力量。

选择公理

证明一个集合存在的最直接方法是定义它，这相当于从已经定义的集合中构造它。空集足以开始构建我们定义的所有集合。但我们也可以间接地证明存在。我们证明一个集合存在并具有一定的性质，而没有明确地定义它，没有构造它，没有准确地说我们谈论的是哪个集合。

存在性的间接证明使我们能够证明，为了证明一个集合的存在，人们总是可以进行有限次数的任意选择。更准确地说，如果有一份非空且不相交集合的有限列表，那么可以证明，存在至少一个集合，它包含每个列表集合中的一个且只有一个元素。我们没有构建这个新的集合，我们没有选择它的元素，我们只是证明了它存在。有限集合的逻辑原理和构造公理足以证明它的存在。但如果非空且不相交集合的列表是无限的，那么这些原理和公理就不能证明存在一个集合，它包含每个列表集合中的一个且只有一个元素。选择公理明确地说明了这样的集合存在（Zermelo 1904）

**选择公理**: *如果 E 是一个非空且不相交集合的集合，那么存在一个集合，它包含 E 的每个元素中的一个且只有一个元素。*

罗素悖论

除了 Zermelo 的分离公理，我们本可以想到一个更简单的公理

**弗雷格公理**: *如果 A(x) 是一个明智的公式，那么所有使得 A(x) 为真的 x 的集合存在。*

这个公理是由弗雷格 (1879) 提出的，用来奠定所有数学的基础，但罗素 (1901，出版于 1903) 意识到它导致了矛盾。*x 不是 x 的元素* 是一个明智的公式。一般来说，集合不是自身的元素，但可能存在例外，比如所有集合的集合。*所有使得 x 不是 x 的元素的 x 的集合*，所有不是自身元素的集合的集合，如果我们采用弗雷格公理，则存在。它是否为自身的元素？从它的定义可以得出，它是一个元素当且仅当它不是自身的元素。这是荒谬的，所以这个集合不能存在，所以弗雷格公理是假的。

Zermelo 理论使得定义非常大的集合成为可能，但仍然不能定义所有集合的集合。否则，分离公理将使得定义所有不是自身元素的集合的集合成为可能，并且该理论将是矛盾的。我们将在后面展示它确实是正确的，因此是自洽的。因此，它不允许构建会导致矛盾的悖论集合。

一般来说，集合论不允许我们定义它允许定义的所有集合的集合。否则，这个集合将是自身的元素，并且有了分离公理，该理论将是矛盾的，因为在该理论中定义的所有不是自身元素的集合的集合将在该理论中是可定义的。如果该理论是定义良好的，那么在该理论中定义的所有集合的集合也是定义良好的，但它在该理论中是不可定义的。这是数学基础不完备性的原因之一。

在 Zermelo 理论中定义的所有集合的集合在 Zermelo 理论中是不可定义的，但它在一个更强大的理论中是可定义的。例如，替换公理提供了定义它的方法。

不可数无限

当我们能够用自然数 0, 1, 2, 3, 4... 对集合中的所有元素进行编号时，该集合就是可数的。可数集合可以是有限的或无限的。所有自然数的集合是无限的且可数的。康托尔 (1874) 证明存在更大的无限集合。特别是，自然数集合的集合不可数。

这是通过归谬法证明的。假设自然数集合的集合是可数的。这意味着它们都可以用一个数字来标识。然后让我们定义集合 C ，该集合包含不在其编号的集合中的数字，并让 n 为 C 的编号。但如果 n 不在 C 中，那么根据 C 的定义，它就在 C 中。因此它必须在 C 中。但这样一来，根据 C 的定义，它就不在 C 中了。n 在 C 中当且仅当它不在 C 中。这是个矛盾。因此集合 C 不可能存在。因此，自然数集合的集合不可数。

由一个理论定义和命名的存在物的集合总是可数的，因为我们使用有限的字母表来定义和命名。总能对从有限字母表中形成的单词进行编号。只需按长度排序，然后按字母顺序排列相同长度的单词即可。单词的编号就是其序列号。

不可数性是数学基础不完备性的原因之一。一个理论只能定义可数的集合，因此它永远无法定义不可数集合中的所有元素，它永远无法提供完全填充不可数集合的手段。

当从一个集合到另一个集合存在双射时，这两个集合具有相同的基数。这意味着我们可以用另一个集合的元素识别一个集合中的所有元素。从 E 到 F 的双射是一个函数，该函数的定义域是 E，并且每个 F 元素都有唯一的先行元素。因此，具有相同基数的两个有限集合必然具有相同数量的元素。基数的概念将元素数量的概念推广到无限集合。两个集合，无论是有限的还是无限的，只有当且仅当它们具有相同数量的元素时，它们才具有相同的基数。根据这个定义，康托尔创立了无穷数理论。

当一个集合与自然数集合具有相同的基数时，该集合是可数无限的。

康托尔证明了一个集合不能与其所有部分的集合具有相同的基数。他得出结论，存在许多无穷数，而不仅仅是自然数的数目。

良序集和无穷归纳法

良序集的概念使我们能够指定一个过程的概念，在这个过程中，每一步都在前一步完成之后确定。当这样的过程是有限的时，它的每一步都可以用从 1 到 n 的自然数进行编号。当一个过程是无限的时，它的每一步都可以用良序集中的一个元素来标识。

一个集合 E 是全序的，当且仅当存在一个关系 <，使得对于 E 中的所有 x，y 和 z，

如果 (x<y 且 y<z) 那么 x<z
如果 x<y 那么不成立 y<x
x<y 或 y<x 或 x=y

为了使一个逐步过程能够确定，剩余步骤中的第一个步骤必须始终确定。因此，我们要求步骤的顺序，以便后续步骤的集合始终具有第一个元素（或最小元素）。这导致对 E 上的顺序关系强加以下属性

如果 E 的任何部分的严格上界的集合不为空，则该集合具有第一个元素。

(x 是 y 的严格上界当且仅当 x 严格大于（或在）y 的所有元素。）

可以证明，如果 E 是一个全序集，则这个严格上界属性等价于以下属性

E 的任何非空部分都具有第一个元素。

一个集合是良序的，当且仅当（它是全序的，并且它的每个非空部分都具有第一个元素）。

自然数集是其自然顺序关系最小的良序无限集。更大的良序集可以简单地通过在无限步骤序列之后添加步骤来定义。

无穷归纳原理可以推广到所有良序集

如果 x 是一个包含良序集 y 的第一个元素的集合，并且当 x 包含 y 中所有严格在 z 之前的元素时，x 始终包含 y 中的元素 z，那么 x 包含 y 中的所有元素。

这是通过归谬法证明的：如果 y 中所有不在 x 中的元素的集合不为空，则该集合具有第一个元素。这个第一个元素的存在与关于 x 的一个或多个条件相矛盾。因此，y 中所有不在 x 中的元素的集合为空。

两个良序集 E 和 F 代表相同的序数，当且仅当它们是同构的。这意味着存在从 E 到 F 的双射 f，使得 x<y 当且仅当 f(x)<f(y)。

与基数一样，序数也可以被认为是数字，可以是有限的也可以是无限的。但是序数的算术比基数的算术更精细，因为两个良序无限集可以具有相同的基数，但代表非常不同的序数。

集合是如何定义良好的？

除了空集之外，纯集合论中的所有集合都是从先前定义的集合中定义的。当集合总是通过遵守以下三个条件来定义时，它们就是定义良好的

对于一个新定义的集合，我们必须能够给出集合的良序列表，可以是有限的也可以是无限的，使得列表中的每个集合都是从先前定义的集合中定义的。列表中的第一个项目始终为空集。列表中的最后一个项目是新定义的集合。
新定义集合的元素必须始终是先前定义的集合或先前定义集合的一部分。
属于新定义集合的原子真理必须由集合的定义以及属于先前定义集合及其部分的原子真理决定。

我们可以考虑一个更严格的条件来代替第二个条件：新定义集合的元素必须是先前定义的集合。但这个条件可能会禁止定义无限集合的全部部分集合，因为它不可数。由于一个定义良好的集合的全部部分集合本身就是定义良好的，因此必须承认，一个定义良好的集合的元素可以是尚未先前定义的集合。

弗雷格的公理不符合第二个条件，因为新定义集合的元素不一定是先前定义的集合或此类集合的一部分。

在弗兰克尔的公式 (ZFC) 中，分离公理不符合第三个条件，因为使用无界量词意味着属于新定义集合的原子真理是由属于所有集合的所有原子真理决定的，而不仅仅是由属于先前定义集合的原子真理决定的。为了满足第三个条件，用于定义集合的所有量词必须受先前定义的集合约束。

策梅洛提出的所有集合构造公理都符合这三个条件，前提是在使用分离公理构造的集合的定义中，量词是有限制的。

在策梅洛的理论中，可定义的集合是什么？

我们可以从一个初始数字零和一个数字构造函数 the successor of 中定义所有自然数。同样，我们可以从初始集合和集合构造函数中定义策梅洛理论中的所有可定义集合。初始集合是空集和所有自然数的集合。基本构造函数是 the pair of、the sum-set of、the set of parts of 以及所有可以用分离公理定义的无限数量的构造函数，前提是量词在集合的定义中是有限制的。构造函数是基本构造函数的所有有限组合。策梅洛理论中的可定义集合是所有通过将这些构造函数之一应用于空集和所有自然数的集合而获得的集合。

置换公理

如果 R 是集合之间定义良好的函数关系，并且 E 是一个集合，那么我们可以将 E 中的所有元素替换为它们的函数图像，从而得到一个集合。更准确地说，存在一个集合，其中包含所有满足存在 E 中的 x 使得 Rxy 的 y，并且只有这些 y。

一个关系是函数关系，当且仅当它始终将单个元素与同一个元素关联起来：对于所有 x，y 和 z，如果 Rxy 且 Rxz，那么 y=z

弗兰克尔公理的解释提出一个难题：何时函数关系是定义良好的？

在 ZFC 理论中，弗兰克尔允许使用无界量词定义的函数关系，因此是定义不当的函数关系。在弗兰克尔的版本中，置换公理因此是错误的。为了正确应用弗兰克尔的公理，我们需要一个定义良好的函数关系理论。

一个定义良好的集合理论

策梅洛理论是一个关于定义良好的集合的理论，前提是在用分离公理构造集合的定义中强制使用有界量词规则。但是，如果我们想发展无限集理论，这就不够。ZFC 更加强大，但它允许定义不明确的构造。

我们可以定义一个比策梅洛理论更强大的理论，该理论只允许使用基本构造函数及其有限组合进行定义良好的构造。

第一类构造函数使用已经构造的集合构造新的集合。策梅洛理论的基本构造函数（对，和集，幂集以及所有可以用分离公理定义的构造函数，前提是所有量词在集合定义中是有界的）是第一类构造函数。第一类构造函数的有限组合也是第一类构造函数。我们引入两个新的基本构造函数：映象集和通过有限次迭代获得的集合，我们将其简称为无限集。它们是第二类构造函数。它们用第一类构造函数构造第一类构造函数。

如果f是一个带有一个参数的第一类构造函数，那么f 的映象集是一个第一类构造函数，对于任何集合x，它构造所有满足以下条件的 y 的集合：存在 x 中的 z 使得 y=f(z)。f 对 x 的无限集是包含以下元素的集合：x, f(x), f(f(x)), f(f(f(x))) ... 对于f 的所有有限次迭代。

一个构造函数f总是可以用一个关系来定义：f(x)=y 或 f(x,y)=z 或 ...

我们将证明本理论中的所有第一类构造函数都可以用纯集合理论中的关系来定义。

{x,y}=z 由以下定义：对于所有 w，w 是 z 的元素当且仅当 (w=x 或 w=y)

y 是 x 的和集 由以下定义：对于所有 z，z 是 y 的元素当且仅当存在 w 使得 (w 是 x 的元素，并且 z 是 w 的元素)。

y 是 x 的幂集 由以下定义：对于所有 z，z 是 y 的元素当且仅当 z 包含在 x 中

令 A(w, y₁ ... y_n) 是一个自由变量为 w, y₁ ... y_n 的语句。我们假设 A(w, y₁ ... y_n) 中的量词总是受 y₁ ... y_n 之一的限制。分离公理断言：对于所有 y₁ ... y_n 和所有 x，存在 z 使得对于所有 w，w 是 z 的元素当且仅当 (w 是 x 的元素，并且 A(w, y₁ ... y_n))。这相当于断言存在一个带 n+1 个参数的构造函数f。f(x, y₁ ... y_n)=z 由以下定义：对于所有 w，w 是 z 的元素当且仅当 (w 是 x 的元素，并且 A(w, y₁ ... y_n))。因此，所有用分离公理定义的构造函数都可以用纯集合理论中的关系来定义。

在理论中可以定义的构造函数组成的构造函数也可以在该理论中定义。例如 g(f(x))=y 可以用以下定义：存在 z 使得 f(x)=z 且 g(z)=y

令f 是一个带有一个参数的第一类构造函数，R 是定义它的关系：Rxy 当且仅当 f(x)=y

y 是 f 对 x 的映象集 由以下定义：对于所有 z (z 是 y 的元素当且仅当存在 w 使得 (w 是 x 的元素，并且 Rwz))

x 对 R (或对f) 封闭由以下定义：对于所有 y 和所有 z，如果 y 是 x 的元素，并且 Ryz，那么 z 是 x 的元素

y 是 f 对 x 的无限集 由以下定义：x 是 y 的元素，并且 y 对 R 关闭，并且对于所有 z，如果 (x 是 z 的元素，并且 z 对 R 关闭)，那么 y 包含在 z 中

我们得出结论，本理论中的所有第一类构造函数都可以用纯集合理论中的关系来定义。

为了建立一个定义良好的集合理论，我们保留了策梅洛的所有公理，除了无穷公理，并添加了两个公理模式：替换公理和广义无穷公理。

替换公理：如果 R 是一个定义带有一个参数的第一类构造函数的关系，那么对于所有 x，存在 y 使得对于所有 z (z 是 y 的元素当且仅当存在 w 使得 (w 是 x 的元素，并且 Rwz))
广义无穷公理：如果 R 是一个定义带有一个参数的第一类构造函数的关系，那么对于所有 x，存在 y 使得 (x 是 y 的元素，并且 y 对 R 关闭，并且对于所有 z，如果 (x 是 z 的元素，并且 z 对 R 关闭)，那么 y 包含在 z 中)

所有第一类构造函数都是通过基本构造函数的有限组合得到的：对，和集，幂集，无限集，映象集以及所有用分离公理定义的构造函数，前提是所有量词在集合定义中是有界的。

该理论中所有可定义集合的集合是通过将所有第一类构造函数应用于空集得到的。

我们可以用一个更强大的无穷公理来丰富这个理论，该公理允许对任何序数进行无限归纳。

一致性证明

当一个理论永远不允许同时证明一个公式及其否定时，它是一致的、非矛盾的或连贯的，否则它是矛盾的、不一致的、荒谬的、不连贯的。

当然，我们希望一个数学理论是一致的。一个不一致的理论不能区分真假。

为了证明一个理论是一致的，最直接的方法就是简单地证明它是真的，也就是说，证明它的所有定理都是真的。一个真实的理论不可能是不一致的，因为如果一个公式是真，那么它的否定就是假，因此不是真的。

为了证明一个理论的所有定理都是真的，只需证明它的所有公理都是真的，因为真公式的逻辑结果总是真的。

一个公式的数学真值总是从一个模型中定义的，一个作为思维存在而存在的理论实体。在数学上是真实的，就是在一个数学模型中是真实的。

为了证明一个理论是一致的，只需要证明它的公理对于一个理论模型是正确的。

皮亚诺公理的真实性

一个理论的模型是通过定义一组原子真值来定义的。一个公式是原子的，当它不包含逻辑连接词时。皮亚诺算术的原子公式是数值表达式之间的等式，以及断言它们是自然数的公式。一个数值表达式是由0、s、+ 和 . 组成的。

例如，ss0 + ss0 = ssss0 (2 + 2 = 4) 是一个原子公式，它是真的。同样，s0 + (ss0.ss00) 是一个自然数 也是真的。

所有真实的数值等式的集合可以用多种方式构建。这有点费力，因为我们必须给自己足够的规则来生成所有这些基本真理，而不遗漏任何一个，但这并不难，因为它是非常基本的。任何计算机都可以轻松地区分真等式和其他等式。显然，这个原子真值集合是存在的。由于一个真实的理论必然是一致的，因此皮亚诺公理的一致性同时得到了证明。

策梅洛公理的模型

我们可以通过将集合的宇宙取为如下定义的集合M来定义策梅洛公理的模型

令S(x) = x U P(x) 是x 和其所有部分的集合的并集。M 是N 与S(N)、S(S(N)) ... 的并集，也就是说，对于任何自然数n，所有Sⁿ(N) 的并集。

让我们证明所有公理对于这个集合的宇宙M 都是正确的。

从M 的定义中，我们可以立即得出空集公理和无穷公理是正确的。

由于Sⁿ(N) 包含在Sⁿ⁺¹(N) 中，如果n <p，那么Sⁿ(N) 包含在S^p(N) 中。

令x 和y 是M 中的两个元素。因此，我们必须有n 和p，使得x 是Sⁿ(N) 的元素，而y 是S^p(N) 的元素。如果n <= p，那么x 和y 都在S^p(N) 中，因此它们的对在S^p+1(N) 中。如果n>=p，那么{x,y} 在Sⁿ⁺¹(N) 中。因此，对公理在M 中是正确的。

让我们用归纳法证明S^p(N) 的元素的元素也是S^p(N) 的元素。该语句对于N = S⁰(N) 是正确的，因为任何自然数n = {0 ... n-1}。由于P(x) 的元素的元素都在x 中，因此如果该语句对于Sⁿ(N) 是正确的，那么该语句对于Sⁿ⁺¹ (N) 也正确，因此该语句对于任何自然数n 都是正确的。

因此，Sⁿ(N) 的元素的和包含在Sⁿ(N) 中，因此是Sⁿ⁺¹(N) 的元素。因此，和公理在M 中是正确的。

由此可见，Sⁿ(N) 中一个元素的所有子集都包含在Sⁿ(N) 中，因此它们都是Sⁿ⁺¹(N) 的元素。所以，Sⁿ(N) 中一个元素的所有子集组成的集合包含在Sⁿ⁺¹(N) 中，因此是Sⁿ⁺²(N) 的一个元素。因此，幂集公理在M 中成立。

由于M 中所有元素的子集都是M 的元素，因此分离公理在M 中必然成立。

如果E 是一个非空且不相交的集合的集合，并且它属于Sⁿ(N)，那么从E 的每个元素中选择一个元素的集合包含在Sⁿ(N) 中，因为E 的元素的元素都在Sⁿ(N) 中，因此它是Sⁿ⁺¹(N) 的一个元素，因此属于M。所以选择公理在M 中成立。

从集合M 的公理的成立情况，我们可以得出结论：策梅洛理论是一致的。然而，这种一致性证明与之前算术一致性的证明之间存在差异。我们没有显式构建原子真命题的集合。我们没有命名模型的所有元素，也没有说明如何为所有这些元素生成真原子公式的集合。我们无法做到这一点，因为集合M 是不可数的。

是否需要得出结论，这种一致性证明毫无价值？不。但这引发了一个疑问。我们能确定我们构建的集合存在吗？谈论甚至无法列出所有元素的集合，是否冒着荒谬的风险？

我们知道不可数集存在，因为我们可以想到它们。没有什么可以阻止我们思考所有自然数集的集合。我们甚至可以在想象中看到它。

无限二叉树是由一个根节点构建的，根节点分为两个分支，一个在左边，另一个在右边，这两个分支又分别分为两个分支，以此类推，无限地进行。从根节点开始并且永不停止的路径定义了一个自然数集。如果在第n 步中路径选择了左边的分支，那么n 是该集合的一部分，但如果路径选择了右边的分支，则不是。因此，无限二叉树的所有路径的集合是所有自然数集的集合的一种表示。现在我们可以通过观察无限二叉树在视野中展开来想象它。我们可以一目了然地看到它所有的路径，并且它们是不可数的。

即使是一条有限长度的直线，它上面也有不可数个点。就像我们可以看到直线和曲面一样，我们也可以看到不可数。

为了使策梅洛公理的相容性证明为假，必须是我们对不可数集的理解是错误的，也就是说，在我们不知情的情况下，对不可数的推理导致了荒谬。但为什么害怕我们会被自己的推理所愚弄呢？当我们推理一个集合的所有子集时，似乎我们并没有犯任何错误，即使它是一个无限集。

为了使策梅洛公理的一致性证明形式化，只需要在策梅洛公理中添加一个对无限公理的扩展：存在一个包含N且当包含x时总是包含x U P(x)的集合。这样我们就得到了一个更强大的理论，可以证明之前理论的一致性。如果我们想证明这个新理论的一致性，只需要给自己一个新的无限公理。存在一个包含M且当包含x时总是包含x U P(x)的集合。因此，我们可以定义一系列越来越强大的理论，使得一个理论的一致性总是可以由下一个理论证明。

集合论没有终极模型。

当我们定义一个集合的集合，使得所有公理在无界量词被解释为该集合的集合的界限量词时为真时，我们就定义了集合论的一个模型。集合的集合在该理论中扮演着所有被研究集合的宇宙的角色。集合论的一个自然模型是取该理论中所有可定义集合的并集（M 是策梅洛理论的一个这样的自然模型）。但这个模型不能是终极模型，因为它不可能定义终极真理。当我们陈述一个关于所有集合的定理时，它的真理超出了关于该理论中所有可定义集合的并集的真理。我们希望它即使对于该理论中不可定义的集合也是真的，因为我们希望它对所有集合都真正成立，只要它们被很好地定义。

要有一个终极模型，必须能够很好地定义所有良好定义的集合的集合，但这是不可能的，因为它将是它自己的元素。

我们可以考虑为集合论定义一个终极模型 $V$ ，如下所示

$V_{0}=\varnothing$ ，其中 $\varnothing$ 是空集 {}。

$V_{\alpha }=\bigcup _{\beta <\alpha }{\mathcal {P}}(V_{\beta })$ 对于每个序数 α，其中 ${\mathcal {P}}(X)\!$ 是 $X$ 的所有子集的集合。

类 $V$ 然后被定义为所有 $V_{\alpha }$ 的并集，对于所有序数 α

$V=\bigcup _{\alpha }V_{\alpha }$

但這個類別並沒有被很好地確定。為了確定它，所有序數的類別必須事先被很好地確定。但是，序數本質上是一個良序集。我們不能從所有序數的類別來定義所有集合的類別，因為第二個是從第一個定義的。

對於數論或其他特定數學實體，公理的真值總是通過參考模型來確立。我們有一個模型作為公理真值的標準。對於集合論，我們無法擁有最終模型，但我們仍然有真值標準。我們證明存在的集合必須要麼是定義明確的，要麼它們的存在必須源於定義明確的集合。在沒有最終模型的情況下，良好定義的要求充當了真值的標準。

基礎的不完備性

庫爾特·哥德爾於 1931 年證明，我們無法明確地給出所有數學原理的完整列表。更準確地說，一個明確的原理列表永遠不足以證明所有數學真理，即使我們將自己限制在關於自然數的真理。這是哥德爾第一個不完備性定理。原理的不完備性是必要的。它不是來自我們的缺乏想像力或工作。數學家能夠給出非常強大的公理列表，這些公理通常足以證明人們想要證明的所有真理。但是這些列表是不完備的，因為它們不足以證明所有數學真理。它們可以通過新的、更強大的公理來豐富，但它們永遠無法被最終完成。總會有一些數學真理是它們無法證明的。

這個不完備性定理有時被誤解為證據，表明存在我們永遠無法知道的真理，存在我們永遠無法回答的明智問題，存在我們永遠無法找到的解決方案。這種解釋是邏輯上的錯誤。哥德爾證明，對於任何由明確的公理列表定義的連貫理論 *T*，至少有一個真理 *V* 是 *T* 無法證明的。但這並不證明存在一個真理 *V* 是任何理論都無法證明的。實際上，當我們發現一個真理 *V* 在一個理論 *T* 中無法證明時，通常很容易定義一個理論 *T+*，將一個新的公理添加到 *T* 中，從而允許證明 *V*。

希爾伯特（1930 年）的原則「我們必須知道，我們將知道」，即使在哥德爾之後仍然成立。沒有任何東西可以說存在我們永遠無法知道的數學真理。

我們第一次聽到哥德爾的不完備性定理時，通常會非常驚訝，因為我們習慣於將數學真理和可證明性等同起來。當我們知道如何證明一個定理時，我們就知道它是真的。但當我們理解一個明確的公理列表不足以證明所有數學實體的存在時，這種驚訝很容易消失，即使我們將自己限制在最基本的東西，如自然數和自然數的集合。

康托爾的定理，*自然數集不可數*，可以被認為是關於原理不完備性的第一個定理，因為它表明一個理論永遠無法明確地定義所有自然數集。更一般地，只要集合是不可數的，一個理論就永遠無法明確地定義所有元素。

一個理論無法證明它所陳述的所有真命題，因為它永遠無法定義足夠的集合來給出這些證明。例如，無限歸納原理應用於自然數集。如果集合在理論中沒有被定義，我們就不能使用它們來定義用於歸納推理的公式。我們可以得出結論，數學不完備性是不可數性的結果，因為一個理論永遠無法定義不可數的集合，因此總有一些集合是它無法定義的。

我們首先以消除技術難度的方式證明哥德爾第一個不完備性定理，並讓我們專注於論證的核心，一個關於自身不可證明的真命題。哥德爾證明，這個命題在允許公式化的理論 *T* 為真的假設下是真的。但這個關於「不可證明」命題真值的證明無法在 *T* 中形式化。這個命題從 *T* 的公理中是不可證明的，但它不是絕對不可證明的，因為哥德爾已經證明了它的真值。為了形式化這個證明，需要一個證明 *T* 的公理為真的理論。但塔斯基已經證明，一個理論永遠無法為自身定義一個真值謂詞。這就是為什麼關於「不可證明」命題的證明無法在 *T* 中形式化的原因。

康托爾關於自然數集不可數性的定理、哥德爾關於可證明性不完備性的定理、塔斯基關於真值不可定義性的定理以及丘奇和圖靈關於不可判定性的定理，都是同一數學不完備性的體現。

我們將最後證明，數學原理的不完備性並不令人感到驚訝，因為如果我們知道如何找到所有不可判定問題的解決方案，我們就會擁有一種全知，我們就會知道如何找到所有問題的所有解決方案。

哥德爾第一個不完備性定理

這裡提出的證明是非傳統的。哥德爾在算術理論上進行論證。它表明公式可以用數字表示，邏輯推理關係可以用數字之間的關係來表示。他證明的所有技術難點都來自這裡：證明公式之間的邏輯關係可以用表示這些公式的數字之間的數值關係來確定。通過在不是數論而是公式論的理論上進行推理，消除了這種難度。

沒有任何東西禁止建立一個允許在自身公式上進行推理的理論。這種方式不如哥德爾的證明那麼令人信服，因為它並沒有證明數論是不完備的，而只是證明了關於自身公式的奇怪理論是不完備的。人們甚至可能相信，證明核心中的悖論命題僅來自理論的怪異，並擔心存在一些不一致，因此該理論不是一個好的數學理論。這種擔憂是沒有根據的。如果我們做對了，很容易建立一個關於自身公式陳述真理的真實且因此一致的數學理論。這是證明數學不完備性的最簡單和最快的方式。但這還不足以證明數論的不完備性。

以下證明與哥德爾的證明相同，只不過一點不同，那就是在公式論上進行推理，因此公式不是用數字表示的。

*T* 是一個將自身公式視為個體或對象的理論。它包含二元謂詞 *是……的邏輯結果*，並在其公理中承認邏輯原理。任何有限的前提列表都可以被識別為一個單一的公式，即它們的合取。

它還具有其他謂詞和公理，允許人們推理關於公式是如何構造的。特別是，它必須能夠定義一個謂詞 *是一個具有單個自由變量的公式*。具有自由變量的公式既不是真也不是假。我們必須為它們的變量 *f*、*x*、*y* ... 賦值，然後才能決定它們的真值。例如，*f 是一個公式* 是一個具有自由變量 *f* 的公式。*T* 理論 *T* 還必須能夠定義一個由 *g 是從一個具有自由變量的公式 f 中獲得的，通過用 x 替換其變量的所有出現* 定義的三元謂詞。假設所有公理都已正確選擇，因此它們是真實的，並且足以證明最基本的正式真理。

一旦定義了公理列表，*T* 就允許定義一個謂詞 *在 T 中是可證明的*，因為要成為可證明的，就足以是有限個公理的合取的邏輯結果。

*T* 然後允許定義以下謂詞

*哥德爾 (f)* 按定義等於 *f 是一個具有自由變量的公式，並且存在 g 使得 g 在 T 中不可證明，並且 g 是通過將 f 替換為其自由變量的所有出現從 f 中獲得的*。

*哥德爾 (f)* 是一個具有單個自由變量 *f* 的公式，因為變量 *g* 由存在量詞綁定。

然後我們可以證明，*哥德爾 (哥德爾 (f))* 是一個真命題，但在 *T* 中不可證明。

*哥德爾 (哥德爾 (f))* 按定義表示 *哥德爾 (f) 是一個具有自由變量的公式，並且哥德爾 (哥德爾 (f)) 在 T 中不可證明*。

如果 *哥德爾 (哥德爾 (f))* 在 T 中是可證明的，那麼它將是假的，因為它關於自身聲稱它在 *T* 中不可證明。現在我們假設 *T* 的所有公理都是真的。因此，*T* 的所有定理，即在 *T* 中可證明的命題，也都是真的。因此，*哥德爾 (哥德爾 (f))* 不能是 *T* 的定理，因此它是真的，因為這就是它所說的。因此，我們在 *T* 中找到了一个真命題和一個不可證明的命題。

為了將這個證明轉換為數論，只需證明謂詞 *在數論中是可證明的* 和 *g 是從一個具有自由變量的公式 f 中獲得的，通過用 x 替換其變量的所有出現* 可以用表示公式的數字之間的算術關係來表示。

技术说明：为了正确地构建理论T，必须注意公式变量的使用。f是公式变量，但本身并不是T的良构公式。因此，例如对于任何公式f，f，也不是T的良构公式。良构公式必须始终包含应用于常量或变量的常量谓词。此外，当公式A(f)应用于另一个公式B(f)时，即形成A(B(f))，变量f在B(f)中是自由的，但在A(B(f))中不是，因为B(f)在那里是一个常量。

不可数性和不完备性

哥德尔定理的证明类似于康托尔定理的证明，因为具有自由变量的公式可以被视为所有对其为真的存在物的名称。哥德尔证明定义了所有无法证明属于它们所编号的公式命名的集合的数字集合。

从数字集合的不可数性得出哥德尔不完备性结果并非先验的。哥德尔真实的不可证语句只处理数字，而不是数字集合。人们可能希望算术能证明所有只与数字相关的真理，它不需要证明所有数字集合的存在。但这种希望是徒劳的。

为了证明算术真理，我们使用数学归纳原理，它可以表述如下

如果一个数字集合包含零，并且它始终包含其每个元素的后继，那么它包含所有自然数。

没有明确处理数字集合的数论将此原理应用于具有自由变量的公式。这些用来表示数字集合。

一个明确的理论永远无法证明所有关于数字的真理并不奇怪，因为总是有它无法定义的数字集合，这些集合可能需要证明关于数字的某些真理。关于数字的真实语句是不可证的，当该理论没有定义证明它所需的数字集合时。以下将表明，对于哥德尔的真实不可证语句，缺失的集合是算术真理的数字集合。

塔斯基关于真理不可定义性的定理

我们可以通过简单地说出我们必须说的话来说出真理，但我们也可以通过冗余地坚持并说出我们所说的是真理来表达。我们使用真理谓词，可以将其归因于或不归因于我们所说的一切。塔斯基 (1933) 证明，如果一个数学理论是真实的，那么这样的真理谓词就不可能存在。

让我们从上面讨论的关于其自身公式的理论 T 开始推理。

如果T包含真理谓词它是真的，那么公式它是真的，当且仅当f对于T的所有公式f都是真的。根据真理的定义，雪是白色的，当且仅当雪是白色的。正是凭借这一原理，塔斯基奠定了数学真理理论（塔斯基 1933），我们现在将其理解为模型理论。

让我们通过归谬法来证明，如果一个理论T是真实的，那么真理谓词不可能存在于它之中。

假设对于T的所有公式，在T中定义了一个谓词是真实的。

让我们通过f是具有自由变量的公式，并且存在一个公式g，使得g不为真，并且g是通过将f的所有自由变量出现的f替换为f而从f获得的，来定义具有自由变量的公式Tarski(f)。

Tarski(Tarski(f)根据定义意味着Tarski(Tarski(f))不为真。Tarski(Tarski(f))当且仅当不为真时才为真，这是一个谬论，因此如果谓词是真实的是真实的，它就不可能存在于理论T中。

要将此证明转换为数论，只需对谓词是真公式的数字进行推理。一个数论永远不允许定义这样一个谓词，如果它是真实的。

塔斯基既是能够定义数学真理的理论家，也是证明它在所有数学理论中都不可定义的人。

塔斯基定理提供了哥德尔第一个不完备性定理的另一个间接证明：如果一个理论能够定义自身可证性的谓词，并且它的所有定理都是真的，那么必须至少存在一个真且不可证的语句，否则可证性谓词将是真理谓词。

如何证明不可证的？

让我们回到定义了可证性谓词在T中可证和T中的一个真且不可证语句的理论T。通过展示这个“不可证”的语句，我们证明了它是真的。证明很简单，但它基于理论T本身是真实的假设。但理论T不允许定义自身真理的谓词，如果它是真实的，只允许定义可证性的谓词。因此，我们无法用理论T的方法形式化“不可证”语句的非形式化证明。这就是为什么这个可证语句在T中是不可证的。但是塔斯基对数学真理的定义允许我们用一个真理谓词定义一个理论T+，该谓词仅限于T：是T的真公式。然后可以在T+中形式化T中真且不可证语句的非形式化证明。因此，T中的不可证语句是T+中证明的定理。但当然T+不是一个完备的理论，因为我们可以在T+中找到一个新的真且不可证的语句，该语句需要一个真理谓词来证明，该谓词仅限于T+。

要在T+中形式化非形式化证明，必须在T+中证明T的所有定理都是真的。它是通过数学归纳法证明的。如果一个公式集合包含T的所有公理及其元素的所有直接逻辑结果，那么根据T的定理集的定义，它包含T的所有定理。因此，要证明T的所有定理都是真的，只需证明T的所有公理都是真的，以及真公式的直接逻辑结果同样也是真的就足够了。但要形式化这个非形式化证明，需要在T+中有一个针对T公式的真理谓词。

要将此证明转换为数论，只需对谓词是该理论的真公式的数字进行推理。人们总是可以为算术理论添加新的公理，以便这个真理谓词（限于初始理论）是可定义的。因此，可以在富集的理论中证明初始理论中真实且不可证的语句。只需形式化非形式化证明即可。

哥德尔第二不完备性定理

哥德尔已经证明，一个一致的理论永远无法证明自身的一致性。哥德尔的第二个不完备性定理经常被误解。人们认为，对一致性的证明非常困难，或者难以获得，或者永远无法得到理性的证明，因为它会陷入恶性循环。但有一个更直接的解释。一致性证明有时很容易找到，并且是不可反驳的，没有任何逻辑错误，并且没有任何疑问能够持续存在，但它们不能在证明了一致性的理论中形式化，因为它们需要该理论的真理谓词。塔斯基关于真理谓词不可定义性的定理解释了哥德尔的第二个不完备性定理。

哥德尔第二不完备性定理：一个真实的理论不能证明自身的一致性。

让我们对理论T及其真语句进行推理，该语句在T中是不可证的，Gödel(Gödel(f))。

让我们通过归谬法来证明T不能证明自身的一致性。如果可以的话，它可以证明Gödel(Gödel(f))并且不是Gödel(Gödel(f))在T中是不可证的。

但根据Gödel(f)的定义，它可以证明如果不是Gödel(Gödel(f))那么 (Gödel(Gödel(f)) 在T中是可证的)。因此它可以证明如果不是Gödel(Gödel(f))那么 (不是Gödel(Gödel(f)) 在T中是不可证的)。但不是Gödel(Gödel(f))意味着Gödel(Gödel(f))根据Gödel(f)的定义在T中是可证的。因此T可以证明如果不是Gödel(Gödel(f))那么 ((Gödel(Gödel(f)) 在T中是可证的) 在T中是不可证的)。

此外，T 可以证明对于每个公式 f，如果 f 在 T 中可证，则断言 f 在 T 中可证的公式在 T 中可证。这一点有时被认为是哥德尔证明中的难点。但对于理论 T 来说，这几乎是显而易见的，因为对一个定理的证明同时证明了该定理是可证的。由于 T 可以证明 如果非 Gödel(Gödel(f))，那么 (Gödel(Gödel(f)) 在 T 中可证)，它也可以证明 如果非 Gödel(Gödel(f))，那么 ((Gödel(Gödel(f)) 在 T 中可证) 在 T 中可证)。

由于 T 可以从非 Gödel(Gödel(f)) 中得出矛盾的结论，它可以通过归谬法证明Gödel (Gödel(f))。但Gödel(Gödel(f)) 自己说它在T 中不可证。所以T 不会是真的。

因此，T 如果为真，则不能证明自身的相容性。

这种推理可以通过对公式进行编号而移植到数论。

一致性证明是否陷入恶性循环？

展示模型的一致性证明是在一个比T₀ 强的理论 T₊ 中形式化的，T₀ 是它证明了一致性的理论，因为它们定义了 T₀ 的真值集，而这个集合在 T₀ 中无法定义。如果一个理论是荒谬的，那么通过添加公理获得的任何理论也是荒谬的。一个荒谬的理论可以证明任何东西，一个肯定和它的反面，包括荒谬并非荒谬。因此，我们证明一个理论一致性的方法不能让我们区分一致理论和不一致理论，因为一个比不一致理论“更强”的理论可以证明它是相容的。这就是为什么人们有时认为这种证明什么也没证明，但这是一种错误。

我们不会对任何我们一无所知的 T₀ 理论进行推理。 T₀ 是皮亚诺算术或策梅洛理论，或其他我们用来奠定数学知识的理论。我们事先知道这些理论允许我们证明真理，因为没有它们，我们就不会拥有数学知识，而且似乎很明显我们有一些数学知识。如果我们非常悲观，我们可能会担心我们的形式理论包含会导致矛盾的措辞错误，而我们并不知道。但毫无疑问，这些理论经常揭示真相，除非我们放弃数学知识。当我们证明形式理论是真实和一致时，我们证实了我们已经直观相信的东西。而且我们证明了我们推理的自然能力足以让我们正确地推理推理。所以这不是一个恶性循环。它是理性的良性循环，理解自身。

理论、软件和递归可枚举集

数学理论和软件、计算机程序之间存在着非常密切的对应关系。当我们明确定义一个理论时，我们总是可以编写一个程序来证明它的所有定理。它只需按顺序打印所有公理和它之前打印过的公式的所有直接逻辑推论即可。这种寻找证明的方法只具有理论上的意义。在实践中，计算机将在找到值得写入的定理之前打印大量的毫无意义的公式。即使是最强大的计算机，通常也需要等待过长的时间才能找到有趣猜想的证明或反证。

我们可以给出几个递归可枚举集的定义，它们都是等价的。从许多其他条件中选择的以下条件，这三个条件都定义了集合E 的递归可枚举性

属于E 的所有原子真值都是一个明确理论的可证语句、定理。
存在一个软件，当我们呈现E 的元素的名称时，它总是回答“是”，当我们呈现不在E 中的实体的名称时，它不回答或回答“否”。
存在有限数量的初始表达式和有限数量的生成规则（Smullyan 1961），足以生成属于E 的所有原子真值。

一个明确理论的定理集始终是一个递归可枚举集。如果我们向一个证明查找器软件呈现一个定理，它将始终能够识别它是一个定理，因为它会检查所有可能的证明，无论它们有多长。如果我们呈现一个非定理，它不会回答，因为它会永远寻找一个不存在的证明。

不可判定集和问题

递归可枚举集总是可数的。由于它们的所有元素都可以被命名，我们总是可以在所有命名实体的集合中定义它们的补集，只要我们固定了一个命名系统。

当一个集合及其补集都是递归可枚举时，这个集合是可判定的，否则它是不可判定的。

当一个问题的所有解的集合不可判定时，该问题是不可判定的。

一个不可判定集的例子是皮亚诺算术中的所有真值集。哥德尔的第一不完备性定理证明了这个真值集不是递归可枚举的，因此不可判定。如果它是递归可枚举的，那么人们可以找到一个足够的公理完整列表来证明所有算术真值，但哥德尔证明了这样的列表不存在。

说一个问题不可判定并不意味着我们无法解决它，也不意味着它有我们永远找不到的解，它只意味着没有明确定义的理论可以给出该问题的所有解。我们定义的理论只能部分解决一个不可判定问题，永远无法完全解决。对于不可判定问题，我们永远不会结束，它是一个永远确定的苦役。但我们仍然可以寻找和找到解决方案，而且没有任何解决方案是先验不可获得的。只要有足够的创造力，我们就可以发明一种理论，使我们能够找到它。

数学原理的不完备性源于不可判定集的存在。如果所有真值集都是递归可枚举的，那么我们可以给出足够的公理列表来找到它们。但不可判定性表明真值集并不总是递归可枚举的。

通用机器和理论

一台可编程计算机是一台通用机器，因为它能够执行任何可想象的程序。如果程序是一次性写入只读存储器 (ROM)，那么计算机只是一台特定机器。

一台通用机器可以做其他机器（通用或特定）所能做的一切。只需给出程序即可。因此，所有通用机器在本质上都是等价的。它们都能做完全相同的事情。

在实践中，计算机的计算能力和存储空间有限。但计算能力只是一个速度问题，存储空间原则上可以无限扩展。想象一下，一台安装在能够在一个可以随时扩展的数据库中移动的机器人的计算机。

一个通用理论是一个可以证明所有其他理论可以证明的理论。例如，逻辑可以被形式化为一个通用理论。只需给出足够的公理，以便所有形式为 C 是 P 的逻辑结果 的真公式对于所有格式良好的公式C 和P 都是可证的。由于任何理论的任何定理总是从公理的有限合取中证明出来的，因此这种逻辑的形式化是一个通用理论。

哥德尔通过证明公式之间的逻辑关系可以通过表示公式的数字之间的算术关系来表示，证明了算术也是一个通用理论，即使它局限于一阶皮亚诺算术。

通用理论的存在构成悖论。与任何明确的理论一样，一个通用理论U 不能证明所有真理。它们不能证明的这些真理原则上可以在一个更丰富的理论 U+ 中证明，该理论有更多公理。但由于初始理论U 是通用的，它可以证明 U+ 可以证明的所有内容，这似乎与 U+ 比 U 更丰富的假设相矛盾。特别是，一阶算术的一致性证明可以在一阶算术中形式化，因为它可以在一个明确的理论中形式化，并且一阶算术是一个通用理论。但哥德尔的第二不完备性定理似乎禁止了这种可能性。

这个悖论的解释有点微妙。U+ 理论可以在U 中形式化，但U “不知道”U+ 是U 的一个丰富，也就是说U 可以证明U+ 的所有定理都是U+ 的定理，但它不能证明U+ 的定理对它本身有效。因此，它可以形式化自身一致性的证明，而没有明确地说出来，没有断言它是关于自身的一致性。

停机问题的不可判定性

停机问题：给定一个计算机程序和一个初始内存状态，计算机将停止并提供答案，还是会无限运行而不会给出答案？

假设计算机在存储空间上没有限制，并且在计算时不受外部因素的影响。

图灵证明了停机问题是不可判定的（1936 年）。

停止的机器的（程序、初始状态）对的集合是可枚举的，因为计算机可以模拟所有其他机器。如果它被提供了一个程序和一个初始状态，它只需要在初始状态上运行程序并等待它停止。如果它停止了，计算机就会响应它停止了。如果它没有停止，计算机就不会停止并且不会响应。

另一方面，不停止的机器的（程序、初始状态）对的集合不是可枚举的。这可以通过归谬法证明。如果它是可枚举的，那么就会有一个程序 P，使得对于任何对（程序 p，初始状态 i），当它为真时，机器停止并响应 p 从 i 开始不停止。一个程序可以被写入内存，因此也是一个可能的初始状态。从 P 开始，我们可以编写一个程序 P'，使得对于任何程序 p，当它为真时，机器停止并响应 p 从初始状态 p 开始不停止。我们可以将 P' 作为运行 P' 的机器的内存初始状态。这台机器会停止吗？根据构造，当且仅当它不停止时，它才会停止。这是一个荒谬。因此 P' 不可能存在，因此 P 也不可能存在。因此，不停止的机器的（程序、初始状态）对的集合不是可枚举的。因此停机问题是不可判定的。

所有逻辑定律集合的不确定性

逻辑定律的集合是一个通用理论，因为一个公式是某个理论的定理当且仅当断言它来自其公理的有限合取是一个逻辑定律。因此，通过了解所有逻辑定律，我们就知道所有理论的所有定理。

当一个理论用有限数量的公理定义时，一个公式不是定理当且仅当断言它来自公理的合取不是一个逻辑定律。

基本理论（皮亚诺算术，策梅洛理论 ...）通常用公理模式定义。例如，分离公理是一个模式，它允许以无穷数量的公式形成无限数量的公理。当它在谓词逻辑中表述时，数学归纳原理也是如此。但是这些具有无限数量公理的理论总是等价于具有有限数量公理的理论。通过以哥德尔和伯奈斯的方式引入类，它们类似于集合，但太大而不能真正被视为集合，策梅洛理论只有有限数量的公理。

即使理论有无限数量的公理，人们也总是要求存在有限数量的原则或规则足以机械地产生所有公理，否则该理论就不是明确的。这就是为什么明确的理论总是等价于具有有限数量公理的理论。

如果逻辑定律的集合是可判定的，那么所有可枚举的集合都是可判定的。属于可枚举集合 E 的所有真值都是具有有限数量公理的理论的定理。因此，E 的补集是所有 x 的集合，使得 如果公理成立，那么 x 属于 E 不是一个逻辑定律。如果逻辑定律的集合是可判定的，那么该集合将是可枚举的，因此 E 将是可判定的。

停机问题不可判定性的证明表明，至少存在一个不可判定的可枚举集合。因此，逻辑定律的集合不是可判定的。

第一个不完备性定理的证明可以直接证明逻辑定律集合的不可判定性。如果逻辑定律的集合是可判定的，那么理论 T 可以有足够的公理来证明所有形式为 f 不是 g 的逻辑结果 的真公式。因此，它可以证明所有形式为 f 在 T 中不可证 的真公式。由于 Gödel(Gödel(f)) 在 T 中不可证，因此 T 可以证明它。但 Gödel(Gödel(f)) 说它本身在 T 中不可证。然后 T 可以证明 Gödel(Gödel(f)) 在 T 中不可证，这是荒谬的。因此逻辑定律的集合是不可判定的。

逻辑定律集合或 Entscheidungsproblem（希尔伯特 1928 年）的不可判定性是由丘奇和图灵在 1936 年独立地用不同的方法证明的。

普遍性是不可判定性的原因

我们知道如何证明其不可判定性的问题总是完备问题，因为如果我们有一种方法可以找到它们的所有解，那么我们也会有一种方法来解决所有问题。从这个角度来看，数学原理的不完备性最终并不那么令人惊讶。我们不必将其视为无能的表现，因为它是由思维的普遍性造成的。我们可以思考所有问题，所有理论。我们可以陈述适用于所有可想而知和可思考的事物的普遍定律。但是我们没有足够的方法或原则来解决所有问题。我们的方法，即使是最强大的方法，也不能解决所有问题。我们只是生物。知道如何找到一个不可判定问题的全部解将是一种全知，因为人们将同时知道如何找到所有问题的全部解。

一个有限的原则列表足以生成所有逻辑定律。这就是哥德尔关于逻辑完备性的定理。因此，逻辑定律的集合是可枚举的。但由于逻辑定律的集合是不可判定的，因此不是逻辑定律的公式的集合不是可枚举的。逻辑定律在所有可能的世界中都是真的。逻辑定律的否定是谬误，在所有可能的世界中都是假的。既不是逻辑定律也不是逻辑定律的否定的公式在某些世界中为真，在其他世界中为假，它描述了可能的世界，可以想象的世界。描述一个可能世界的任何有限公理系统都使得其合取的否定不是一个逻辑定律。既不是逻辑定律也不是谬误的公式的集合是所有公理和有限公理系统的集合，它们至少关于一个可以想象的世界。说它不是可枚举的意味着我们不能给出一个有限的原则列表，足以产生所有这些公理系统。想象力超越了所有框架。无论一个人给自己什么有限的原则列表，总有它不允许研究的可能世界。因此，数学的不完备性是想象力的普遍性和力量的结果。

下一章：相对论原理的真值>>>