认识论概要/数学基础

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

一阶逻辑提供了一种方法，可以创建有限数量的基本概念应用于一个域（有限或无限）的个体的理论。为了用一阶逻辑的原理推理关于所有可以应用于特定域个体的概念，只需要将概念（属性和关系）视为新的个体，并为自己提供一个新的归属关系，该关系将属性（关系）与它们所归属的个体（个体的 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) 是关于集合的明确定义的公式，则所有满足 A(x) 为真的 E 中的 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，当且仅当对于所有 z（z 是 x 的元素当且仅当 z 是 y 的元素）时，x = 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 ，无法从策梅洛公理中证明。它可以通过一个新的公理，即由弗兰克尔（1922）提出的替换公理来证明，该公理更强大，可以证明大型无限集合的存在。但即使有了这个新公理，仍然有一些集合是理论无法定义的。

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

对分离公理的解释存在一个难题。什么是明确定义的公式？根据弗兰克尔的说法，任何从基本谓词 是...的元素 和 等于 以及逻辑连接词构成的公式都是明确定义的公式。分离公理始终可以应用于它们。但策梅洛并不相信这种方法，因为这些所谓的合理公式可能包含关于所有集合的断言，就好像所有集合的宇宙具有客观存在一样。但我们不知道这样的宇宙是什么。因此，我们并不总是知道如何理解用于在 ZFC 中定义集合的公式的含义。这个理论导致证明了非明确定义集合的存在。然而，非明确定义的集合不是集合，它不存在。所以 ZFC 是假的。

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

选择公理

证明一个集合存在的最直接方法是定义它，这相当于从已经定义的集合构建它。空集足以开始构建我们定义的所有集合。但我们也可以给出存在的间接证据。我们证明一个集合存在并具有某些属性，而没有明确地定义它，没有构建它，没有确切地说出我们指的是哪个集合。

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

选择公理： 如果 E 是一个非空且不相交集合的集合，则存在一个集合，它包含每个 E 元素的一个元素，且仅包含一个。

罗素悖论

我们本来可以考虑一个比策梅洛分离公理更简单的公理

弗雷格公理： 如果 A(x) 是一个合理的公式，则所有满足 A(x) 的 x 的集合存在。

这个公理是由弗雷格（1879）提出的，用来奠定所有数学的基础，但罗素（1901 年，1903 年出版）意识到它会导致矛盾。 x 不是 x 的元素 是一个合理的公式。通常，集合不是自身的元素，但也可能存在例外，例如所有集合的集合。 所有满足 x 不是 x 的元素的 x 的集合 ，所有不是自身元素的集合，如果我们采用弗雷格公理，就存在。它是自身的元素吗？从它的定义可以看出，它是一个元素，当且仅当它不是自身元素时。这是荒谬的，所以这个集合不可能存在，所以弗雷格公理是假的。

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

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

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 中的所有 x、y 和 z，一个集合 E 是全序的

• 如果 (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 的第一个元素的集合，并且当它包含 y 中所有严格在 z 之前的元素时，它总是包含 y 中的元素 z，则 x 包含 y 的所有元素。

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

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

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

集合是如何定义良好的？

除了空集之外，纯集合论中的所有集合都是从先前定义的集合中定义的。当且仅当集合始终通过尊重以下三个条件来定义时，集合是定义良好的

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

我们可以考虑一个更严格的条件来代替第二个条件：一个新定义的集合的元素必须是先前定义的集合。但这个条件可能会禁止定义无限集合的幂集，因为它是不可数的。由于一个定义良好的集合的幂集本身是定义良好的，所以必须接受一个定义良好的集合可以有作为其元素的集合，这些集合以前没有被定义。

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

在弗兰克尔的公式化（ZFC）中，分离公理不尊重第三个条件，因为无界量词的使用意味着属于一个新定义的集合的原子真值由属于所有集合的所有原子真值来确定，而不仅仅是属于先前定义的集合的原子真值。为了尊重第三个条件，在集合定义中使用的所有量词都必须受到先前定义的集合的限制。

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

Zermelo 理论中的可定义集合是什么？

我们可以从一个初始数字零和一个数字构造函数——“后继”——来定义所有自然数。类似地，我们可以用 Zermelo 的理论从初始集合和集合构造函数来定义所有可定义的集合。初始集合是空集和所有自然数的集合。基本构造函数是“二元组”、“和集”、“幂集”以及可以用分离公理定义的无限数量的构造函数，前提是量词在集合定义中是受限的。构造函数是所有基本构造函数的有限组合。Zermelo 理论中可定义的集合是所有通过对空集和自然数集应用这些构造函数之一得到的集合。

替换公理

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

当一个关系总是将同一个元素与单个元素关联时，它就是函数关系：对于所有 x、y 和 z，如果 Rxy 且 Rxz，那么 y=z

对 Fraenkel 公理的解释提出了一个难题：何时函数关系是定义良好的？

在 ZFC 理论中，Fraenkel 允许使用不受限的量词定义函数关系，因此是定义不好的函数关系。因此，在 Fraenkel 的版本中，替换公理是错误的。要正确应用 Fraenkel 公理，需要一个定义良好的函数关系理论。

定义良好集合理论

Zermelo 的理论是一个定义良好集合理论，前提是在用分离公理构造集合的定义中施加了受限量词规则。但是，如果我们想发展无限集合理论，它是不够的。ZFC 强大得多，但它允许定义不好的构造。

我们可以定义一个比 Zermelo 理论强大得多的理论，它只允许使用基本构造函数及其有限组合来进行定义良好的构造。

第一类构造函数从已经构造的集合中构造集合。Zermelo 理论的基本构造函数（“二元组”、“和集”、“幂集”以及可以用分离公理定义的所有构造函数，前提是在集合定义中所有量词都是受限的）是第一类构造函数。第一类构造函数的有限组合也是第一类构造函数。我们引入两个新的基本构造函数：“像集”和“通过有限迭代获得的集合”，我们将其缩写为“无限集”。它们是第二类构造函数。它们从第一类构造函数中构造第一类构造函数。

如果f是一个具有一个参数的第一类构造函数，那么“f的像集”是一个第一类构造函数，它对于任何集合x构造所有 y 的集合，使得存在 z 属于 x，使得 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

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

为了奠定一个定义良好集合理论，我们保留了 Zermelo 的所有公理，除了无限公理，并且我们添加了两个公理模式：替换公理和一个广义的无限公理。

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

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

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

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

一致性证明

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

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

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

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

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

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

Peano 公理的真理

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

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

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

Zermelo 公理的模型

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

设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 不是集合的一部分。因此，无限二叉树的所有路径集是所有自然数集的集合的表示。现在，我们可以通过观察无限二叉树在视野中的展开来想象它。我们可以一眼看到它所有的路径，它们是不可数的。

一条直线上有不可数多个点，即使它长度有限。因为我们可以看到直线和表面，所以我们可以看到不可数的东西。

为了使策梅洛公理的一致性证明为假，我们必须错误地认为不可数集合，即在不知不觉中，关于不可数的推理会导致我们陷入荒谬。但为什么害怕我们可能被自己的理性愚弄？似乎我们在对一个集合的所有子集进行推理时没有犯错误，即使它是一个无限集。

为了使策梅洛公理的一致性证明形式化，只需要在策梅洛公理中添加对无限公理的扩展：存在一个包含 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 ，任何理论都无法证明它。事实上，当我们在一个理论 T 中找到一个无法证明的真理 V 时，通常很容易定义一个理论 T+ ，在 T 中添加一个新公理，从而允许证明 V 。

希尔伯特（1930 年）的原理，“我们必须知道，我们将知道”，即使在哥德尔之后仍然成立。没有任何东西可以证明存在我们永远不会知道的数学真理。

我们通常在第一次听到哥德尔的 不完备性定理时感到非常惊讶，因为我们习惯于将数学真理和可证明性等同起来。我们知道，当我们知道如何证明一个定理时，我们就知道了它是真的。但是，当我们理解一个明确的公理列表不足以证明所有数学对象的实存在时，这种惊讶很容易消除，即使我们只限于最基本的数学对象，即自然数和自然数的集合。

康托尔的定理，自然数的集合不可数，可以被认为是关于原理不完备性的第一个定理，因为它表明一个理论永远无法明确地定义所有自然数的集合。更一般地说，只要集合是不可数的，一个理论就永远不能使所有元素被明确地定义。

一个理论无法证明它所陈述的所有真命题，因为它永远不能定义足够的集合来给出这些证明。例如，无限归纳原理应用于自然数的集合。如果集合在理论中没有被定义，我们就不能用它们来定义公式，然后用这些公式进行归纳推理。我们可以得出结论，数学的不完备性是不可数性的结果，因为一个理论永远不能定义不可数的集合，因此总有它无法定义的集合。

我们首先以一种消除技术困难并允许我们专注于论证核心的一种方式来证明哥德尔的第一个不完备性定理，即一个关于自身不可证明性的真命题。哥德尔证明了，这个命题在允许表达它的理论 T 是真的的情况下是正确的。但是这个“不可证明”命题的真实性证明不能在 T 中形式化。这个命题从 T 的公理无法证明，但它不是绝对不可证明的，因为哥德尔已经证明了它的真实性。为了形式化这个证明，需要一个证明 T 的公理是真实的理论。但是塔斯基证明了一个理论永远不能为自己定义一个真理谓词。这就是为什么“不可证明”命题的证明不能在 T 中形式化的原因。

康托尔关于自然数的集合不可数性的定理，哥德尔关于可证明性不完备性的定理，塔斯基关于真理不可定义性的定理，以及丘奇和图灵的不可判定性定理，都是同一种数学不完备性的体现。

最后，我们将证明数学原理的不完备性并不令人惊讶，因为如果我们知道如何找到所有不可判定问题的解决方案，我们将拥有一种无所不知的能力，我们将知道如何找到所有问题的解决方案。

哥德尔的第一个不完备性定理

这里提出的证明是不寻常的。哥德尔论证的是一个算术理论。它表明公式可以用数字表示，逻辑推论之间的关系可以用数字之间的关系表示。他证明的全部技术难度来自这里：表明公式之间的逻辑关系可以通过表示这些公式的数字之间的数字关系来确定。通过不针对数字理论，而是针对公式理论进行推理，消除了这种困难。

没有什么禁止做一个允许针对它自己的公式进行推理的理论。这种方式不像哥德尔的那么令人信服，因为它没有证明数论是不完整的，而只是证明它自己公式的一个奇怪理论是不完整的。人们甚至可能认为，证明的核心是那个悖论性的命题，它仅仅来自理论的奇怪性，并担心存在一些不一致性，因此该理论不是一个好的数学理论。这种恐惧是毫无根据的。如果我们做对了，很容易创建一个真实的，因此是一致的数学理论，它陈述了关于它自己公式的真理。这是证明数学不完备性的最简单、最快的方法。但这不足以证明数论的不完备性。

以下证明与哥德尔的证明相同，只有一点不同，即一个人针对公式理论进行推理，因此公式没有用数字表示。

T 是一个将它自己的公式视为个体或对象的理论。它包含二元谓词是…的逻辑推论，并且在它的公理中承认逻辑原理。任何有限的前提列表都可以被识别为一个单一的公式，即它们的合取。

它还有其他谓词和公理，允许人们推理关于公式是如何构建的。特别是，它必须使定义谓词是具有一个自由变量的公式成为可能。具有自由变量的公式既不是真的也不是假的。在我们决定它们的真值之前，我们必须为它们的变量 f ， x ， y ... 赋值。例如， f 是一个公式 是一个具有一个自由变量 f 的公式。 T 理论 T 还必须使定义由 g 是通过用 x 替换其所有变量出现来从具有一个自由变量的公式 f 中获得的定义的三元谓词成为可能。假定所有公理都被正确选择，因此它们是正确的，并且足以证明最基本的正式真理。

一旦定义了它的公理列表， T 就可以定义谓词在 T 中可证明，因为要可证明，就足以是公理的有限合取的逻辑推论。

T 然后允许定义以下谓词

Gödel (f) 按定义等于 f 是一个具有一个自由变量的公式，并且存在 g 使得 g 在 T 中不可证明，并且 g 是通过用 f 替换其所有自由变量出现来从 f 中获得的。

Gödel (f) 是一个具有一个自由变量 f 的公式，因为变量 g 被存在量词绑定。

然后我们可以证明 Gödel (Gödel (f)) 是一个真命题，但在T中不可证。

Gödel (Gödel (f)) 根据定义意味着 Gödel (f) 是一个带有自由变量的公式，并且 Gödel (Gödel (f)) 在 T 中不可证 。

如果 Gödel (Gödel (f)) 在 T 中可证，那么它将是假的，因为它本身表示它在 T 中不可证。现在假设 T 的所有公理都是真的。因此， T 的所有定理，即在 T 中可证的命题，也是真的。因此， Gödel (Gödel (f)) 不能是 T 的定理，因此它是真的，因为这正是它所表达的。因此，我们在 T 中找到了一个真命题且不可证的命题。

为了将这个证明移植到数论，只需证明谓词 在数论中可证 和 g 是通过将 x 代入其所有自由变量的出现而从带有自由变量的公式 f 中得到的 可以用表示公式的数字之间的算术关系来表示。

技术说明：为了正确地构建理论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 获得的 来定义带有自由变量的公式 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 中可证。这个点在 Gödel 证明中有时被认为是困难的。但对于理论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₀是皮亚诺算术或策梅洛理论，或者我们选择作为我们数学知识基础的其他理论。我们事先知道这些理论允许我们证明真理，因为没有它们，我们就不会有数学知识，而且我们似乎很清楚我们有一些数学知识。如果我们非常悲观，我们可能会担心我们的形式理论包含会导致矛盾的措辞错误，而我们并不知道。但毫无疑问，这些理论经常揭示真理，除非我们放弃数学知识。当我们证明形式理论是真实和相容的时，我们证实了我们已经直觉上相信的东西。并且证明了我们自身的推理能力足以对推理进行正确的推理。所以这不是恶性循环。这是理性能理解自身的良性循环。

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

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

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

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

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

不可判定集合和问题

递归可枚举集合总是可数的。由于它们的元素都可以命名，一旦我们确定了一个命名系统，我们就可以始终在所有命名存在的集合中定义它们的补集。

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

一个问题在它的所有解的集合是不可判定时是不可判定的。

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

说一个问题不可判定，并不意味着我们无法解决它，也不意味着它有我们永远找不到的解，它只意味着没有明确定义的理论可以带来该问题的所有解。我们定义的理论只能部分解决不可判定问题，永远无法完全解决。对于不可判定问题，我们永远无法完成，这是永恒的苦役。但我们仍然可以寻找和找到解决方案，没有解决方案是先验不可触及的。只要我们足够有创造力，就可以发明一个使我们能够找到它的理论。

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

通用机器和理论

一台可编程计算机是一台通用机器，因为它能够执行任何可能的程序。如果程序是一劳永逸地写入只读存储器 (ROM)，则该计算机只是一台特定机器。

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

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

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

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

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

这个悖论的解释有点微妙。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 年独立使用不同的方法证明。

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

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

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

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