史海钩沉
哥德尔不完备性定理的完整故事
著名数学家库尔特·哥德尔证明了两个"不完备性"定理，这揭示了算术真理的复杂性，打破了人们对于形式化证明的梦想。
在20世纪30年代，特尔斯基等逻辑学家已经确立了谓词逻辑的语义学。他们描述了"解释"的确切含义，以及一个公式在某个解释下为真的意义。简而言之，一个解释是一个非空集(论域)加上每个n元关系符号对应宇称上的n元关系，每个n元运算符号对应宇称上的n元运算。
在此之前，逻辑一直止步于句法和证明论层面。语义学的出现引发了人们对句法与语义之间关系的思考。逻辑学家们特别想知道，每个永真式(在所有解释下都为真的公式)是否都可证明。
年轻的哥德尔在其博士论文中对此给出了肯定的答复:他证明了每个永真式都有证明，这就是他的"完备性定理"。
算术真理
在所有解释下为真很重要，但实际上我们还需关注哪些在个别解释下为真。我们特别想知道在算术解释下(宇称为整数，有等于、小于关系和后继、加法、乘法运算)哪些为真。
哥德尔的同事们正在寻找一种现代术语中所谓的"判定程序"，用于判定一阶算术形式在标准解释下是否为真。例如，孪生素数猜想就是这样的一个一阶公式。
哥德尔起初也试图找到这种判定程序，但最终认为不可能，并着手证明。假设算术真理(现在称为True算术)的集合存在判定程序，那我们就可以列举所有公式，剔除假的，留下真的作为True算术的公理。这些公理就是完备的:每个公式要么就是其中之一，要么其否定式就是。
哥德尔的策略是证明True算术没有完备公理化。对于任何一组假设的公理集A，他都能构造出一个U(A)语句，使其在A下无法证明但却为真。他使用了与"谎言悖论"相同的伎俩:U(A)就是"U(A)在A下无法证明"这一命题。
由此可推出U(A)为真(它确实无法在A下证明)，但同时也无法证明。
可递归枚举与递归
在此过程中遇到一个重要概念——(可递归)枚举。一个集合是可递归枚举的(re)，当且仅当存在一台机器，它运行可能永不停止，但最终会输出该集合中任何特定元素，且只输出该集合的元素。一个简单的re集合例子就是自然数，可由一个从0开始的计数器来枚举。
一个集合是递归的，当且仅当存在一个判定程序来测试其元素是否属于该集合。也就是说，哥德尔的同事们想证明算术中所有真一阶公式的集合是递归的。
可以证明每个递归集合都是re的——要枚举其元素，只需将自然数通过筛选器，滤除非元素即可。另一方面，如果一个集合S和它的补集-S都是re的，那S一定是递归的。要判断n是否属于S，只需同时枚举S和-S，直到n出现在其中之一:若出现在S的枚举中，n属于S;否则n属于-S。
哥德尔编码
我们需要证明各种公式集合是re的还是递归的，但严格来说，只有自然数集合才有这些性质。哥德尔的解决方案是设计了一种编码方案，使每个公式都有一个唯一的编码，反之亦然。
编码方式有多种，细节并不重要。例如，我们可以将一个数分解为指数幂的乘积，将该数视为对应的指数序列的编码。
一旦能编码任意长度的序列，我们就可以编码嵌套序列和任意层次结构，由此得到逻辑公式、证明树、公式集合等。可以证明公式集合和证明树(尤其是后者)是递归的，因此也是re的。
结果的可枚举性
然后，从证明树的枚举中，我们可以筛选出那些无前提的，并提取出它们的结论。这表明永真式(公式的编码)的集合是re的。
永真式是空公理集的所有结果。我们可以用类似的论证证明，对于任何有限公理集，其结果的集合都是re的。
经过一些努力，我们还可以证明对于任何可枚举的公理集，其结果的集合同样是re的。我们枚举出公理集的所有前缀段，对每个前缀段枚举其结果，再合并所有这些枚举。(这里的原理是re集合的可递归并是re的)。
判定程序
这意味着，如果我们有算术的一组完备公理集，那我们就有了判定程序。
一组公理是完备的，当且仅当对于任何公式ψ，要么ψ要么其否定式¬ψ是这组公理的结果。如果我们有算术的一组完备(re)公理集，要判断一阶算术公式ψ在算术解释下是否为真，我们只需枚举这组公理的所有结果，等待ψ或¬ψ出现。如果ψ出现，则为真;否则为假。由于公理集是完备的，ψ和¬ψ中必定有一个最终会出现，我们不会永远等待下去。
另一方面，如果存在判定程序，我们也可以很容易地找到一组可枚举的完备公理集。我们运行公式集合通过判定程序，过滤掉假的，留下真的算术公式，这个集合显然是re的(假设存在判定程序)，因此显然构成了算术真理的完备公理化。
总结一下，算术真理是否递归，等价于是否有完备的(re)公理集。
算术的公理
那么，哪组公理才算完备呢?实际上只有一个候选者，那就是皮亚诺算术公理。皮亚诺公理有不同形式，最简单的是加法和乘法的递推方程，加上一个形式化的数学归纳公理。现在我们已经知道皮亚诺算术是不完备的，这是由于哥德尔的定理。但当时哥德尔显然并不知道这一点。我也没有查到当时人们是否已经意识到皮亚诺算术的不完备性。
如果皮亚诺算术是不完备的，那么需要添加什么呢?诸如分配律等已经可以通过归纳法证明了。
哥德尔起初认为算术是可公理化的，但在某个时候他开始怀疑，并着手证明它的不可公理化性。他的策略是构造出一个语句，使其可证明性会导致矛盾。这个语句应该断言某个真命题的不可证明性。
谎言句
解决方案就是产生一个断言自身不可证明性的句子。如果可以证明它，那它就是假的，从而导致矛盾。但如果它不可证明，那它就是真的，因此算术是不完备的。
通过编码，我们可以谈论可证明性，但关键是让这个句子指代自身。
令PA表示在A下的可证明性。枚举所有一元公式，使φn为第n个这样的公式。
现在考虑一元公式¬PA(φi(i)))，记作δ(i)。在上述枚举中，它必定有一个编号d，使得δ(d)等价于¬PA(φd(d))。但δ的编号就是d，所以δ(d)就是φd(d)。综合等价关系，我们得到φd(d)等价于¬PA(φd(d))，即φd(d)断言了自身的不可证明性。
现在我们仔细分析。如果φd(d)可证明，那就会导致矛盾，而这在A是一致的时候是不可能的。所以con(A)蕴含φd(d)不可证明，即con(A) -> φd(d)。但如果我们能证明A的一致性，那我们就可以证明φd(d)，这又与之前的结论矛盾(假设A确实是一致的)。
因此，如果A是一致的，我们就不能证明它的一致性。这就是哥德尔的第二个不完备性定理。
所以，对于任何足够强大且一致的系统A，它不仅是不完备的，而且它自身的一致性也是不可证明的。这打破了人们对于算术有完备的、最终的公理化系统、算术真理的判定程序以及可证明一致的公理集的梦想。
事实上，算术真理是一个非常复杂的集合——每增加一个量词交替都会提高一个复杂度层次。
它远比哥德尔之前的研究者们所期望的那个可判定的集合要复杂得多。
依赖经验
既然我们无法证明皮亚诺算术的一致性，那我们该如何自圆其说呢?(我们可以用更强大但自身一致性也存疑的系统来证明皮亚诺算术的一致性)。
我们只能依赖一个多世纪以来对皮亚诺公理的经验。在这段时间里，人们从未发现任何矛盾。这为皮亚诺算术的一致性提供了有力的实验证据。
同时，在这段时间里，皮亚诺系统被证明在"实用"数学领域是完全足够的。这为皮亚诺算术在实践意义上的完备性提供了有力的实验证据:我们感兴趣的一切真命题都是可证的。
实际上，直到1977年，帕里斯和哈林顿才发现一个"自然"的不完备性例子。他们发现了一种强大的Ramsey定理形式，它蕴含着皮亚诺算术的一致性，因此不可证明。
所以一致性和完备性在实践中都不是问题。只有当我们将自己局限于形式推理时，情况才会变得糟糕。如果我们像任何其他科学一样允许实验证据，我们就处于一个良好的状态。这就是不完备性定理的真正意义所在。
本文译自 Bill Wadge's Blog，由 BALI 编辑发布。