关于“哥德尔的不完全性定理”的讨论 - 2022/4/15 - 19

Paul Jorion于2007年2月建立了他的博客（https://www.pauljorion.com/blog/），就各种社会，思想和学术方面的议题与公众进行讨论。他把我的文章（https://www.pauljorion.com/blog/2022/04/12/unilog-2022-godels-incompleteness-theorem-revisited-par-yu-li/）放在了他的博客，引起讨论，我把部分法语对话翻译出来与大家分享。

对话：2022/4/15 - 17

BasicRabbit：

我开始，。。。

我感兴趣的问题是：为什么现在要重新审视一个80年前的定理？

保罗-乔里昂（Paul Jorion, PJ）在《真理如何……》的最后提出了一个答案：

“图灵在面对那些无可争辩的事实时，是否动摇了（……），但这些事实使他在工作的第一部分所做的工作失去了资格？我不知道，我所知道的是，数之间的重要关系震撼了他，他在生活世界中遇到的斐波那契数字重复出现的砖墙让他想起了一个加密系统的编码钥匙。如果这是他的疑惑，他不禁想到，人工智能的’图灵测试’是毫无意义的：如果有光之路有任何价值，就有一个编码器，而人工智能已经存在了数万年，因为它是关于我们的。”

对我来说，这才是重要的，也是基本上修正哥德尔不完全性定理的动机：这些定理对人类智能--或自然智能--和人工智能（AI）之间的关系有何说法？

从词源上看，定理是一个愿景的对象。我认为这个定义更多的是指柏拉图学派（一切皆为几何），而不是毕达哥拉斯学派（一切皆为数），对后者而言，定理更像是一个辞典的对象。(在这方面，PJ在第291页指出，是几何学家欧几里德将 "公理 "风格引入数学，即从 "看 "到 "说 "的过程(1)）。

柏拉图式的哲学家--几何学家 René Thom 在《操作的无限性和物理现实》（这篇文章我没有读过！）中写道： »根据许多哲学，上帝是一个几何学家；也许说几何学家是上帝更符合逻辑；也许毕达哥拉斯式的哲学家--代数学家亚历山大-格伦迪克（Alexandre Grothendieck，《梦想的钥匙》的作者，副标题为 "与善良的上帝对话"）会同意："根据一些哲学，上帝是一个算术师；说算术师是上帝可能更符合逻辑"？(对我来说，有关的上帝是哲学家们的既定存在，PJ在《真理如何......》中多次提到）。

虽然我一直“专业”地沉浸在不完全性问题中（现在已经超过50年了……），但我对回答你的三个问题没有任何用处（我是对我的同事柳渝说的），原因是，我一直感兴趣的不完全性问题是在集合论而不是算术的背景下，在这种背景下，人们有一种 "语义 "方式来解决这类问题（通过使用P.Cohen的强制方法构建新的集合论模型）。尽管如此，我还是想指出，我的论文指导老师Jean-Louis Krivine 提出了哥德尔不完全性定理的语义证明（凭记忆，可以在他的 "Théorie axiomatique des ensembles, PUF "末尾找到）。

对我来说，哥德尔不完全性定理提出的“哲学”问题是，人们是否能从与自指（“我撒谎”）相关的主观知识中推导出客观知识（定理）。在我看来，这就是我认为的形而上学（根据亚里士多德，对作为存在的研究）的顶端，我没有答案……

在参考书目中，你提到了芝诺悖论中的一个。如果我们查阅维基百科，这个悖论是通过发明/发现无穷小微积分解决的。PJ建议我们要小心（第274页）："让我们在求助于无限小数时谨慎些，以避免芝诺悖论为我们设置的陷阱。对于我现在的导师René Thom来说（对于跟随他的我来说......），这个悖论只能由一个连续体思想家来解决（托姆认为他也许是自亚里士多德以来第一个这样的思想家）。

也许说谎者悖论也会如此？也许数学家将不得不改变他对数学的看法？从毕达哥拉斯到柏拉图？

(1) 从 "看 "到 "说"，即从形态学到逻辑学，这个问题已经由Jean Petitot在 "Le hiatus entre le logique et le morphologique: prédication et perception"（(http://jeanpetitot.com/ArticlesPDF/Petitot_Thom_Urbino.pdf)）中 "哲学-数学 "地解决了。

关于你的问题2的第二部分（"如果不是，什么是PM不完全性的有效证明？"），我找到了Church、Tarski和Gödel（1）的 "限制定理 "的最新（和统一）证明版本。这是Patrick Dehornoy（比我强得多……）的作品，当时我认识他，第四部分阐述并证明了这些限制性定理。 一切都有动机和解释，在我看来，微妙的观点（从他的观点来看……）并没有回避，相反，系统地提出了。我想，在你关心的有争议的问题上，你也许能把自己的观点与他的观点对比(对于辩论来说，这已经太晚了： Patrick 在2019年去世了......）。

关于你的问题2：“如果不是，什么是PM的不完全性的有效证明？”

你和PJ（1）所说的哥德尔不完全性定理只是一个特例。本身是一个有趣的特例，但很明显与真正的定理有差距：见（2）和下面的内容。出现的一个问题是：这个特例能否在不使用说谎者悖论或对角线论证的情况下被证明？古德斯坦定理（连同科比和帕里斯的定理）回答了这个问题：见（3）中的证明简图，这个证明（我）觉得有点晕，（我）认为在皮亚诺算术中获得证明的希望不大（事实上没有，古德斯坦定理从皮亚诺算术中的不可证明性已由L.科比和J.帕里斯在1982年确立（4））。

一旦解决了不完全性定理的这一特殊情况，就可以很自然地考虑皮亚诺的算术，古德斯坦定理已被添加为公理。那么，哥德尔不完全性定理的一个结果是，这个新理论—其中古德斯坦定理是一个定理，因为它是一个公理—也是不完全的。

关于你文章中提到的无限倒退。

我似乎读到过（由PJ？），古希腊人不知道（因此不接受）递归证明的原则，亚里士多德对2的平方根的非理性的证明是通过回归到无穷大的论证来完成的，导致了一个荒谬的现象。

Peano的递归公理涉及自然整数（每个人都有，早在一年级就有），并说整数上的无限回归（可以用算术语言表达的回归）是不可能的。如果古德斯坦定理的证明使用了这种类型的论证，那么它很可能是对可能是无限序数的回归（我认为是这样的，但你必须咨询专家来确认）。在这个问题上，我在一支我认为被授权的笔下读到—Patrick Dehornoy的笔，目前（Wiles）对Fermat-Wiles 定理的证明使用了一个转折递归，人们还不知道（在他说这话的时候）这个著名的算术定理是否在皮亚诺的算术中得到了证明。

关于哥德尔的完全性定理。

PJ（1）："1930年，库尔特-哥德尔证明了第一个定理，表明 "一阶就哥德尔寻求对其不完全性定理进行句法证明而言，确实没有理由多说。就我而言，我不能没有这个完全性定理，它根据等式把可证明性和真理联系起来：在一个理论中可证明性=在该理论的所有模型中都是真的，这个定理具体说明了Ladrière写的："真正的陈述是公理和定理"(2)。这个定理让我--我为自己说话，每个人都看到了自己的门--给不完全性定理赋予了语义（原文如此）：总有一个尊重假设的理论语言的封闭声明（让我们说是皮亚诺的假设，以固定思想），在这个理论的一个模型中是真的，在另一个模型中是假的。在我看来，这值得解释。

在群论中（例如），很容易看到这个完全性定理的作用：为了证明换元性 "公理 « 独立于理论的公理，只需展示一个换元群和一个非换元群，这并不困难。我对算术（比方说皮亚诺的算术）产生的问题，我相信是每个接近这些完全性和不完全性问题的人都会产生的问题：天真地认为，无论谁来到这些问题中，“显然”只有一个皮亚诺算术的模型，这个模型是标准模型N，是自CP以来大家都知道的模型（指上面唤起的Ladrière的论断）。但当你再深入研究这个问题时，你会了解到像皮亚诺这样的理论从来都只有一个模型（用逻辑学家的行话说就是分类理论），它们总是有很多（甚至是无穷大）：这对我来说是相当难以消化的，但我确信你必须经历这些才能希望真正进入不完全性定理的课题。

你说 : "我希望发起一场辩论"。

我认为，为了启动认识论者和专家之间关于这个问题的辩论，有必要就我提到的几点达成共识。那么就有必要找到一个同意辩论的专家（我离这个专家还很远，非常远），也许是Druuh？我将饶有兴趣地阅读他与PJ和Yu Li的交流。

柳渝（Yu Li）：

我认为，讨论哥德尔的不完全性定理，首先重要的是，对哥德尔说什么取得共识，而哥德尔所说的就在他的1931论文中！

哥德尔的论文由四章组成，在进行完全的形式化证明之前，哥德尔在第1章概述了其证明的主要思想，第1章篇幅很短（2页），对解读哥德尔的不完全性定理的整体思想了解很有帮助！

哥德尔的不完全性定理作为整体，包括定理的“结论”和“证明”：结论是说PM（Principia Mathematica）和相关系统（如PA）是不完全的；而作为证明，哥德尔构造出一个类似于“说谎者悖论”的命题Q：“说自己是不可证的”，并将此作为PM中存在着“不可判定命题”的证据。

所以，通过解读哥德尔论文的第1章，我们可以问：

1. 类似于说谎者悖论的悖论命题Q是PM中的不可判定命题吗？

2. 哥德尔的证明有效吗？如果不是，什么是PM的不完全性的有效证明？

3. 今天重温哥德尔不完备性定理，从认识论的角度看，对我们会有什么启示？从算法理论的角度看，对解决 "P与NP « 问题以及人工智能的一些基础理论问题会有什么启示？

Druuh：

如果你不介意的话，让我们一步步来吧。一些初步的评论：

1. BasicRabbit, 你在这个帖子和之前的 "什么是名副其实的证明"（Goodstein，无限序数的转换，历史观点，等等......）的许多评论确实非常有趣，但只有数理逻辑方面的专业数学家才能欣赏其真正的价值，而这并不是这里的所有人。因此，我建议尽可能地脚踏实地。

2) Mr Jorion, 乔里昂先生，你在上一篇文章中向我索取关于 "在所有模型中可证明等同于真实 "的参考资料，这一事实表明你完全缺乏数学逻辑知识，因为这一基本结果对所有大学二、三年级的学生来说是众所周知的。既然你知道这一点，你对存在一个 "在N中为真但在Peano中无法证明 "的公式还有问题吗？ 柳渝，你对此事的立场是什么？

说到这里，我想澄清一些事情，以便没有误解，并从正确的角度开始：你所批评的是不完全性定理本身，还是哥德尔的证明？我承认我从来没有读过原始证明，而是在我还是学生的时候读过一个稍有不同的版本。

你文章中说“然而，哥德尔以惊人的轻率提出了这样的主张： ‘同样，从形式的角度来看，证明只不过是公式的有限序列（具有某些可指定的属性）’ ”。-> 为什么这让你感到惊讶？它只是来自证明的形式理论。

不完全性定理证明中的所有微妙之处在于一个纯技术性的关键点：递归理论。哥德尔的巧妙想法包括在整数中对语言的公式进行明确的巧妙编码，例如，可以得到自然整数对（a,b）的集合A，其中a是一个公式的代码，b是T中a的证明的代码，是一个递归集合。而另一个结果表明，存在一个 "代表 "这组整数对的语言公式DEM(x,y)，也就是说，A的整数对正好是验证公式DEM(x,y)的那些。

https://zupimages.net/up/22/15/fbcd.png

https://zupimages.net/up/22/15/qfsl.png

如果没有理解递归的所有细节和微妙之处，以及公式编码的巧妙之处，就无法理解该定理的证明。

柳渝：

我认为这是一个非常宝贵的机会，让我们一起讨论哥德尔不完全性定理，因为没有多少人愿意花时间和精力在这样一个困难而敏感，但又有关不同领域的基本议题上。

我先回答BasicRabbit的问题：为什么现在要重新审视一个80年前的定理？

我解读哥德尔不完全性定理缘起于我的关于P vs NP问题的研究。众所周知，P vs NP问题是计算复杂性理论（Computational Complexity Theory），乃至计算机理论的核心问题。

“计算复杂性理论”曾是众多的计算机基础课程的一部分，我有机会多次关于此内容的教学经验，但却是我前所未有的“奇怪”的经验，因为每次讲完课不久，我没有什么感觉，脑子一片空白，只剩下几个流行定义：P，NP，NP-完备性，就更不用说学生们的感受了。

一次偶然的机会，因读到中国哲学家周剑铭关于中西文化比较的一篇文章与他相遇，说起我教“计算复杂性理论”课的“奇怪”经验，他说你的感觉有道理，因为这里面涉及到形式与内容的纠缠。

于是我们开始长达10年关于P vs NP问题的合作研究：我们解读了提出P vs NP问题的Cook的原文，发现Cook在其证明中引入Oracle导致的认知混乱；我们借鉴了中国传统逻辑中的一个著名命题”白马非马“，以澄清当前定义中P与NP的层次混淆。

但是到后来，我依然感觉遇到了“瓶颈”：我们知道NP与“不可判定问题”密切相关，这是图灵1936年论文的主题，但是却被流行的“停机问题”所代替了。问题是， “停顿问题”并没有能够为“不可判定问题”提供启发性的理解，而从我们的角度来看， “不可判定问题” 与“NP问题”密切相关，。。。

因读到PJ一篇关于“白马非马”的博文，我与PJ相识，得知他质疑哥德尔不完全性定理，让我意识到对“不可判定问题”的追究应该回到哥德尔那里，于是有了现在我和PJ重新审视这个80年前的定理的合作：我主要从算法和逻辑的角度解读，而PJ主要从知识论的角度解读。

正如我所建议的，为了使我们的讨论具有建设性，让我们首先关注哥德尔在他的论文中说什么，至于PJ说什么和我说什么，目前都不是重点，否则我们有可能陷入死胡同的争论，…