先声明一件事情，其实我们现在口中的Gödel第一不完备定理说的其实是Gödel-Rosser 不完备定理，因为Gödel第一不完备定理有一些重要的补充是逻辑学家J.B.Rosser给出来 的，不过很多书籍都把Rosser的功劳给鬼隐了，但我下面还是称Gödel-Rosser 不完备定理，另外下面的形式算术是指皮亚诺算术(必须包含乘法)。 另外前几篇文章有人说哲学家不懂Gödel-Rosser不完备定理，但是根据我的经验，许多分 析哲学家对Gödel-Rosser不完备定理是十分了解的，像有一本介绍此定理的专书，就是 剑桥哲学系的Peter Smith写的。另外有一本很着名的可计算理论和数理逻辑教科书- Computability and Logic 的三位作者(G.S. Boolos等)，都是哲学家。倒是数学系的教授 ，据我所知对这个定理通常都有严重的误解，例如台大数学系有一个很爱开高微的教授， 我这届上课的时候就有说到这个定理，但整个叙述有严重的错误(台下的学生还抄得很开心 )，另外有一个台大数学系的兼任教授，专攻机率论，兴趣旁及科学史与科学哲学，在他 有一本《微积分的历史步道》，里面也有讲到这个定理，但整个叙述也是错误的，如果 你去问数学系的教授一些最基本递归论的知识，例如什麽是recursive set，什麽是 recursive enumerable set，什麽是recursively axiomatizable，其实大部分不是 专攻逻辑的教授应该都会摇摇头。 然而，欧陆的确有蛮多哲学家误解此定理，详细的情况可参考Alan Sokal的《知识的骗局 》。 回到原题，原文有几个地方的我认为是有问题的： 「 哥德尔定理表明，那种把全部数学知识与真理镶嵌在封闭的形式化、公理化演绎系统中的 理想是无法实现的。" 」 「 注：哥德尔不完全性定理由以下两条定理组成：(1)足以包括数论在内的任一形式系统中， 存在一个不可判定的公式——即一个公式和它的否定都是不可证明的。(2)足以包括数论在 内的形式系统的协调性在本系统中不能得到证明。 」 错误：不存在一个完备的形式算术系统，形式算术没有完备的无矛盾扩张。 理由：这种说法有一个严重的问题，形式算术其实是存在无矛盾扩张的。做法有很多种， 先讲一个思路，PA不完备的原因是不是因为公理不够？这不能完全说错，只是我们如果PA 只加一条axiom(称作PA_1)，递归关系和可表达性没有改变，所以仍可以找到一个不可判定 语句，同样的再加一条axiom所形成的PA_2也是一样。但考虑下面的方法：将PA公里集用归 纳定义给出无限的无矛盾扩张联集得PA*，就得到一个完备化的系统。不过根据Gödel-Ros ser不完备定理，PA*中axiom的Gödel number set变成非递归的(若否，就不完备)，根据 Church-Turing论题，不存在演算法来判定一个给定的formula是不是PA*中的axiom，也不 存在任何演算法可以确定一个有限证明序列是不是A*的证明。通俗的说，就是你不能写一 个程式来判定随便给一个formula是不是A*中的axiom，或是写一个程式来判定某一个有限 文章是不是证明，那这样的完备系统又有什麽用呢？ 简言之，Godel-Rosser不完备定理断言：PA的任何递归无矛盾扩张是不完备的，因此， Godel-Rosser不完备定理只适用於recursively axiomatizable的理论(也就是所有axiom的 Godel number set 必须 recursive)，只是大部分的通俗书籍为了避开递归论(可计算理论 )的知识，所以都把这个定理的叙述简化成不严格的说法，然後加上一些感叹和有问题的哲 学诠释，仔细去看，中文版的wikipedia对歌德尔不完备定理也是错误的，英文版的写法才 是正确的写法。顺便说一句，既然形式算术的无矛盾扩张是存在的，这样Gödel-Rosser不 完备定理给出了一个很棒的东西：得到一个有趣的非递归集! (David Hilbert大概作梦都没有想到有这种东西，他曾经给出一个连续统假设的证明计画 ，却把一个集合误为recursive set，从他在提出Hilbert第十问题的说法和以往过於乐观 的态度，似乎他把很多集合误认为recursive set) 另外原文指出： 「 奈格尔和纽曼则进一步指出：“哥德尔不完全性定理表明，即使在基本数论中也有数不清 的命题是不能用这种公理化方法解决的。无论机器设计得多麽好，运算得多麽快，它都不 能对这些问题作出回答……哥德尔定理表明，人脑的能力和结构是至今任何非生命的机器 所不能比拟的。” 」 我很好奇这两位为什麽会说出这麽荒谬的话..，因为他们据我所知他们对此定理的了解算 是深入的。基本数论中的确有很多问题根本不能用PA解决，举个例子，Paris-Harrington 定理用形式PA是证不出来的，但在增强版的PA却可以证出此定理。事实上，有许多数学家 开始热衷比一阶算术更强的二阶算术，例如宾州大学的Stephen G. Simpson，我记得最近 很红的牛津哲学家Timothy Williamson在一篇文章中有关注到这件事情。 至於「人脑的能力...」 之云云，也是有严重的问题，详见下述。 接下来谈到心智哲学的应用 「人类的思维和精神是不可能被完全模拟的。哥德尔不完全性定理告诉我们，数学认识活 动和数学思维的本质决不是形式化、算法化、程序化和机械化所能完全概括的。」 这完全是唬烂，的确Gödel-Rosser不完备定理似乎"暗示"这这样的结论，但你仔细观察 会发现，这样的观点有很多严重的漏洞和细节要补，以数学物理家Roger Penrose的论证为 例，他认为人类有一种心灵的洞察力可以判定歌德尔语句，但机器不能，但这种说法早就 被逻辑学家Martin Davis电到吱吱叫了，而计算机科学之父图灵在1947年的演讲早就指出 这种论证的漏洞，比Roger Penrose提出论证的时间早了40多年，也就是：Gödel-Rosser 不完备定理只会阻止只输出真语句的演算法，但你想想看，每个数学家都会犯错，Gödel -Rosser不完备定理并不会阻止能输出真也能输出假的演算法。(详细请参看Martin Davis 的着作Engines of Logic: Mathematicians and the Origin of the Computer)，另外华 裔逻辑学家、哲学家王浩的着作A Logical Journey: From Gödel to Philosophy中有一 篇也在谈这个论证的问题。国内的逻辑学者蔡行健教授 也有很细致的探讨：http://oldthinker.nccu.edu.tw/new_paper/paper001/21-2.pdf 原文指出： 「 人的精神与思维的主体 性地位也开始被动摇。实际上，近代的日心说与进化论并没有对人文精神和人的主体性构 成实质性的威胁，但当人的主体意识、人的精神与思维活动可以被模拟、被物化、被复制 ，甚至最终被替代时，这才是一种真正的人文精神和人道主义的危机。所幸的是，在数学 真理的後现代发展中，人终於能够坚守住关於人的本质的最後一道防线：在一切认识活动 中，人的最终主体性地位与终极性价值是无法取代和不可动摇的。这或许是数学真理观的 後现代转向对关於人的主体性及其意义的一个异质於激进的後现代解构主义立场的基本认 识论和价值论定位。 」 按照这篇文章的论证，这段话的成立是基於上面反机器论者的论证是成立的，很可惜据我 所知，还没有一位哲学家或科学家能给出一个有说服力的论证。倒是图灵机可以模拟人脑 似乎有一线曙光。(当然，这还会牵涉到很多心智哲学的问题) 呜，这篇文章其实还有很多问题，有空再谈。 -- 要怎麽将100只狸猫关在15个笼子里 而每个笼子的狸猫数量都不一样 但是 每个笼子都要有可爱的狸猫喔 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.169.227.3 ※ 编辑: Hseuler 来自: 118.169.227.3 (06/09 14:30) ※ 编辑: Hseuler 来自: 118.169.227.3 (06/09 19:57) 这个问题有趣 等我有空我会回一篇 真厉害..对，我觉得他们之所以会弄错，是因为他们参考的一些数学史的书籍也写错了. ※ 编辑: Hseuler 来自: 118.169.227.3 (06/11 22:40)