哥德尔不完全定理与数学认知的局限性

打开文本图片集

摘 要：哥德尔不完全定理揭示了数学认知的局限性，任何一个含有初等数论及一阶谓词逻辑的形式证明系统中，都存在这样的命题，在此（封闭）系统中，依靠系统中的公理及一阶逻辑演算方法，既不能证明该命题为真，也不能证明它为假。哥德尔在定理的证明中开启可计算理论（递归论）之门，用现在成熟递归论的结果重新认识哥德尔不完全定理，使其变得更容易接受。近年来，机器学习取得突破性成果，由此引发有关人工智能是否可以完全代替人的思维能力等热点问题讨论。针对这一问题，如果承认“人工智能”是在一个交互计算系统中完成的，那么哥德尔不完全定理给出的是否定回答。

关键词：数学认知；递归论；形式系统；哥德尔不完全定理

中图分类号：O141.1

文献标识码： A

人类文明的进步体现在对自然和社会认知的推进，数学作为一种抽象的表达工具，在认知过程中起到重要作用。伴随着数学的发展，人们对自然和社会发展规律具有更深刻的认识。在数学发展的历史长河中，不同时代的数学家们都力图想用一个统一的数学系统“一统天下”。早在古希腊时期，毕达哥拉斯学派认为“万物皆数”（这里的数指有理数），结果发现直角边长为1的等腰三角形的斜边长（2）无法用有理数表示，由此产生第一次数学危机，从而导出无理数的产生[1]。用现在数学的眼光看，实数集R中有理数部分仅占很小的一部分，稀疏到测度为0。

到了二十世纪初，希尔伯特曾经有一个宏伟计划：想为全部的数学提供一个（排除悖论在外）安全的理论基础，让所有数学证明过程能够统一到一个形式系统中，按照一套通用规则，完成任意一个真命题的证明。不幸的是哥德尔不完全定理的出现，完全毁灭了这个美好的愿望。

1 哥德尔不完全定理概述

1931年，著名数学家哥德尔（Gdel）提出形式系统的不完全性理论，具体内容包含两个定理[2-4]：

第一定理：任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，在这个系统中，既不能证明该命题为真，也不能证明它为假。

第二定理：如果形式系统S含有初等数论，当S无矛盾时，它的无矛盾性不能在S内证明。

初等数论是指建立在自然数集合N上的算术系统，其运算包括普通的加、减、乘、除法运算、其命题涉及数的性质、数之间的关系等。当然，其中的减法和除法需要作一些简单限制，保证运算封闭。一阶谓词逻辑主要提供一个符号化描述语言及形式证明方法，以其合式公式描述一个合法的命題（判断）陈述，以其形式推理描述一个命题的形式化证明过程。

形式系统需要一个描述语言L，初等数论指Peano算术系统，Peano算术系统中公理集是由真命题构成的一个递归集。在严格的数学语言表达下，哥德尔得到的不完全定理可陈述为[3]：存在语言L中的一个命题描述σ，满足如下条件：

（a） 如果Peano算术系统是协调的，则σ不可证明；

（b） 如果Peano算术系统是ω-协调的，则σ不可证明。

其中，协调性指不存这样的命题，在系统内能同时形式推导出命题本身及其否定命题。

哥德尔不完全理论被称为20世纪最有意义的数学真理中最杰出、最具有代表性、最有震撼力的发现，是现代逻辑史上一座重要的里程碑。哥德尔不完全性定理告诉我们： 真与可证是两个概念。可证的一定是真的，但真的不一定可证。通俗地说，真的只保证存在性，但可证你得给出证明过程。

哥德尔不完全性定理的影响远远超出了数学的范围，它不仅使数学、逻辑学发生革命性的变化，引发了许多富有挑战性的问题，并且涉及到逻辑学、哲学、语言学、计算机科学、宇宙学、乃至当今的热点话题——人工智能。2002年8月17日，著名宇宙学家霍金在北京举行的国际弦理论会议上发表了题为《哥德尔与M理论》的报告，认为建立一个单一的描述宇宙的大一统理论是不太可能的，这一推测也正是基于哥德尔不完全性定理。

从辩证的角度看：可解是相对的，依赖于形式规则系统；不可解是绝对的，即任何界定规则系统中，都存在这样的问题，在该系统中不能机械地完成它的求解（证）过程。正如尺规问题的不可解性，仅用直尺和圆规不能三等分任意角，但适当修改规则是可以做到的[5]。从这个意义上讲，哥德尔不完全定理的出现是合情合理的。

针对近年来机器学习取得的突破性成果而引发有关人工智能是否可以完全代替人的思维能力等热点争论问题，如果承认“人工智能”是在一个交互计算系统中完成的，那么哥德尔不完全定理给出的是否定回答。

2 数学危机推动数学认知

在数学史上，曾经发生过三次数学危机，每次数学危机从产生到解决都带来一次数学认知的飞跃[1]。危机的出现，表明数学描述的认知规律尚有漏洞；危机的解决不仅是补漏，更重要的是将数学认知推进更深层次。

2.1 第一次数学危机： 无理数的发现

危机发生于大约公元前400年左右的古希腊时期，起源于根号2的发现，到公元前370年左右，以无理数的定义作为危机结束的标志。在此之前，古希腊毕达哥拉斯学派认为“万物皆数”。源于对长度、重量和时间等简单度量的需要，用整数商表示分数建立有理数体系，当时认为用有理数就能足够表达了这些实际量度。但是，边长为1的正方形的对角线的长度表达却超出了有理数系。这冲击着当时希腊人持有的“一切量都可以用有理数表示”的观念，并建立无理数概念以解决第一次数学危机。现在看来：以直线上的点所表示数，除有理数表示的点之外，尚有更大更精彩的空间。

2.2 第二次数学危机：无穷小量的表述与微积分基础定义的争论

危机发生在十七、十八世纪，围绕微积分诞生初期的基础定义展开的争论，这场危机最终完善了微积分的定义和与实数相关的理论系统，并基本解决了第一次数学危机时关于无穷计算的连续性问题。微积分的应用推向所有与数学相关的学科加以应用，得益于这场大讨论。

其实，这次危机的萌芽出现在大约公元前450年，芝诺注意到由于对无限性的理解问题而产生的矛盾。芝诺的关于时空的有限与无限的四个悖论中，“两分法”悖论最为著名：向着一个目的地运动的物体，首先必须经过路程的中点，然而要经过这点，又必须先经过路程的1/4点……，如此类推以至无穷。结论是：无穷是不可穷尽的过程，运动是不可能的。

芝诺揭示的矛盾是深刻而复杂的。经过许多人多年的努力，终于在17世纪晚期，形成了无穷小演算——微积分这门学科。在微积分大范围应用的同时，有关微积分基础的问题也越来越严重。关键问题就是无穷小量究竟是不是零？无穷小及其分析是否合理？由此而引起了数学界甚至哲学界长达一个半世纪的争论，造成了第二次数学危机。

直到19世纪20年代，一些数学家开始关注微积分的严格基础。从波尔查诺、阿贝尔、柯西、狄里赫利等人的工作开始，到威尔斯特拉斯、戴德金和康托的工作结束，经历了半个多世纪，基本上解决了这些矛盾，为数学分析奠定了一个严格的基础。

危机并不可怕，第二次数学危机不但没有阻碍微积分的迅猛发展和广泛应用，反而让微积分在各个科技领域得到广泛应用，解决了大量的物理问题、天文问题、数学问题，极大地推进了工业革命的进程。

2.3 第三次数学危机：集合论中悖论的发现

危机产生于十九世纪末和二十世纪初，当时正是数学空前兴旺发达的时期。危机源于在康托尔对集合的描述性定义中被发现存在悖论。1897年，福尔蒂揭示了集合论中的第一个悖論。1902年，罗素发现了著名的罗素悖论，由集合概念本身就能直接描述这个悖论：定义满足性质“x x”的对象全体构成一个集合A={x " x x }。那么，A作为一个对象，是否在集合A中？即“A∈A”是否成立？如果成立，那么它应该具有性质“AA”； 如果它不成立，就应该有“AA”，即A作为对象满足集合A要求的特征性质，从而有“A∈A”。

由于数学的基础描述工具是集合论，罗素悖论使整个数学大厦动摇。弗雷格在收到罗素的信之后，在他即将要出版的《算术的基本法则》中写道：“一位科学家不会碰到比这更难堪的事情了，即在工作完成之时，它的基础垮掉了，当本书等待印出的时候，罗素先生的一封信把我置于这种境地”。于是，终结了他十多年的刻苦钻研。

解决第三次数学危机的方法是引入公理集合论，数学家们通过将集合的构造公理化，以排除上述类似集合的存在性。此后，希尔伯特曾经的宏伟计划中，为建立安全的数学理论基础，首先是将悖论排除在外。

7 Gdel不完全定理的简化版本——递归公理系统的不完全性

本节给出哥德尔不完全定理的一个简化版本——递归公理系统的不完全性，其不完全性定理的证明直接来自于“真命题集TP不是r.e.集”。实际上，由定理6.5，TP是一个产生集，系统中的不可证明命题不仅存在，而且可以由TP的产生函数对应的算法产生出该命题的编码。从而否定回答第6节中的问题2：是否存在一个以真命题集TP的某个子集为公理的形式证明系统，在此系统中，可以证明TP中每一个命题？

在前述含有初等算术的一阶逻辑语言L下，一个形式证明系统是一个序对（A，D），其中A是命题集S的一个子集，作为系统的公理集合；D是S中由公理可证明的形式证明下严格定义的集合。

考虑系统（A，D）满足如下条件：

（1a） “证明”可有限描述，从而一个证明可以编码成一个自然数；

（1b）如果公理集A是递归的，则问题 “p是来自公理集A某个命题σ的一个证明”是可判定的。

这样的公理证明系统称为递归公理证明系统。借助于编码技术，集合A和D可以视为两个自然数子集，则A和D都是递归集。

我们现在可以将第6节中的问题2解释为：

（2a）A是一个递归集；

（2b）真命题集TP中的可证明的命题是指：利用公理A对其进行证明的命题，其证明可以“精准描述”。

在上述限制下，第6节中的问题2可以解释为：是否有一个递归公理系统（A，D），真命题集TP每一个命题都是可证明命题？

形式上，在这种“精准描述证明”的意义下，考虑证明系统（A，D）的两个基本性质：

（2b1） 协调性：不存在命题σ，使得σ，σ都可证。

（2b2）完全性：对任意的命题σ，或σ可证明，或σ可证明（σ可反驳）。

于是，不完全性是指：存在命题σ，σ和σ都不可证。即σ成真不可证明，成假也不可反驳。

由于可证明和可反驳都是需要算法支撑的，所以，哥德尔不完全定理在递归系统下考虑是合理而自然的。这样一来，递归论的方法就能用上。

引理7.1 在任意一个递归证明系统（A，D）中，可证明命题集Pr是一个r.e.集。

证明 设Pr是真命题集TP中可证明命题集，由于证明都可以有限描述，则Pr是一个能行枚举集。由于公理集A是递归集，则下面定义的谓词M（x，y）是可判定谓词。

9 结束语

哥德尔不完全定理所述的Peano算术系统是一个递归系统，借助于哥德尔编码技术，将可以有限描述的命题对象、形式证明编码成自然数，则问题讨论转移到自然数集上。于是，递归论中的工具和结论可以熟练运用。

本文基于递归论的一些基本结果解读哥德尔不完全定理及其证明，文章中的相关结果主要来自文献[3]。全文中一个关键性的递归可枚举（r.e.）集合K={x：φx（x）↓}及其补集K作为产生集的性质起到重要作用，其中集合K本身的定义来自于对角线思想。

在证明过程中，结合可证明命题集关联指标集Pr*，以及可反驳命题集关联的指标集Ref*都是r.e.集的性质，利用伴随于产生集K的产生函数的全可计算性，哥德尔不完全定理中所需要的自身及其否定均不可证明的命题σ：=m—K— 可以能行构造。

为方便读者理解哥德尔不完全定理及其证明，文中比较全面地罗列了相关背景、基础知识和处理方法，部分内容略显多余和重复。

一个数学系统或体系总是在一套公理假设和一套形式推演规则下建立起来的，新结果的推导和结论的重用不断地丰富这一体系，但其“根”还是在公理系统和推演规则，只要系统的协调性还在，一切形式推理的结果都连着这个“根”，哥德尔不完全定理表明：基于一个协调的封闭数学系统，其认知有其局限性。从辩证的角度看：可知亦可解的问题对象不过是相对的存在，不可知亦不可解的问题对象是绝对的存在。

哥德尔不完全定理的内涵及应用涉及领域较多，限于水平，作者不敢妄加評述。近年来，机器学习取得突破性成果，由此引发人工智能是否可以完全代替人的思维能力等热点问题讨论，针对这一问题，作者认为：如果承认“人工智能”是在一个交互计算系统中完成的，那么哥德尔不完全定理给出的是否定回答。

参考文献：

[1]胡作玄.第三次数学危机[M]. 成都：四川人民出版社，1985.

[2]360百科.哥德尔不完全性定理[EB/OL].[2018-04-28].https：//baike.so.com/doc/6603875-6817662.html.

[3]CUTLAND N. Computability——An introduction to rescurisive function theorem[M]. Cambridge： Cambridge University Press， 1980.

[4]杨东屏. 哥德尔不完全定理的剖析[J]. 曲阜师范大学学报， 1993， 19（1）： 31-36.

[5]R·柯朗，H·罗宾. 什么是数学[M]. 左平，张饴慈，译. 上海：复旦大学出版社，2004.

[6]ARORA S， BARAK B. Computational Complexity——An Modern Approach[M]. Cambridge： Cambridge University Press， 2009.

[7]WEIHRAUCH K. Computable Analysis——An Introduction[M]. Berlin： Springer-Verlag， 2000.

[8]M.戴维斯. 可计算性与不可解性[M].沈泓等，译. 北京：北京大学出版社，1984.

（责任编辑：周晓南）

推荐访问:定理 局限性 不完全 德尔 认知