库尔特·哥德尔（二）

顺便说一句，在洛文海姆-斯科勒姆定理的证明中，特别是在定理中为可满足的句子构建模型的部分，洛文海姆和斯科勒姆的树构造或多或少与哥德尔论文中出现的相同。在 1967 年写给王浩的信中，哥德尔指出了这样一个事实，即他的完备性证明几乎在 1923 年就被 Skolem 获得了。尽管 van Heijenoort 和 Dreben (Dreben and van Heijenoort 1986) 评论说“在 20 年代的大部分时间里，它并没有被证明”。语义完整性，但量化有效性的决策问题，这个问题源于施罗德和Löwenheim，这是研究量化理论的主要关注点”（此类结果的例子包括 Behmann 提出的一阶单子谓词演算的决策程序，（Behmann 1922）），根据哥德尔的说法，Skolem 没有获得的原因完整的证明是不同的，并且在哲学上很重要，与当时对语义和无限方法的主要偏见有关：

从数学上来说，完备性定理确实是 Skolem 1923 的一个几乎微不足道的推论。然而，事实是，当时没有人（包括 Skolem 本人）从 Skolem 1923 中得出这个结论，也没有像我一样从类似的考虑中得出这个结论。他自己的……逻辑学家的这种盲目性（或偏见，或者无论你怎么称呼它）确实令人惊讶。但我认为解释并不难找到。其原因在于当时普遍缺乏对元数学和非有限推理所需的认识论态度。 （哥德尔 2003b）。

斯科勒姆对完备性定理的贡献问题已在 van Atten 和 Kennedy 2009 以及 van Atten 2005 中进行了广泛讨论。

2.2 不完备性定理

哥德尔在他 1929 年的论文中就已经提到了关于实数的问题可能无法解决，他反对希尔伯特的形式主义原则，即一致性是存在的标准。事实上，给出分析一致性的最终证明以及证明其完整性是当时所谓的希尔伯特纲领的一个关键需求。因此，轮到哥德尔解决这些问题，尤其是第一个问题，这使他得出了两个不完备性定理。 （对于希尔伯特纲领的讨论，读者可以参考标准参考文献：Sieg 1990、1988、1999；Mancosu 1998、Zach 2003、Tait 1981 和 Tait 2002。）

第一不完备性定理通过展示一个算术陈述提供了完备性的反例，该算术陈述在皮亚诺算术中既不可证明也不可反驳，尽管在标准模型中是正确的。第二不完备性定理表明，算术的一致性不能用算术本身来证明。因此，哥德尔定理证明了希尔伯特纲领的不可行性，如果它具有那些特定的需求、一致性和完整性的话。

顺便说一句，冯·诺依曼甚至在哥德尔之前就以这种方式理解了这两个定理。事实上，冯·诺依曼走得更远，认为它们完全证明了经典数学的不可行性。正如他在 1931 年 6 月写给卡尔纳普的信中所说：

因此，今天我的观点是： 1. 哥德尔已经证明了希尔伯特纲领的不可实现性。 2. 没有更多的理由拒绝直觉主义（如果不考虑审美问题，实际上对我来说审美问题也是决定性因素）。因此，我认为柯尼斯堡的基础性讨论已经过时了，因为哥德尔的基础性发现将问题提升到了一个完全不同的水平。 [9]

去年秋天，冯·诺依曼给哥德尔写了一封措辞更为强烈的信：

因此，我认为你的结果消极地解决了基本问题：经典数学没有严格的理由。 （哥德尔 2003b，第 339 页）

哥德尔本人花了几年时间才发现希尔伯特纲领的这些方面已被他的结果彻底驳倒（Mancosu 2004）。

2.2.1 第一不完备性定理

在他的《逻辑之旅》（Wang 1996）中，王浩发表了哥德尔（应王的要求）撰写的关于他发现不完备性定理的材料的全文。这些材料构成了王的《关于库尔特·哥德尔的一些事实》的基础，并得到了哥德尔的阅读和认可：

1930年夏天我开始研究经典分析的一致性问题。希尔伯特为什么想用有限方法直接证明分析的一致性是很神秘的。我看到两个有区别的问题：用有限数论证明数论的一致性，以及用数论证明分析的一致性……由于有限数论的领域没有明确定义，我开始解决后半部分……我用数论中的谓词表示实数……并发现我必须使用真值概念（对于数论）来验证分析公理。通过枚举给定系统内的符号、句子和证明，我很快发现算术真理的概念不能用算术来定义。如果可以在系统本身中定义真理，我们就会遇到类似说谎者悖论的情况，表明系统是不一致的……请注意，这个论证可以形式化以显示不可判定命题的存在，而无需给出任何单独的实例。 （如果没有不可判定的命题，所有（且仅有）真命题都将在系统内得到证明。但是这样我们就会遇到矛盾。）……与真理相反，给定形式系统中的可证明性是某些特定命题的显式组合属性。系统的句子，可以通过适当的基本方法正式指定......

我们看到哥德尔首先尝试将分析的一致性问题简化为算术的一致性问题。这似乎需要一个算术的真值定义，这反过来又导致了悖论，例如说谎者悖论（“这句话是假的”）和贝里悖论（“仅由十四个英语单词组成的表达式无法定义的最小数字”） ）。哥德尔随后注意到，如果真理被可证明性取代，这样的悖论不一定会出现。但这意味着算术真理和算术可证明性并不同时广泛——这就是第一不完备性定理的由来。

关于哥德尔发现的这段描述是在事后很久才告诉王浩的。但在哥德尔与伯奈斯和策梅洛同时代的通信中，对他的定理路径的描述基本上是相同的。 （分别参见 Gödel 2003a 和 Gödel 2003b。）从这些叙述中我们可以看出，算术中真理的不可定义性这一结果归功于塔斯基，很可能是哥德尔在 1931 年以某种形式获得的。逻辑学家当时就真值概念所表达的偏见，当塔斯基于 1935 年宣布他关于形式系统中真值的不可定义性的结果时，这些偏见就猛烈地凸显出来，这可能阻碍了哥德尔发表该定理。

2.2.2 第一不完备性定理的证明

现在我们描述这两个定理的证明，用皮亚诺算术表述哥德尔的结果。哥德尔本人使用了与《数学原理》中定义的系统相关的系统，但包含皮亚诺算术。在我们介绍第一和第二不完备性定理时，我们将皮亚诺算术称为 P，遵循哥德尔的符号。

在进行正式证明的细节之前，我们定义哥德尔在第一不完备性定理中使用的 ω 一致性概念：如果 P ⊢ Øφ(n) 对于所有 n 意味着 P ⊬ ∃xφ(x ）。自然地，这意味着一致性，并且源自自然数满足皮亚诺算术公理的假设。

证明中使用的主要技术工具之一是哥德尔编号，这是一种将自然数分配给我们形式理论 P 的术语和公式的机制。有不同的方法可以做到这一点。最常见的是基于自然数作为素数幂乘积的独特表示。数论的每个符号 s 以固定但任意的方式分配一个正自然数 #(s)，例如

(0)：= 1 (=)：= 5 (Ø)：= 9

(1)：= 2 ( ( )：= ​​6 (∀)：= 10

(+)：= 3 ( ) )：= ​​7 (vi)：= 11 + i

(×)：= 4 (∧)：= 8

对应于符号序列 w = ＜ w0,…, wk ＞ 的自然数为

⌈w⌉ = 2(w0)：· 3(w1)：· … · pk#(wk),

其中 pk 是第 k+1 个素数。它被称为哥德尔数，用 ⌈w⌉ 表示。通过这种方式，我们可以将哥德尔数分配给公式、公式序列（一旦采用了区分一个公式何时结束而另一个公式何时开始的方法），以及最值得注意的证明。

这里的要点是，当一个公式被解释为一个自然数时，那么与该自然数相对应的数字可以作为公式的参数出现，从而使语法能够“引用”自身，可以这么说（即，当一个数字代入公式时，该数字代表的哥德尔数）。这最终将允许哥德尔将说谎者悖论形式化（用“可证明性”代替“真理”），方法是将其自己的自然数代码（或更准确地说是相应的数字）。

进行形式化所需的另一个概念是数论谓词的数字可表达性的概念。如果对于每个自然数元组 (n1, …, nk)，数论公式 φ(n1, …, nk) 可以用 P 进行数字表达：

N ⊨ φ(n1, …, nk) ⇒ P ⊢ φ(n1, …, nk)

N ⊨ Øφ(n1, …, nk) ⇒ P ⊢ Øφ(n1, …, nk)

其中 n 是表示自然数 n 的形式术语。 （在 P 中，这是 S(S(…S(0)…)，其中 n 是应用于常数符号 0 的后继函数的迭代次数。）主要目标之一是以数字方式表达谓词

Prf(x, y)：“哥德尔数 x 的序列是哥德尔数 y 的句子的证明。”

达到这个目标涉及定义45个关系，每个关系都根据前面的关系定义。这些关系都是原始的递归。[10]所需的关系包括主张它代码序列，公式或公理的自然数量的关系，或者是代码，由SB表示（ru1…unz（x1）…z（xn）表示），通过用代码r的公式获得的公式，通过代替其自由变量UI xi th数字i = 1，…，n。定义的第四十五个原始递归关系是PRF（x，y），四十六是

prov（y）：‘gödel数字y的句子在p中可证明”

但是，它不具有原始递归，但是通过存在量化x来从prf（x，y）获得。 （Prov（Y）仅满足NumerWise表达性的“正”部分，而不是负面部分；但不需要负部分。）

在他的论文的定理v中，戈德尔证明了原始递归的任何数量理论谓词在P中都是可表达的。因此，由于PRF（X，Y）和替代是原始的递归，因此当闭合项被替换为P时，这些都是由P表示。自由变量x和y。正如我们将看到的那样，这是问题的核心。关于NumerWise Exprachisibal的另一个关键点是，尽管我们非正式地解释了Prov（SB（Ru1…Unz（X1）…Z（Xn））），by：'如果Gödel编号为r的公式是可证明的，如果Gödel编号是Gödel编号，则可以证明XI数字代替了ITH变量，“理论P中的正式陈述也不是我们证明的任何内容都吸引了这种含义。相反，Prov（SB（RU1…UNZ（x1）…Z（xn）））是毫无意义的逻辑和算术符号。正如戈德尔（Gödel以下定理（v）的语言，没有提及对P的​​公式进行任何解释（Gödel1986，p。171，ItalicsGödel's）。

戈德尔在他的不完整定理中使用了当今戈德尔的固定点定理中给出的一种方法。尽管戈德尔在证明不完整定理的过程中构建了一个固定点，但他并未明确指出固定点定理。固定点定理如下：

定理2（Gödel的固定点定理）

如果φ（v0）是数字理论的公式，则有一个句子ψ，使得p⊢φ（⌈ψ⌉），其中⌈ψ⌉是与⌈ψ⌉的自然数代码相对应的形式术语。

证明：让σ（x，y，z）是一个公式，即数字表达数字理论谓词‘y是通过在gödel数字为x的公式中替换术语x的公式中获得的公式的gödel数。令θ（v0）为公式∃v1（φ（v1）∧σ（v0，v1，v0））。令k =⌈θ（v0）⌉和ψ=θ（k）。现在直接通过构造p⊢ψφ（⌈ψ⌉）。

如果理论可证明其否定，则可以从理论中驳斥句子。 Gödel所说的第一个不完整定理如下：

定理3（Gödel的第一个不完整定理）

如果p是ω的，那么有一个句子既无法证明也不可反驳。

证明：通过上述语法的明智编码，编写一个公式prf（x，y）[11]数字理论，可在p中表示，以便

n代码φ⇒p⊢prf（n，⌈φ⌉）的证明。

和

n不编码φ⇒P⊢prf（n，⌈φ⌉）的证明。

让prov（y）表示公式∃xprf（x，y）[12]。通过定理2有一个典型的句子φ

p⊢（φ↔prov（⌈φ⌉））。

因此，φ说：“我不可证明。因此，通过（3）p⊢φ，因此p不一致。因此

p⊬φ

此外，通过（4）和（2），对于所有自然数n，我们都有p⊢prf（n，⌈φ⌉）。由ω的矛盾P prf（x，⌈φ⌉）。因此（3）给出了p⊬φ。我们已经表明，如果P是ω的，则φ与P独立。

戈德尔在总结第一个定理的证据时说：“我们可以很容易地看到刚刚给出的证据是建设性的；那是……以直觉上无可辩驳的方式证明……”（Gödel1986，第177页）。这是因为，正如他指出的那样，所有存在性陈述均基于他的定理V（给出原始递归关系的数值表达性），这在直觉上是不可决的。

2.2.3第二不完整定理

第二个不完整定理确定了数字理论一致性的不可证实性。首先，我们必须写下一个表达公理一致性的数字理论公式。这很简单。我们只让con（p）为句子¬prov（⌈0=1⌉）。

定理4（Gödel的第二个不完整定理）如果P一致，则无法从P中证明CON（P）。

证明：令φ如（3）。用于推断'如果p⊢事的推理，那么p⊢0≠1'并不能超越基本数理论，因此，尽管有很多努力（见下文），请在P中正式化。 ⊢（prov（⌈φ⌉）→¬con（p）），因此由（3），p⊢（con（p）→φ）。由于p⊬φ，我们必须具有p con（p）。

第二个不完整定理的上述证明（草图）在避免形式化时很简单。严格的证明必须建立“如果p⊢事，则在P中p⊢0≠1”的证明。

值得注意的是，在戈德尔的第二个不完整定理的证明中，不需要ω的矛盾。另请注意，通过p的一致性和现在称为löb定理的事实，p pry（⌈φ⌉）表示p⊢事物，这两个事实都不是可证明的。

1936年，罗瑟（Rosser）取消了第一个不完整定理中Ω偶然性的假设，并被一致性较弱的概念所取代。 Rosser的概括涉及将固定点定理应用于公式r（x）：'对于所有z：tot to tot the be is the be is the be is the be coolige coolive the公式的gödel号码均具有Gödel编号X的证明，或者比Z的证明更短。 （具有Gödel编号的公式）X'（请参阅Rosser 1936）。

关于第二个不完整定理，该论点部分依赖于正式化我们所看到的第一个不完整定理的证明。他在1931年的戈德尔（Gödel）省略了这一步骤。他计划将第二部分的步骤包括在第二部分中（请参阅Gödel的脚注48a，1931年）。但是，他没有写它，而是转向连续性问题。[13] （第二部分也是要详细阐述其他观点：“真正的不完整理由”，以及两个定理对其他系统的适用性。）他也许并没有被迫参加看起来像是正式化的练习，而是依靠关于说服的非正式论点（成功）。但是，这一步骤被证明是一定的不平凡。正如克莱恩（Kleene）在1931年戈德尔（Gödel）的介绍中所说的那样，“当然，定理XI（一致性）的论点的想法非常令人信服；但是事实证明，细节的执行需要比预期的要多的工作和护理。” （参见第126-141页，哥德尔1986年。）最终，希尔伯特（Hilbert）和伯尔尼（Bernays）在他们的希尔伯特（Hilbert）和伯恩（Hilbert）和贝尔尼（Bernays）中给出了第二个定理的完整证明。他的1956年和勒布（Löb一般环境”（Feferman 1960/1961），对第一和第二定理进行了简洁而完全的一般处理。但请参阅补充文件：

不完整定理驳斥了希尔伯特的计划吗？

有关更详细的讨论，请参阅有关Gödel不完整定理的条目。

2.3加速定理

戈德尔（Gödel）1936年以摘要的“证明时间长度”发表的戈德尔（Gödel）1936年的“加速”定理，1936年说，虽然有些算法的句子是真实但无法证明的，但还有其他句子，但最短的证明是更长的句子，但即使是最短的句子也是如此。比预先给出的任何绑定作为句子的递归函数。更准确：

定理 5.

鉴于任何递归函数f有算术的可证明句子φ，因此最短的证明大于f（⌈φ⌉）的长度。

我们将概述的证明对证明的长度使用的特定概念很敏感。另一种可能性，以及戈德尔（Gödel）的想法是证明中的公式数量。公共汽车（见下文）在任何一种情况下都证明了定理，因此两种情况都得到解决。

证明：让F成为总递归功能。通过Gödel的固定点定理，有一个公式φ（n），指出“φ（n）在PA短中没有比F（n）的证明”。如果长度通过符号数量来衡量，这是可以使用的，因为我们只需要搜索比F（n）短的有限的证据。请注意，对于所有n，φ（n）都是正确的，因为如果φ（n）是错误的，那么将有一个简短的φ（n）证明，因此通过声音φ（n）是正确的，一个矛盾：φ （n）是真实的。这可以在PA中进行形式化，因此我们得到的结果是，对于每个n句φ（n）都是可以在pa中证明的。由于所有n对于所有n都是正确的φ（n），因此它不能在PA中具有比F（n）短的证明。

加快定理是考虑和阐述不完整定理的证据的结果。它通过简短的证据将定点技术应用于无法可靠性的概念，而不是将固定点定理应用于不可证实性的最初想法。证明的风味与不完整定理的证明非常相同。有趣的是，由于罗瑟（Rosser），它的历史可以追溯到同一年，从而消除了在第一个不完整定理中使用ω的使用；就像戈德尔的加速定理一样，罗瑟的建筑利用了简短和长期证明的问题。戈德尔从未提交过加速定理的证明。多年来，有几个相关的证据出版了，但戈德尔最初结果的第一个完整证明才在1994年由山姆公交车在他的“关于戈德尔的定理上的证据I：算术的线路数量和速度的数量”（Buss 1994）给出）。公共汽车还提供了避免自我参考的定理的第二个证明，遵循了由于Statman的一项技术。戈德尔通过公式的数量来衡量证明的长度；但是还有其他可能性，例如证明中的符号数量。莫斯托夫斯基在1952年证明了通过符号数量来衡量的加速定理的情况（Mostowski 1982）。有关类似结果的证明，请参见Ehrenfeucht和Mycieleski 1971和Parikh 1971。量度：只有一个有限的证明具有给定数量的符号，而给定数量的公式有无限的证明。