书评：被爱因斯坦视为知己的哥德尔的逻辑人生
http://www.sciencenet.cn/htmlnews/2008/10/212081.html书评：被爱因斯坦视为知己的哥德尔的逻辑人生
哥德尔思想的博大精深，“恰是远在天边的一处幽秘风景，虽令人心弛神往却难以身临其境”；所以，要领略那一处风景，“实在得有一种能够顾盼几个世纪的历史眼光才行”。
http://www.sciencenet.cn/upload/news/images/2008/10/20081015225552888.jpg人们对于爱因斯坦并不陌生，但对于被他视为知己的普林斯顿高等研究院的同事哥德尔却不甚了解。哥德尔无疑是一位智慧巨人，美国《时代》杂志评选出对20世纪思想产生重大影响的100人中，哥德尔列为第四。他的不完全性定理不仅使数学发生革命性的变化，而且改变了整个科学世界和建筑于此定理之上的哲学，还波及语言学、计算机科学、宇宙学，甚至包括法律上的“无罪推定”。对于人类来说，不了解哥德尔就不了解人类已达到的智力水平与人类智力奋斗的历程，也就无法了解我们这个世界在思想观念上已经发生或正在发生的深刻变化。
哥德尔被认为是自亚里士多德以来最伟大的逻辑学家。哥德尔定理粉碎了逻辑最终将使我们理解整个世界的梦想，同时也引发了许多富有挑战性的问题：什么是理性思维的界限？我们能够完全理解我们自己造的机器吗？我们能够搞清楚我们心智的内在工作过程吗？当对他们的研究结果缺乏逻辑的确定性时，数学家还怎么继续工作？从逻辑的发展去理解哥德尔是一种适当的方式，因此，《逻辑人生》也是对他一生的一个恰如其分的概括。
自古以来，人类一直在给知识的确定性寻找一个坚实的基础。从亚里士多德使逻辑学成为一个专门的学科开始，甚至哲学上无休止的争论也是源于对我们的知识是否有确定性以及这种确定性的来源的争论。但逻辑学家、数学家与哲学家不同，他们不满足于仅仅给知识的确定性一个形而上学的解释，他们希望用逻辑与数学为人类的知识建立一个严格的、自满自足的、与形而上学无关的基础。科学家们一直坚信，总有一个完备的公理化系统，任何命题在其中或被证明为真、或被证明为伪。有了这样一个一劳永逸的系统，任何知识都可以被证明、被推导或者被确认。
1930年初，信心满满的希尔伯特在自己的出生地哥尼斯堡接受“荣誉市民”的演说时还乐观地说：“我们必须知道，我们必将知道。”但同样在1930年秋于哥尼斯堡举行的科学哲学讨论会上，年方25岁的哥德尔在会议即将结束时宣布了那个革命性的发现——不完全性定理。简单说就是在一个稍微复杂（例如包含算术中的加法和乘法）的形式系统中，存在一些命题，我们既不能证明它是真的，也不能证明它是假的。换言之，一个定理的真假和它的可证性不是一回事。这与我们对数学的传统观念大不相同。过去对于数学中的一个问题，我们怎样确定说它被解决了呢？要么你给出一个证明，要么你给出一个反例说明这个定理不成立。这两种情形不论哪种都可以使问题得到解决。但这个不完全性定理却大大颠覆了人们对传统数学的观念，打碎了无数人的美梦，数学的“灾难”因此降临了。对此，数学家外尔哀叹道：“上帝是存在的，因为数学无疑是相容的；魔鬼也是存在的，因为我们不能证明这种相容性”。
如日中天的哥德尔此后把大部分的精力转移到了哲学思考上面。伟大的科学家成了独步一时的哲学家，是一个既入世又遁世、既雄心勃勃又固执己见的矛盾体。在走向生命终点的最后旅途中，哥德尔越来越多地崇尚某种神秘主义色彩。在他的哲学手稿中留下了这样一句话：世界的意义就在于事实与愿望的分离，即事与愿违。他生命的最后几年，因为妄想人们要毒死他而不吃饭，最终在1971年7月14日因营养不良和身体机能衰竭在美国普林斯顿医院去世。理性的逻辑学家最终却走向了它的对立面。
显然，哥德尔的科学、哲学和生活3个方面紧密地联系在了一起。正如著名的华裔逻辑学家王浩所言，“哥德尔的事迹发人深省，其意境超乎学院天地”，实在是一个值得了解的人物。
哥德尔是幸运的，尽管他是一个孤僻的遁世者、偏执狂和抑郁症患者，但赏识他的仍不乏其人。对于爱因斯坦来说，在普林斯顿高等研究院的日子，最重要的并不是科学研究，而是陪哥德尔散步回家，他们谈论哲学、物理学和政治，“彼此知心得不得了，彼此赏识得不得了”；爱因斯坦赞扬哥德尔是“自亚里士多德以来比任何人都有力地动摇了逻辑基础”的人。著名经济学家摩根施特恩说“他确实是自莱布尼茨以来，或者说是自亚里士多德以来最伟大的逻辑学家”。王浩称哥德尔定理的奠基性贡献“好比弗洛依德的心理学、爱因斯坦的相对论、玻尔的互补性原理、海森堡的测不准原理、凯恩斯的经济学和DNA的双螺旋”。
2002年8月17日，英国著名科学家霍金在北京国际弦理论会议上发表了题为《哥德尔与M理论》的报告，他说，建立一个单一的描述宇宙的大统一理论是不太可能的。这一推测正是基于数学领域的哥德尔不完全性定理。其实，这只是哥德尔思想的巨大冰山的一角，要更深入地认识、理解它，还需要更多的时间与更高的智识。
《科学时报》 (2008-10-16 B3科学 文化，原题《哥德尔的逻辑人生》) http://zh.wikipedia.org/w/index.php?title=%E5%BA%93%E5%B0%94%E7%89%B9%C2%B7%E5%93%A5%E5%BE%B7%E5%B0%94&variant=zh-cn 库尔特·哥德尔维基百科，自由的百科全书
跳转到: 导航, 搜索
库尔特·哥德尔（Kurt Gödel，1906年4月28日－1978年1月14日），数学家、逻辑学家和哲学家。其最杰出的贡献是哥德尔不完备定理和连续统假设的相对协调性证明。
目录[隐藏]
1 学术 2 性格 3 社交 4 国籍 5 其他 6 参见 [*]7 参考
[编辑] 学术哥德尔是个兴趣广泛的人。他在大学时本来修读理论物理和基础数学，后来又转研数理逻辑、集合论，但1940年代中就将注意力投放在哲学上。
大学时，哥德尔曾参加石里克小组的聚会。
1930年9月7日，他正式宣布其哥德尔不完备定理，引起当时重要数学家如冯·诺伊曼和希尔伯特等的重视。后来又钻研连续统假设，但未能完全解决该问题。
[编辑] 性格哥德尔是个要求严格的人。因此，他很多的想法在生前都没有正式发表甚至记录，要逝世后从其手稿找出。
他不喜欢谈论自己或受到注目。哥德尔曾要求王浩在死后才可以发表一篇有关他的传记。他在学术研究之外的东西，都不公开发表意见。
他亦讨厌旅行。
他自幼多病，而且从小便患了疑病症。他还患过抑郁症。后来他在普林斯顿的医院绝食而死，因为他认为那些食物有毒。
[编辑] 社交哥德尔的妻子原本在夜总会工作，还已婚。他们的婚姻遭到哥德尔家人返对，但有情人终成眷属，在1938年9月20日结婚。他们没有小孩。
他和家人感情不坏，哥德尔去了美国后还常常跟他们书信，之后接他们到美国。但其家人似乎对他了解不深：读大学时，哥德尔的兄长研习医学，从其他人口中才知道他在数学方面颇有名气。
在普林斯顿时，哥德尔和爱因斯坦成了很好的朋友。后人常将他们比较。哥德尔和爱因斯坦都在自己的范畴有极为重大的贡献，很聪明，有好奇心，直率。但爱因斯坦性格开朗外向，这点和哥德尔大相迳庭。爱因斯坦的死对哥德尔的情绪有很大打击。
[编辑] 国籍虽然他的传记列出很多国家，他通常被视为奥地利人。他出生在奥匈帝国的布尔诺，在十二岁时成为捷克斯洛伐克公民，在二十三岁时成为奥地利公民。当希特勒吞并奥地利时，哥德尔自动成为德国人。第二次世界大战后，他再次成为奥地利公民，而且取得美国公民权利。
[编辑] 其他哥德尔的大部分手稿使用加贝尔斯贝格速记法写成。
http://zh.wikipedia.org/w/index.php?title=%E5%93%A5%E5%BE%B7%E5%B0%94%E4%B8%8D%E5%AE%8C%E5%A4%87%E5%AE%9A%E7%90%86&variant=zh-cn
哥德尔不完备定理维基百科，自由的百科全书
跳转到: 导航, 搜索
在数理逻辑中，哥德尔不完备定理是库尔特·哥德尔于1931年证明并发表的两条定理。简单地说，第一条定理指出：
任何一个相容的数学形式化理论中，只要它强到足以蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题。
这条定理是在数学界以外最著名的定理之一，也是误解最多的定理之一。形式逻辑中有一条定理也同样容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上是错误的。稍后我们可以看到一些对哥德尔定理的误解。
把第一条定理的证明过程在体系内部形式化后，哥德尔证明了他的第二条定理。该定理指出：
任何相容的形式体系不能用于证明它本身的相容性。
这个结果破坏了数学中一个称为希尔伯特计划的哲学企图。大卫·希尔伯特(David Hilbert)提出，像实分析那样较为复杂的体系的相容性，可以用较为简单的体系中的手段来证明。最终，全部数学的相容性可以归结为基本算术的相容性。但哥德尔的第二条定理证明了基本算术的相容性不能在自身内部证明，因此当然就不能用来证明比它更强的系统的相容性了。
目录[隐藏]
1 哥德尔不完备定理的意义 2 不确定命题的例子 3 对哥德尔定理的一些误解 4 讨论和推论 5 第一不完备定理的证明要点 6 第二不完备定理的证明要点 7 参见 [*]8 外部连接和参考资料
[编辑] 哥德尔不完备定理的意义哥德尔定理是一阶逻辑的定理，故最终只能在这个框架内理解。在形式逻辑中，数学命题及其证明都是用一种符号语言描述的，在这里我们可以机械地检查每个证明的合法性，于是便可以从一组公理开始无可辩驳地证明一条定理。理论上，这样的证明可以在电脑上检查，事实上这样的合法性检查程序也已经有了。
为了这个过程得以进行，我们需要知道手头有什么样的公理。我们可以从一组有限的公理集开始，例如欧几里德几何。或者更一般地，我们可以允许无穷的公理列表，只要能机械地判断给定的命题是否是一条公理就行。在计算机科学里面，这被称为公理的递归集。尽管无穷的公理列表听起来有些奇怪，实际上自然数的的通常理论中，称为皮亚诺公理的就是这么一样东西。
哥德尔的第一条不完备定理表明任何一个允许定义自然数的体系必定是不完全的：它包含了既不能证明为真也不能证明为假的命题。
存在不完备的体系这一事实本身并不使人感到特别惊讶。例如，在欧几里德几何中，如果把平行公设去掉，就得到一个不完备的体系。不完备的体系可能只意味着尚未找出所有必须的公理而已。
但哥德尔揭示的是在多数情况下，例如在数论或者实分析中，你永远不能找出公理的完整集合。每一次你将一个命题作为公理加入，将总有另一个命题出现在你的研究范围之外。
你可以加入无穷条公理（例如，所有真命题）到公理列表中，但你得到的公理列表将不再是递归集。给出任意一条命题，将没有机械的方法判定它是否是系统的一条公理。如果给出一个证明，一般来说也无法检查它是否正确。
在计算机科学的语言中，哥德尔定理有另一种表述方式。在一阶逻辑中，定理是递归可枚举的：你可以编写一个可以枚举出其所有合法证明的程序。你可以问是否可以将结论加强为递归的：你可以编写一个在有限时间内判定命题真假的程序吗？根据哥德尔定理，答案是一般来说不能。
[编辑] 不确定命题的例子哥德尔和保尔·科恩得出的一些结果结合起来给出了不确定命题（既不能证明也不能否证的命题）的一个实际例子：选择公理和连续统假设都是集合论的标准公理系统内的不确定命题。
在1973年，同调代数中的怀特海问题被证明是集合论中的不确定命题。
1977年，Paris和Harrington证明了组合论中的一个命题，拉姆赛理论的某个版本，在皮阿诺公理给出的算术公理系统中是不确定的，但可以在集合论的一个更大体系中证明为真。
在计算机科学中用到的Kruskal的树问题，也是在皮亚诺公理中不确定而在集合论中可证明的。
Goodstein定理是一个关于自然数的相对简单的命题，它在皮亚诺算术中是不确定的。
Gregory Chaitin在算法信息论中构造了一个不确定命题, 即``Chaitin 随机数Ω的第n个字节是否为0"这样的命题在ZFC内是不可判定的.
[编辑] 对哥德尔定理的一些误解由于哥德尔的第一条定理有不少误解。我们举出一些例子：
[*]该定理并不意味着任何有趣的公理系统都是不完备的。例如，欧几里德几何可以被公理化为一个完备的系统。（事实上，欧几里德的原创公理集已经非常接近于完备的系统。所缺少的公理是非常直观的，以至于直到出现了形式化证明之后才注意到需要它们）[*]该定理需假设公理系统可以定义自然数。但是并非所有系统都能定义自然数。例如，塔斯基(Tarski)证明了实数和复数理论都是完备的公理化系统。[*]这理论用在人工智能上，则指出有些道理可能是我们能够判别，但机器单纯用一阶逻辑断却无法得知的道理。不过机器可以用非一阶逻辑的逻辑系统。
[编辑] 讨论和推论不完备性的结论影响了数学哲学以及形式化主义（使用形式符号描述原理）中的一些观点。我们可以将第一定理解释为“我们永远不能发现一个万能的公理系统能够证明一切数学真理，而不能证明任何谬误”
以下对第二定理的另一种说法甚至更令人不安：
如果一个公理系统可以用来证明它自身的相容性，那么它是不相容的。
于是，为了确立系统 S 的相容性，就要构建另一个系统 T ，但是 T 中的证明并不是完全可信的，除非不使用 S 就能确立 T 的相容性。举个例子，自然数上的皮亚诺公理的相容性可以在集合论中证明，但不能单独在自然数理论范围内证明。这对大卫·希尔伯特的著名的未解决的23个数学问题中的第二个给出了一个否定回答。
理论上，哥德尔理论仍留下了一线希望：也许可以给出一个算法判定一个给定的命题是否是不确定的，让数学家可以忽略掉这些不确定的命题。然而，对可判定性问题的否定回答表明不存在这样的算法。
要注意哥德尔理论只适用于较强的公理系统。“较强”意味着该理论包含了足够的算术以便承载对第一不完备定理证明过程的编码。基本上，这就要求系统能将一些基本操作例如加法和乘法形式化，例如在鲁宾逊算术Q中那样。有一些更弱的公理系统是相容而且完备的，例如Presburger算术，它包括所有的一阶逻辑的真命题和关于加法的真命题。
公理系统可能含有无穷条公理（例如皮亚诺算术就是这样），但要哥德尔定理生效，必须存在检验证明是否正确的有效算法。例如，可以将关于自然数的所有在标准模型中为真的一阶语句组成一个集合。这个公理系统是完备的；哥德尔定理之所以无效是因为不存在决定任何一条语句是否公理的有效算法。从另一方面说，这个算法的不存在正是哥德尔定理的直接结果。
另一个哥德尔定理不适用的特殊情况是：将关于自然数的所有语句首先按长度然后按字典顺序排序，并从皮亚诺公理集开始，一个一个遍历列表，如果发现一条语句既不能证明又不能否证，就将它作为公理加入。这样得到的系统是完备的，兼容的，并且是足够强大的，但不是递归可枚举的。
哥德尔本人只证明了以上定理的一个较弱版本；以上定理的第一个证明是罗梭(Russel)于1936年给出的。
基本上，第一定理的证明是通过在形式公理系统中构造如下命题
p = “此命题是不可证明的” 来完成的。这样，它可以看成是说谎者悖论的一个现代变种。
如果公理系统是相容的，哥德尔证明了p（及其否定）不能在系统内证明。因此p是真命题（p声称它不可证明，而它确实不能），尽管其证明不能在系统内形式化。请注意将p作为公理加入系统并不能解决问题：扩大了的系统中会有另一个哥德尔语句出现。
罗杰·彭罗斯声称“可被机械地证明的”和“对人类来说看起来是真的”的这一区别表明人类智能不同于自然的无意识过程。这一观点未被普遍接受，因为正如Marvin Minsky 所指出的，人类智能有犯错误和理解不相容和谬误句子的能力。但Marvin Minsky透露说库尔特·哥德尔私下告诉他，他相信人类有一种到达真理的直觉方法，但因为跟计算机式的方法不同，人类可以知道为真的事情并不受他的定理限制。
对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点也可以作如下评论：我们其实不知道p是真是假，因为我们并不（也无法）知道系统是否是相容的。因此实际上我们并不知道系统之外的任何真理。我们所确知的只有这样一个命题：
要么p在系统内部无法证明，要么该系统是不相容的。 这样的命题之前已经在系统内部被证明。实际上，这样的证明已经给出。
[编辑] 第一不完备定理的证明要点要充实对证明要点的描述，主要的问题在于：为了构造相当于“p是不可证明的”这样的命题p，p就必须包含有自身的引用，而这很容易陷入无穷循环。将要介绍的哥德尔巧妙的把戏，后来被艾伦·图灵用于解决可判定性问题。
开始的时候，每个公式或者说可形式化的命题都被我们的系统赋予一个唯一的数，称为哥德尔数。这要通过一种可以方便地在哥德尔数和公式之间（机械地）来回转换的方式来完成。因为系统足以表述“数”的概念，因此也就足以表述公式的概念了。
象F(x)这样的公式含有一个自由变量x，它们称为命题形式。一旦x被一个特定的数代替，它就马上变成一个真正的特定命题，于是它要么是在系统中可证明的，要么不。命题形式自身并不是命题，因此不能被证明也不能能被否证。但每一个命题形式F(x)都有一个哥德尔数，可用G(F)表示。无论自由变量取什么值，G(F)的取值都不会改变。
通过小心地分析系统的公理和推理规则，可以写下一个命题形式P(x)，它表示x是系统中一个可以证明的命题的哥德尔数。形式描述如下：如果x是一个可证明命题对应的哥德尔数，P(x)就可被证明，而其否定~P(x)则不能。（尽管这对于一个证明要点来说已经足够，但在数学上却不太严格。请参见哥德尔和罗素的有关论文，关键字是“omega-consistency”。
现在，哥德尔的把戏来了：一个命题形式F(x)称为不可自证的，当且仅当把命题形式F的哥德尔数G(F)代入F中所得的命题F(G(F))是不可证明的。这个定义可以形式化，于是可以构造一个命题形式SU(z)，表示z是某个不可自证命题形式的哥德尔数。SU(z)的形式描述如下：
对某个命题形式F(x)有z = G(F)，而且设y是命题F(G(F))的哥德尔数，则有~P(y)成立。 现在我们所要的语句p就可以如下定义：
p = SU(G(SU)) 直观上，当问到p是否为真的时候，我们是在问：“不可自证这个特性本身是不可自证的吗？”这很容易让人联想到理发师悖论，那个理发师只替那些不替自己理发的人理发：他替自己理发吗？
现在让我们假定公理系统是相容的。
如果p可以证明，于是SU(G(SU))为真，根据SU的定义，z = G(SU)就是某个不可自证命题形式的哥德尔数。于是SU就是不可自证的，根据不可自证的定义，SU(G(SU))是不可证明的。这一矛盾说明p是不可证明的。
如果p = SU(G(SU))的否定是可以证明的，则根据SU的定义，z = G(SU)就不是不可自证命题形式的哥德尔数。这意味着SU不是不可自证的。根据不可自证的定义，我们断定SU(G(SU))是可以证明的，同样得到矛盾。这说明p的否定也是不可证明的。
因此，p既不可证明也不可否证。
[编辑] 第二不完备定理的证明要点令p是如上构造的不确定命题，且假定系统的相容性可以在系统内部证明。我们已经看到，如果系统是相容的，则p是不可自证的。这个证明过程可以在系统内部形式化，因此命题“p是不可证明的”或者“~P(p)”可以在系统内证明。
但是最后一个命题就等价于p自己（而且这种等价性可以在系统内部证明），从而p就可以在系统内证明。这一矛盾说明系统是不相容的。
页:
[1]