>>>  史地研究雜志方面文獻收集  >>>

簡體     傳統

---

　　中图分类号：B81　　文献标识码：A　　文章编号：1006-5261(2008)02-0034-03
　　形式系统的完全性是指系统的有效公式都是该系统的定理，即该系统的所有有效公式在该系统中都可证，否则就是不完全的。1929年，逻辑学家哥德尔(Kurt Gdel)证明了一阶逻辑系统的完全性，即哥德尔完全性定理。然而，1930年他又证明了算术系统PA的不完全性：如果形式算术系统PA是相容的，则必定存在闭公式G及其否定G在此系统中均不可证，即如果PA是相容的，则必定存在闭公式G和G在PA中可表达，但却不能证明它们是PA定理。这就是哥德尔不完全性定理。
　　根据语义，如果G在系统PA中是可表达的，那么根据排中律，G不是真的就是假的，即要么G真要么G真。但是，“可证”与“真”是两个相似却根本不同的概念，因为由G或G在PA中为真，不能证明二者之一在PA中必然为真。
　　我们这里首先简介哥德尔不完全性定理，然后澄清关于哥德尔不完全性定理的一些认识，并探讨哥德尔不完全性定理的价值和意义。
　　1　哥德尔不完全性定理
　　哥德尔不完全性定理的证明过程精细而繁复，极具技巧性。它的知识背景是一个形式算术系统PA，包括一阶逻辑系统和五个皮亚诺(G.Peano)公理。在证明中，哥德尔首先通过可表达性、递归性和哥德尔数进行了两步转换。
　　第一步是给PA的每一符号、公式和证明序列都指定一个不同的自然数，即哥德尔数，目的“是为了把关于形式系统内的对象的断定，转换为关于自然数的断定，也就是说，通过编码，使得对象理论的好些性质都能够在自然数中反映出来，尤其是，有关对象理论的元定理也都可以表示为自然数的定理”[1](P78)。哥德尔数都是自然数，反之则不然。
　　第二步转换是第一步的逆过程，是通过可表达性和递归性再把关于自然数的断定转换为PA中可表达的公式。设f是定义在自然数N上的任一函数或关系，m和n都是任意自然数，则f(m，n)在PA中“可表达”就是“直观算术函数可以通过哥德尔数‘翻译’(映射)为PA中的公式”[２](P97)。但是，任意f在PA中都可表达吗？哥德尔证明了凡递归函数或关系在PA中都是可表达的。
　　这两步转换，先把PA公式转换为自然数，再把自然数转换为PA公式，有什么意义呢？前面区分的两个概念“可表达”与“可证”有助于这里的理解。第一个转换是把PA的元命题真假断定转换为自然数命题的真假断定，而第二个转换却是将自然数命题的真假断定转换为PA的可表达公式。这样，经过两步转换，PA就成了其自身的元系统，断定内容有了十分重要的改变：由对命题真假的断定转换为对可表达性的断定。这两步转换对于在不完全性定理的证明中使用自指命题但又避免悖论是十分关键的。
　　在两步转换之后，哥德尔构造了一个自指命题G。这是极为关键的，原因是哥德尔不完全性定理的证明必须在PA中找到一个闭公式G，使得G和G在该系统中都不可证。语义上，G和G必有一真。有一真但又不可证，就意味着PA没有包容所有真命题，即系统PA是不完全的。最后，哥德尔证明，G与G都是PA的不可证命题，即证明了不完全性定理本身
　　或许有人会问，把自指命题G作为新公理加入PA，形成一个PA的扩充系统PA′，PA′不就是完全的了？事实并非如此。哥德尔证明，增加一条新公理，并没有改变递归关系及其表达性，因为按相似的程序，可以在PA′中找到另外一个不可证命题G′，从而PA′也是不完全的。因而，哥德尔不完全性定理又可扩充表述为：对任一足够丰富的相容的形式系统S，必定存在闭公式G′以及G′在S中可表达，但却不能证明它们是否是S定理。这里的“足够丰富”指系统S必须丰富到包含一阶算术系统PA，它既可以真包含PA又可以等于它，但不能比PA简单，否则就有可能是完全的。
　　哥德尔还给出了不完全性定理的另一种证明：既然真句子集A不能在PA中得到全部表达，而PA的可证命题集B能够表达，足见B是A的真子集。因此，存在真命题G在PA中不可证；既然G真，其否定G也应当在PA中不可证。哥德尔指出，这种证明的缺点是没有摆出一个不可判定命题，而且其中也要明显地求助于集合，会引起直觉主义者的异议。但是，没有一个不可判定命题会让人缺乏某种实在感，更重要的是，不完全性定理表明公理集合论也是不完全的，如果再用集合来证明不完全性定理，则显然会出现循环。
　　哥德尔不完全性定理有一个推论：任一包含一阶算术系统的系统S的相容性，在S自身中都不可证。此推论又称哥德尔第二不完全性定理，而前述不完全性定理又称哥德尔第一不完全性定理。
　　2　对哥德尔不完全性定理的几种误读
　　当前，谈论哥德尔不完全定理已成为学界的时髦，遗憾的是，其中有一些讨论是在没有真正理解和把握哥德尔定理的基础上进行的。
　　第一，有人认为哥德尔完全性定理与不完全性定理中的“完全性”是不同的。例如，《纠正对哥德尔定理的几个误解》一文认为：“哥德尔完全性定理表明一阶逻辑是完全的，即对任何一阶语言的公式φ，φ由Γ‘可证’和φ是Γ的‘语义结论’是重合的。”[3]这一观点可表示为
　　，
　　特别地，当Γ是空集时，有
　　，
　　可见，此“完全性”中的语义有效公式与语形可证公式之间是“当且仅当”的关系。但是，哥德尔的完全性是指“是否初始设定的公理系统和推理规则事实上能够得到每一逻辑数学命题，或者是否可以想象，在所考虑的系统里可能存在不能得出的真命题”[4](P583)，也就是说，哥德尔考虑的完全性是指所有的有效公式是否都可证，应该用公式表示为
　　，
　　也即在哥德尔完全性定理中，有效公式与可证公式之间只有“如果……那么”的关系，而不是，即无“一阶逻辑系统的可证公式都是该系统的有效公式”之意。其实，“”是指可靠性。可靠性和完全性都是形式系统的重要性质，缺少哪一个，形式系统就不完善，但可靠性与完全性不是一回事。
　　不完全性定理的完全性与完全性定理的完全性是一致的，否则就是不完全的。不过，完全与否，是相对于系统而言的。相对于一阶逻辑有完全性，而相对于一阶算术系统以及复杂性超过算术系统的系统就没有完全性，即具有不完全性。
　　第二，哥德尔语句会导致悖论吗？我们经常看到有人论证哥德尔语句会导致悖论。英国学者霍金(S.Hawking)极具代表性，他说：“哥德尔定理是用自我指认的方法证明成立的。这种命题会导致悖论。例如，如果一命题真，那么可合乎逻辑地推出其假；如果一命题假，那么可合乎逻辑地推出其真。”[5](P25)但是，霍金的这个观点却是错误的。的确，哥德尔语句与说谎者的悖论句极其相似，但二者却根本不同。张建军教授在《逻辑悖论研究引论》中对此做了清晰的比较和分析，即
　　L：L是假的：
　　G：G在PA中是不可证的。
　　看起来好像G只不过把L中的“假”换成了“在PA中是不可证”，即把一个语义概念换成了语形概念，但是，后者并不像前者那样导致悖论。要理解其缘由，主要是要理解我们前面对语义概念“真”与语形概念“可证”“不可证”所做的区分。设L是假的可得L真，再设L为真可得L是假的，这就得到了悖论。循此思路，如果我们设G是假的，即“G在PA中是不可证的”是假的，那么可得G在PA中可证为真，这就意味着G是PA中的真理，这样就从G假推出了G真；但是，如果设G真，即“G在PA中是不可证的”，由此却推不出G假，因为G在PA中不可证并不意味着G一定为假。可见，由哥德尔语句G得不出悖论。
　　第三，哥德尔不完全性定理表明心胜于机器吗？哥德尔和他的工作越来越受人垂青，与计算机和人工智能的发展有关。“他最着名的定理表明了数学的不可穷尽性，确定了形式系统(或计算机程序)的局限性，所以与心是否胜过机器这个脍炙人口的问题有了关系”[6](P184)。持“心胜于机器”观点者认为，既然哥德尔不完全性定理表明复杂的形式系统中存在该系统内不能判定的公式，而人心却可以凭借直觉判断出该公式的真假，那么就表明人心胜过机器。与此相似，哥德尔本人也曾提倡“理性主义的乐观主义”，他的推理也与上面相似：人的理性不会一面提出理性不能回答的问题一面又坚持只有理性才能回答这些问题，可见，没有人心不可判定的问题；但数学系统已经极其完善，因此人心胜过机器。但是，哥德尔后来承认他的定理没有了结心胜过机器的问题[6](P185)。之所以如此，是因为哥德尔不完全性定理一方面表明了形式系统的局限性，即任一足够复杂的形式系统都有在其自身不可证的真命题，但另一方面，它也显示了形式系统的巨大威力：低层次的不可证命题可以在高一层次中得到形式证明。可见，哥德尔不完全性定理并没有直接表明人心是否胜过机器。之所以会产生“心胜于机器”的论点，可以说是因为无视哥德尔不完全性定理所显示的形式系统巨大威力的结果。
　　3　结语
　　哥德尔不完全性定理影响深远，它直接摧毁了希尔伯特(D.Hilbert)最初设想的数学目标，使元数学摆脱了虚幻的目标而走上了健康发展道路。
　　哥德尔定理处在整个逻辑学的中心地位。“哥德尔教授的工作已经引起现代逻辑的革命，从数学上也从哲学上大大提高了它的重要性。他所做的数学与哲学出奇地意味深长，美，超脱宿怨。在逻辑的一切现有分支里，他的工作都是基础和生命力”[6](p34)。哥德尔在证明不完全性定理中使用的一些概念，如真、可表达、可证、有效、哥德尔数、递归等，现在都是逻辑学中的基本概念；哥德尔定理的一些思想促成了一些分支学科的大发展，如递归论，证明论等。当前，国际上已将哥德尔不完全性定理赞誉为现代逻辑科学在哲学方面的三大成果之一(另两个为塔斯基的形式语言的真理论和图灵机与判定问题)。
　　最新的事例足以说明不完全性定理的深远影响。2004年，英国学者霍金发表文章《哥德尔与物理学的终极》，放弃了其研究了多年的终极性万有理论：万有理论不存在，永远找不到这种理论。霍金说，他是在仔细重新研读了哥德尔不完全性定理后，才改变了自己的观点，哥德尔定理“很明显”表明万有理论是不可能实现的。
天中学刊驻马店34～36B3逻辑贾国恒20082008
不完全性/真/可表达/可证
　　incompleteness/true/expressible/provable
Comment on Gdel's Incompleteness TheoremGdel's incompleteness theorem is getting more and more attention, but some solutions are wrong, need to be cleared off. Gdel's incompleteness theorem lies in the core of the whole logic, has important promotion roles on many subjects, and is even the source of some subjects.
哥德尔不完全性定理越来越受到人们的垂青和重视，但有些却是错解，需要予以澄清。哥德尔不完全性定理是整个逻辑学的中心，对其他许多学科也有重大的促进作用，甚至是有些学科的发端。
作者：天中学刊驻马店34～36B3逻辑贾国恒20082008
不完全性/真/可表达/可证
　　incompleteness/true/expressible/provable

网载 2013-09-10 21:42:55

驗證：