|
续上文 我们曾经指出，哥德尔是亚里士多德(Aristotle)和G．W．莱布尼茨(Leibniz)以来最伟大的逻辑学家．但是，这决不仅仅是由于他的聪明才智所决定的，更重要的是数学、逻辑学发展到20世纪所面临的问题、面临的任务并由此而出现了一大批优秀的逻辑学家，哥德尔是其中最突出的代表．19世纪在微积分基础工作中出现了A．柯西(Cauchy)、K．魏尔斯特拉斯(Weierstrass)、R．戴德金(Dedekind)和G．康托尔(Cantor)这样一批大数学家，他们十分重视数学的逻辑严谨性．G．弗雷格(Frege)又建立适应数学论证的谓词演算，在逻辑学中首次引进全称量词和存在量词的概念．1900年巴黎数学家大会上希尔伯特提出了23个未解决的数学问题，其中第一个问题是康托尔的连续统假设是否成立，第二个问题是算术公理的协调性．他指出，在关于公理系统所能提出的问题中，最为重要的是：证明这些公理不互相矛盾，就是说，以它们为基础而进行的有限步骤的逻辑推演，决不会导致矛盾的结果．1900年前后，先后在康托尔集合论中发现几个令人吃惊的悖论．这样，出现了数学基础的危机，为解决这种危机，L．E．J．布劳威尔(Brouwer)提出了在数学中取消无穷对象、取消数学论证中无限制地使用排中律的直觉主义建议，由此形成了数学基础研究中的直觉主义学派．罗素提出了把数学还原为逻辑，形成了逻辑主义学派．罗素与A．N、怀特海(Whitehead)合著的《数学原理》(Principia mathematica)一书中完全应用了数理逻辑的方法，从一些逻辑概念和数学公理出发实际上推导出很大一部分数学，而这是沿着弗雷格、G．皮亚诺(Peano)的思路开始的．希尔伯特强调数理逻辑在数学基础研究中的巨大作用，但他不赞成逻辑主义，更反对直觉主义．在希尔伯特看来，悖论的根源不在于实无穷，而在于对实无穷的错误认识．希尔伯特认为直觉主义否定实无穷，否定排中律等等，是对数学“这门科学大砍大杀”，就会使数学“失去大部分最宝贵的财富”．希尔伯特及其学派制定了一个保卫数学建立其严谨基础的方案，人们称之为希尔伯特方案．这一方案是要将数学理论进行形式化处理，建立相应的形式公理系统，用有穷方法研究系统的完全性、协调性和判定性等问题．这些形式公理系统共同的逻辑基础是谓词演算，当时已证明了谓词演算的可靠性(或称一致性)，即任一逻辑定理在所有的解释(或称赋值)下都是真的(称之为普遍有效的)．但是，谓词演算是否具有完全性呢？也就是说，谓词演算中普效命题是否是逻辑定理呢？这是1920年前后人们关注的一未解决的重大问题，直至1928年在前述的希尔伯特与阿克曼的专著第二版中仍然是末获得解决的问题．1929年哥德尔肯定地解决了这一问题，证明了谓词演算的完全性定理．这一结果，对于希尔伯特方案是一有力的支持，因为它表明了希尔伯特所依据的逻辑基础是既可靠又完全的一门独立的数学理论． 哥德尔完全性定理在谓词演算的语法概念与语义概念之间架起了一座桥梁．这里语法概念指形式系统，语义概念指数学模型．这就是说，哥德尔定理是在形式系统与数学模型之间架起了一架桥梁． 形式系统的一合式公式(或称命题，也称语句)集合 S叫做协调的，如果此系统内不存在一合式公式A，使得从S出发公式A与A的否定式 A都是可证的．S不是协调的就叫它是不协调的．一不空集合M及M上定义的关系、函数等一起可以构成一结构．形式系统的一命题A，在结构M上做解释，对于这一解释而言，命题A经解释后在结构M中是真的，就称结构M为A的一模型．若S中每一命题经解释后在结构M中都是真的，就称M是S的一模型．显然，结构、解释、模型都是语义概念．依据上述概念，哥德尔完全性定理是说：对于谓词演算的任一命题集合S而言，都有： S是协调的当且仅当S有模型． 这里所讲的谓词演算是一阶古典谓词演算，也称为狭谓词演算，“一阶”是相对“高阶”而言的，即量词的变域是个体域，而不能是谓词，也不能是函数词，“古典”是相对“直觉主义”或“各种非经典或非标准”而言的． 哥德尔完全性定理是当代模型论的基本定理之一，由它导出了一系列重要结果． 还应当指出，哥德尔完全性定理是对形式系统的整体特征性定理(而不是系统内的形式定理)，这种定理称之为元定理或元数学定理．按照希尔伯特方案和当时人们的思想观念，元定理应局限在有穷方法内给出证明，排中律与无穷过程是不能被使用的．然而，这一定理是很强的，用有穷方法是不可能给出证明的．哥德尔看出了这一问题，大胆地采用无穷方法找出问题的答案，给出了定理的证明．对此，哥德尔曾在致王浩的信中说道，他解决了完全性在于他的哲学思想先进，不拘泥于有穷方法，而并不是他的数学技巧比别人高明(见 Wang Hao，From mathematics to philosophy)．在哥德尔晚年，王浩是他的最好的朋友之一，他们之间就数学基础和哲学问题有许多内容深刻的交谈． 哥德尔不完全性定理是更令人吃惊的．如前指出，不完全性是指形式算系统而言的，也可以说是指皮亚诺算术系统P而言的．哥德尔证明：如果P是协调的，则有一算术的形式命题A即A为P中一命题)，并且A与 A在P中都不可证明的．这与希尔伯特的猜想完全相反．希尔伯特猜想，不仅形式数学系统的基础逻辑——谓词演算是完全的，而且每一个形式数学系统也是完全的，特别是皮亚诺算术系统P也应当是完全的，它的命题集合总是可以一分为二，一部分是P的定理集合(即其中每一元都是P的定理，不妨把定理集合记为T)，另一部分是P的可驳集合(即其中每一元都是P的否定理，即它的否定式是P的定理，不妨把P的可驳集合记为R)．希尔伯特猜想，系统P的命题集合恰好就是T与R的并集合：T∪R．这就是说，皮亚诺公理系统巳完全刻画了算术系统．但是，哥德尔否定了希尔伯特的猜想，从而否定了希尔伯特方案．哥德尔具体地严谨地证明了存在一命题A，A和它的否定式 都不在T中，也不在R中．也就是说，P的命题集合不可能按照其元(即命题)是可证可驳的原则分为两部分，这是一重大的结果．哥德尔怎样获得这一结果呢？ 上述哥德尔不完全性定理在文献中常称为哥德尔第一不完全性定理．哥德尔还证明了另一个定理，文献中称之为第二不完全性定理，这一定理是说，如果系统P是协调的，那么它的协调性在系统P中是不可证明的．它的证明是通过把“P是协调的”这一元数学概念加以算术化，然后在P中形式化，得到它的形式公式可记为“con(P)”．我们再把第一定理的证明，即 加以形式化，也就是把(*)的整个证明在系统P内形式化，则我们应获得 (**)P con(P)→AP． 现在，设P con(P)，这时，由(**)叫将获得P AP，这就得到与第一定理相矛盾的结论．从而就得到了第二定理的证明． 哥德尔的上述结果对逻辑学和数学特别是数学基础产生了巨大的影响，使逻辑学、数学基础学在新的起点上获得了新的发展，揭示了机械的与非机械的思维活动的基本性质，论证了形式系统的逻辑标准与局限性问题，这些都是人类认识史上的重大结果．对于机械的思维活动，哥德尔在证明不完全性定理时，采用了递归方法并开展详尽的论述．根据J．埃尔布朗(Herbrand)和哥德尔的意见，S．C．克林(Kleene)对一般递归函数理论作了深入的研究，A．丘奇(Church)建立λ演算理论，A．M．图灵(Turing)建立另一种机械性思维过程，以描述算法，现在人们称之为图灵机器．人们很快就证明：上述几种机械性思维过程的概念和理论都是等价的，可以相互转换的．近年来，人们进一步发现了一系列可以相互转换的算法概念与理论，并且愈来愈展现出他们在计算机领域内的巨大作用． 关于连续统假设相对于集合论通常公理系统的协调性证明以及在证明过程中所创立的可构成性方法，是哥德尔的又一重大贡献．连续统问题是康托尔首先提出的，这涉及到无穷集合、无穷基数中一些根本问题．在许多无穷集合的比较中，以什么为标准呢？康托尔提出按一一对应来区分集合的“大小”，与自然数集合有一一对应关系的集合称为可数集合，诸如此种集合的基数定义为 ，把所有具有基数为 的集合收集在一起所组成的哪个集合的基数为 ，以此类推，可以获得无穷基数序列： 1900年夏季在巴黎举行的第二次国际数学家代表大会上，希尔伯特做了题为《数学问题》(Mathematische Probleme， Archivder Mathematik und Physik，Series 3，1，pp．44—63，213—237)的演说，提出了前面曾经说过的23个未解决的问题，向20世纪的数学家们提出挑战．其中第一个问题就是“证明连续统假设”．他说：“康托尔关于这种集合的研究，提出了一个似乎很合理的定理，可是尽管经过坚持不懈的努力，还是没有人能够成功地证明这条定理．这一定理就是：每个由无穷多个实数组成的系统，亦即实数集合R的无穷子集合(或点集合)，或者与自然数1，2，3，……组成的集合对等(即有一一对应的关系)，或者与全体实数组成的集合对等，从而与连续统(即一条直线上的点的全体)相对等；因此，就对等关系而言，实数的无穷子集合只有两种：可数集合和连续统．”他接着又说：“由这条定理，立即可以得出结论：连续统所具有的基数，紧接在可数集合的基数之后；所以，这一定理的证明，将在可数集合与连续统之间架起一座新的桥梁．”1925年，已经63岁、身患多种病的希尔伯特又提出了试图证明连续统假设的大纲，这就是他1926年的论文“论无穷”( ber das Unendiche，Mathematische Annalen，95，pp．161—190)．遗憾的是他的证明有漏洞，证明是错误的．这一切都表明连续统问题是很有意义的、难度很大的问题．1934年波兰学者W．谢尔品斯基(Sierpinski)出版他的专著《连续统假设》(Hypothese du continu)，揭示了在分析数学中有12个数学命题与连续统假设等价，有81个命题是它的直接推论．这就更突出了它的重大意义．对于这一问题，哥德尔所取得的重大进展是连续统假设与集合论的通常公理系统(包括选择公理)是协调的，也就是说，集合论的通常的公理系统(包括选择公理)推不出连续统假设的否定式．在证明过程中，哥德尔引进了可构成集合、可构成公理等重要概念．对于任意一集合S而言，集合S1叫做S的可定义子集合，如果有一公式(x1，…，xn，x)和S的元素a1，…，an，使得 S1=｛x|x∈SΛ(a1，…，am，x)｝ 成立，令S＇为S的所有可定义子集合所组成的集合．令 L0= ， (4．1) La+1=(La)＇， (4．2) 可构成公理是说，每一集合都是可构成的，常常记做V=L．哥德尔首先证明通常集合论公理(不包括选择公理)都在L中成立，然后证明，可构成公理蕴涵选择公理与连续假设．文献中常把选择公理记做 AC(Axiom of Choice的缩写)，连续统假设记做CH(Continuum Hypothesis的缩写)，并且把通常的集合论公理系统理解为策梅罗-弗伦克尔(Zermelo－Fraenkel)系统(通常简记为ZF，不包括选择公理，当把它理解为包括选择公理时，也常记做ZFC)．使用上述记号，就有 在ZF中可证明．第三步，哥德尔还证明了：V=L在L中成立．从而就得到了选择公理与连续统假设在L中成立．因为V=L并非是一真命题，只是在L中真，所以AC与CH也并非真命题，它们只是在L中真．哥德尔的结果给人们一种宽慰，不会因为使用选择公理增加不可靠性，也就是说，人们使用ZF公理所建立的数学理论没有矛盾时，再进一步地使用选择公理，即在使用ZFC时所建立的数学理论也没有矛盾．哥德尔建立的AC与ZF的相对协调性证明也是一项重大结果 哥德尔的结果还有更广泛的结论，这就是在L中不仅CH成立，而且广义连续统假设(Generalized Continuum Hypothesis，常缩写为GCH)也成立．其中GCH是F．豪斯多夫(Hausdorff)在1908年提出的，对于任意的序数a，应有等式成立．事实上，康托尔在1883年也曾说应有成立．显然，式(3)与(7)都是式(6)的特殊形式．哥德尔在前边提到的1940年的专著中证明的是V=L→ACΛGCH．他的结果较之更为广泛． 哥德尔创立的可构成方法开辟了集合论研究的新方法、新方向，文献中常称为内模型方法．1940年以后人们对它进行了系统的研究，获得了极小内模型等重要结果，在这些结果与方法的基础上，P．J．科恩(Cohen)1963年创立了力迫方法，证明了广义连续统假设、选择公理相对于通常集合论公理的独立性结果．当我们用符号“ ”表示“推不出”时，哥德尔的定理就是： 哥德尔的结果说明不可能是“否证的”，科恩的结果说明不可能是被“证明的”，因此，就是“不可判定的”了．哥德尔着重指出，从所采取的集合论公理对康托尔猜测的不可判定性的证明，“决不是问题的解决”．它仍然是当代数学的一大难题．这在某种程度可归之于纯数学的困难．此外，哥德尔说：“看来这里还含有更深刻的原因，并且只有在对它们中出现的词项(如“集合”、“一一对应”，等等)和支配这些词项的使用的公理的意义进行(比数学通常作的)更深刻的分析，才能得到这些问题的完全解决．”在哥德尔看来，如果我们所解释的集合论的原始词项的意义被认为是正确的话，那么就可以得出，集合论的概念和定理描述了某个完全确定的实在(即论域)，在其中康托尔猜测必然或者是真的，或者是假的．“因此，从今天所采取的公理得出康托尔猜测的不可判定性，只是意味着这些公理没有包括那个实在的完全描述．”他又说：“可能存在就其证明的结果来说是如此丰富的其它公理，它照亮整个领域并产生这样强有力的解决问题的方法(并且，只要是可能的，甚至可以构造地解决它们)，使得不论它们是否是内在必须的，至少应在如同任何已经完全建立的物理理论同等的意义上接受它的．”哥德尔在分析了与连续统假设有关的许多数学命题之后指出： “与大量的蕴涵连续统假设的否定似乎真的命题相反，没有一个已知的似乎真的命题蕴涵连续统假设．”因此，在新的系统中，“有可能否证康托尔猜测”． 哥德尔40年前的论断，仍然是当今集合论学者关心的课题．以S．斯拉(Shelab)为代表的一批学者提出了一条称为正常力迫的公理，由此可推出 ．但是，正常力迫公理是否具有公理的资格，也是当前人们极为关心的问题． 我们不难看到，哥德尔在“什么是康托尔的连续统问题”这一哲学论文中是紧紧抓住连续统这一难题展开的，他所揭示的观点对于数学研究是有指导意义的，他的思想极为深刻．哥德尔在他的另一篇哲学论文“罗素的数理逻辑”(Russell’s mathematicalIogic，1944)中着重分析了罗素的逻辑思想的发展，指出了数理逻辑在实际发展中曾采取的方法，“…最重要的简单类型论和公理化集合论，它们二者至少在这个范围内是成功的，即它们允许推导现代数学同时避免一切已知的悖论．但许多迹象只是更加清楚地表明，一些原始的概念尚需进一步阐明”．哥德尔进一步发挥了莱布尼茨的思想：“人类将有一种新的工具，同任何视觉工具对视力的帮助相比，更大大增强推理的能力．”哥德尔等人开创的机械思想过程的研究和现代计算机的结合正在不断地发展着新型的推理工具． 哥德尔的工作还有许多方面有引人注目的创造成果，比如：(1)加速度定理，或称证明长度定理，在1936年的论文“关于证明的长度”( ber die L nge von Beweisen)中哥德尔建立了类型、强度都逐一增加的系统：S1，S2，…，Si，Si＋1，…．主要结果是：在Sn与Sn+1(n∈ω)中都存在诸命题，它们在系统Sn与Sn+1中都是可证的．但在Sn+1的证明长度要比Sn中的长度短得多．人们认为，这一结果对于计算机科学可能产生重要的影响．(2)关于判定问题的可解情况，哥德尔发表了论文“对于理论逻辑判定问题的一个特别情况”(Ein Spezialfall des Entschei－dungsproblems der theoretischen Logik，1932)和“关于谓词逻辑演算的判定问题”(Zum Entscheidungsproblem des logischnFunktionenkalküls，1933)，解决狭谓词演算中可判定的命题类的最重要表达形式．所谓狭谓词演算的判定问题就是要寻找一个一般的方法，对于任意给定的命题，我们都可以在有穷步骤内判定它是否是可满足的．1936年，图灵证明了狭谓词演算是不可判定的．在图灵之前，人们一方面寻求可判定的特殊类，一方面寻求归约类(即将狭谓词演算的整个公式类归约到这一特定的类，如前束范式类就是一个旧约类)．阿克曼已经指出前束词归约类．这就建立了关于可满足性的可判定类与归约类之间的一个明确 都是归约类的结果(参见王浩《数理逻辑通俗讲话》，科学出版社，1981)．此外，哥德尔还对直觉主义逻辑等领域有重要工作，这里不一 一列举了． 综上，我们不难看出，哥德尔的工作影响和推动了数理逻辑近60年的发展，使它从较为分散的研究工作扩大为独立的系统的学科，并且产生了若干研究分支，对计算机科学与技术已经产生并将继续产生深刻的影响．他作为亚里士多德、莱布尼茨以来的最伟大的逻辑学家影响将是深远的． （来源：哲学园 作者：小庄编） |
|
|
