您好、欢迎来到现金彩票网!
当前位置:ag视讯 > 哥德尔配数 >

漫谈哥德尔不完备性定理

发布时间:2019-06-27 03:14 来源:未知 编辑:admin

  哥德尔揭示了在多数情况下,你永远不能找出公理的完整集合.每一次你将一个命题作为公理加入,将总有另一个命题出现在你的所能形式证明的范围之外.你可以加入无穷条公理到公理列表中,确保所有命题都可证明为真或假,但此时将没有机械的方法判定给定是否是系统的一条公理.

  1. 形式系统最早的数学定理都是用自然语言写的,但随着数学的内涵越来越丰富,自然语言在表达数学概念时显得越来越啰嗦,比如要描述一个物体的运动过程,七言万语的文字绝对比不上一个公式的简洁直观(为了简化表达,数学家们开始越来越多地用符号来表达数学概念,这种情况发展到极端后自然语言被彻底地抛弃,数学完全的符号化,这种语言就称为形式语言!比如我们高中学过的逻辑与命题里面的各种逻辑连词,谓词等等

  数学家又发现人的推理过程是可以看做符号变换的。比如『已知命题A,又已知命题A能推出B,那么B成立』这条规则可以抽象为 A, A→ B ↣ B [1]。这样一来数学证明可以完全变成机械的符号变换游戏,哪怕你不懂这些符号什么意思,只要你记住规则,就能证明出一个个数学定理。这听起来非常诱人,于是数学家制定了形式语言的语法,把符合语法的句子称为命题,又选出一组命题称为公理,最后制定了一组推理规则,这样给你公理,根据推理规则,你就可以推出许多被称为定理的命题。这套系统就被称为形式系统。从公理推出定理的过程就被称为证明,推出命题否定形式的过程自然就被称为证伪

  仔细想想,这里面其实有个问题:我们怎么确定这套推理系统是对的呢?换句话说,我们怎么知道推出的命题是真命题呢?理论上说,数学可以完全无视现实世界,从任意的公理出发推出任何命题,但我们还是希望我们研究的数学能解决现实问题,所以我们要确保我们的形式系统确实是在描述我们想要的数学理论。为了解决这个问题,数学家为形式语言建立了语义,换句话说,就是把形式语言的符号翻译成我们已知的东西[2],这样如果推出的命题翻译过来是错的,那么我们就需要修改推理规则,直到其语义符合预期。而符合语义的命题我们就称为真命题。后来逻辑学家发现,一种叫一阶语言的形式语言有非常好的性质,用一阶逻辑表达的形式系统,不管你给公理什么语义,只要公理都为真,那么所有能推出的命题都是符合这个语义的真命题,所以现在大部分形式化的数学理论都用一阶语言表达,包括目前数学的基础:ZFC公理集合论。

  既然形式系统这么好,那么能不能把所有数学都形式化呢?以后也不用费脑子证明了,直接扔给机器穷举,一吨吨的数学定理就造出来了。

  他畅想了一个美好的未来,所有的数学理论全都用一种形式语言来描述,并且这套系统满足如下四个性质——

  完备性:任意一个符合这个形式系统语法的句子,也就是一个命题,都能证明或证伪。

  这个想法倒是非常美好,但就在希尔伯特退休后一年,即1931年,哥德尔的两条不完备定理直接宣判了希尔伯特计划的死刑。

  先来解释一下皮亚诺算术是什么。皮亚诺算术是一套用一阶语言描述的形式系统,它被用来刻画自然数以及基本的自然数算术,比如加法、乘法和乘方。那『包含皮亚诺算术的形式系统』是什么意思呢?直观上理解,就是说从这个形式系统中,可以推出一组命题,这些命题可以描述自然数以及算术。比如ZFC集合论就是包含皮亚诺算术的系统,你可以用 {1}, {2} {3}... 来表示1、2、3……,用集合操作来模拟自然数上的运算,所以有些命题是不能在ZFC中证明或证伪的,ZFC也不能证明自己是一致的;再比如图灵机也是一个包含自然数的形式系统,而停机问题可以理解为这个系统里无法被证明和证伪的命题。

  哥德尔的两个不完备定理直接戳破了希尔伯特的梦想:包含算术的形式系统不可能完备,而且这个系统本身的一致性不能在系统内被证明。后来图灵的停机问题又摧毁了希尔伯特对可判定性的期待。

  显然不是的。比如平面几何,你不能从平面几何推出皮亚诺算术,因为平面几何是个完备的理论。而且哥德尔给出的『包含皮亚诺算术』的限制其实都很强了,给一个弱得多的限制,理论依然是不完备的。哥德尔提出第一不完备定理后不久,Rosser就给出了一个更强的(更强的意味着限制更弱)不完备定理:一个系统只要包含罗宾逊算术就足以产生不完备性了(罗宾逊算术只有加法和乘法)。哥德尔当时强调皮亚诺算术(原文其实更模糊,是『基本算术』),主要是针对希尔伯特计划。希尔伯特想把所有数学都形式化成一套系统,然后把证明归结成基本的自然数算术,再在这个系统内证明自然数算术是一致的,这样就完成整个数学的形式化,结果被哥德尔无情打脸。

  另外,哥德尔不完备定理其实还有个隐藏限制,那就是形式语言的公式集必须是递归集合,换言之,你的公式必须可以从有限个符号经过有限步构造出来。如果你用像实数那么多的符号来表示,哥德尔不完备定理就失效了,但这毫无意义,因为人类没办法写出这种语言。同样的,如果你能造出『实数计算机』,那停机问题也可以解决了。

  这么说倒也没错。哥德尔的证明是先把形式语言编码成自然数,然后证明『所有自然数代表的公式集合』是比『能推出的所有公式的编码集合』更大的集合[6],所以总有公式是证明不出来的。如果理论用自然语言描述,自然语言没有确定的语法,也就无法编码了。但是如果你不能精确定义语言,你也无法精确定义『证明』、『真』这样的概念,又怎么保证你证明得对呢?而且用形式语言和用自然语言描述的理论本质是一个东西[7],这就好比一个命题不管你用汉语说还是英语说,真假都一样。所以形式系统的不完备性也可以当做直觉上数学理论的不完备性。

  另外用形式语言可以起到区分元理论和对象理论的作用。元理论是指描述这个形式语言的理论,而对象理论是用这个形式语言来描述的理论。其实我刚才说『一个命题不管你用汉语说还是英语说,真假是一样』是不准确的,比如『这句话是汉语』这句话,翻译到英语就是假的,但是这句话其实是一个元理论的命题,它描述了写『这句话是汉语』的语言本身,所以它不是汉语这个系统内的命题。再比如上一段中『哥德尔的证明是先把形式语言编码成自然数,然后证明「所有自然数代表的公式集合」是比「能推出的所有公式的编码集合」更大的集合』这句话,句中的『证明』和形式系统里的『证明』就不是一个层面的词。如果数学命题都用自然语言描述,就会出现很多元理论和对象理论混淆的情况。

  这得从哥德尔本人的哲学立场说起。哥德尔是个柏拉图主义者,在柏拉图主义者眼里,数学对象都是永恒存在于独立于现实世界的理念世界里的。既然数学天然存在,那推理就不是数学定理存在的前提,而是发现数学的工具。这就好比人们根据天王星的轨道偏差推理出海王星的存在,不能说海王星因为人的推理而存在。所以,虽然哥德尔用了算术知识来证明不完备定理,但不能说不完备定理依赖算术而存在。这只表示哥德尔相信他用的知识是必然正确的,他用这些知识推理出一个对数学世界普遍成立的规律。

  但很多数学家认为数学就是从公理中推出来的,是人类思维的创造。如果站在这个立场,那哥德尔确实有循环论证之嫌:他在算术里讨论了一个元算术的性质。所以这个定理更多地被视为哲学或逻辑学定理而不是数学定理[9]。注意这不是说哥德尔证错了,只是说哥德尔已经到数学和哲学之间模糊的边界了,甚至可以说他是在数学外观察数学。至于到底什么是数学,现在没人能回答得了,大部分数学家也不在乎这个问题,ZFC作为数学基础已经足够好了,空谈主义并不能帮助数学家解决实际问题。顺便一提,现在倒是有不少计算机科学家在做数学基础的研究……

  一般来说,不管什么哲学立场,不管讨论多么基础的对象理论,元理论都会包含一点基本的算术,否则我们连定义符号、语法都不行,形式化更无从谈起。

  5. 计算机是个不完备的形式系统,但是人能证出哥德尔不完备定理,是不是说明人脑比计算机强?

  这是个广为流传的误解。计算机是可以证明哥德尔不完备定理的,Lawrence C. Paulson就用Isabelle这个软件证明了哥德尔不完备定理[10]。虽然目前计算机只能处理形式化的数学,但是你可以先形式化一些基础的结论,然后把其他数学理论在这个形式系统里再形式化一遍,最后证明这些形式系统内的形式系统有不完备性。顺便夹个私货,作为物理主义者,我相信人脑理论上是能用图灵机模拟的,但是能不能造出来、或者造出来能不能被人理解就不好说了。

  6. 物理学需要数学,哥德尔不完备定理是不是意味着我们永远无法理解宇宙?

  这个问题不好说。我倾向于认为哥德尔不完备定理和物理没多大关系。首先,物理定律只是在用数学,而不是创造数学。假设你发现了宇宙最基本的定律,几个方程组可以求出一切物理量,那你也不需要用这个方程组推出自然数、有理数等概念,只要它们能描述你观察到的一切现象就行。再者,宇宙里所有粒子或别的什么基本单元也可能是有限的,你给它们用自然数编号,哪怕一个粒子用一个公式描述,那也是递归集,并不会有不完备性。

  最后选取不同的数学基础,可以把语言翻译到不同的数学对象上。由于目前ZFC是大多数数学家公认的基础理论,所以标准语义都把变量翻译到一个被称为论域的集合上,把函数和关系符号翻译成论域上的函数和关系,这样的标准语义也被称为模型。研究标准语义的理论被称为模型论

  递归集是指『某元素是否存在于该集合中』可以用算法判断出来的集合。至于什么叫『算法』,[0]里提到的数理逻辑教材都有讲。另一个相似的概念是递归可枚举集,指在集合中的元素可以用算法判断出来,但判断元素不在集合中可能会让算法死循环

http://bed-plans.net/gedeerpeishu/448.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有