您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
如何简单清晰地解释哥德尔不完备定理?
命题,定理,公理如何简单清晰地解释哥德尔不完备定理?
发布时间:2020-12-06加入收藏来源:互联网点击:
那么,是不是说有了ep系统之后,加减法就不再是必要的了,我们可以像形式主义者所说的那样,不用再管加减法的意义,彻底抛弃传统的加减法,只需要按照ep系统去操作就可以取代传统的加减法呢?现在还是不够的。要想证明ep系统确实有取代加法算术的能力,我们需要证明两点:
ep系统的完全性:所有正确的加法算式(如2+3=5, 5+7=12等)都能在ep系统中推出。
ep系统的可靠性:所有ep系统能推出的公式,都表达的是正确的而不是错误的加法算式。(如ep系统不能推出4=1+2)
简单地说就是,可靠性保证了ep系统能推的都是正确的算式,完全性保证了正确的算式ep系统都能推出。这两条合起来保证了ep系统能完成所有的加法运算。其中,可靠性是很好证明的,只需证明ep系统的公理都是正确的,并且ep系统的推导规则是保真的(如果推导规则的前提是正确的,那么结论也是正确的)。这样由于系统内所有公式都由公理出发经过推理规则得到,而公理是对的,推理规则保证了不可能从对的推出错的,那么系统内所有公式就都是对的了。但完全性是很难证明的,事实上完全性证明是逻辑学的中心问题之一。(我暂时也不知道怎么证明ep系统的完全性...)
以上是用ep系统举例,说明了什么是可靠性和完全性。相对的,不完全性自然就是说,人们希望一个形式系统能表达某领域内所有的真命题,但这个系统做不到,即,有一些真命题是该形式系统推不出的。哥德尔不完全性定理说的就是这个。哥德尔证明了,能够表达初等数论(算术)的形式系统,总存在一些真的算术命题是它无法推出的。(这里有错,根据评论里 指出,哥德尔证明的不是这个,而是“存在一个公式,形式系统既不能推出它,也不能推出它的否定,即形式系统无法判定它”。)当然,这种形式系统比上面的ep系统复杂得多,但基本的原理就是这样。形式主义数学家希望他们的形式系统足够刻画整个数论,即能推出所有的算术真命题,但年轻的哥德尔粉碎了他们的梦想。
简单来说,这种表达算术的形式系统包含一些类似 的符号——都是我们现在经常在数学中见到的。这种包含量词 和变元 和性质 的逻辑叫做一阶逻辑。这个名称要来源于罗素的《数学原理》。在罗素悖论之后,数学家们对数学的基础展开了新的探索,罗素自己当然也不例外。他拯救罗素悖论的方式是“类型论”(见 LLLBK:据说罗素悖论有解,如何解?),将语言进行分层,最底层的就是一阶的。数学家们按照类型论纲领发展数理逻辑,自然是先从最简单的第一阶开始研究,这些研究现在被归入了一阶逻辑这个领域中。事实上,哥德尔的论文题目就是《〈数学原理〉及有关系统中的形式不可判定命题》,也就是《论罗素那本书里的系统以及相关的一系列系统中有什么推不出的命题》。
3. 定理的证明
虽然这篇论文本身艰深难懂,但思路倒是非常简明。把哥德尔证明的那个不完全的形式系统叫做PM.
首先要区分两个层次的定理:系统内定理和元定理。系统内定理就是PM能推出的公式,如 就是PM的内定理。而元定理是关于PM系统本身的定理。如“ 的首个字符是 ”就是一个元定理,“ 在系统内可推导(简称“可证”)”也是一个元定理。
显然,内定理和元定理是两个不同层次的东西。元定理陈述了一些关于内定理的事情,但内定理无法陈述关于元定理的事。但如果内定理也能陈述关于元定理的事呢,情况会怎么样?那我们就可以在系统内部用字符串表达“xxx公式不可证”,“xxx公式的首字符是 ”这种元定理。我们甚至有可能写出一个公式,它表达了“本公式不可证”。
为表达对哥德尔的敬意,把表达了“本公式不可证”的系统内公式记作G。显然,G为真当且仅当G不可证,G为假当且仅当G可证。PM系统的可靠性是毋庸置疑的——没有数学家会使用不可靠的系统。因此G是绝对不能为假的,因为这意味着G可证,即PM系统推出了假命题,这违反了可靠性。因此,G为真,但这恰好说明G不可证,这也就是说存在不可证的真公式,因此PM系统是不完全的。
因此哥德尔定理证明的关键就在于如何构造这个G。更本质地说,如何发现PM系统能表达关于它自身的元定理。我们已经知道的是,PM系统能够表达算术命题,比如1=1这种。那如果算术能够表达PM的元定理,不就说明了PM能表达PM的元定理?简单的表示就是:
PM—(表达)—算术—(表达)—PM的元层面—(表达)—PM
因此,问题的关键就落在了,如何建立算术和PM系统的元层面之间的关系。举例来说,类似 “ 的首字符是 ”这样的元定理,是否能找到一个类似 这样的正确算式来刻画?
哥德尔通过哥德尔编码的方式来完成这个任务,哥德尔编码给每个基本符号如 等等指派一个数字,如以上三个符号可分别指派1,2,3。从此出发,可以用建立数字和符号串之间的对应。用一个例子来说明:看一个最简单的公式 ,假如给定的编码是,这个公式的六个字符分别对应数字1 2 3 4 3 5,则整个公式对应的哥德尔数为 ,将这个数记为n。即,将素数从小到大排好,在它们上面按顺序写出符号对应的哥德尔数。类似地, 也是一个哥德尔数,它对应的字符串是 ,当然,这并不是一个合法的公式,仅仅是随意排列的字符串而已。根据算数基本定理,一个合数可唯一的分解为这种素数^指数的乘积,这保证了不同的公式对应了不同的哥德尔数。
而元定理“ 的首字符为 ”就能通过它的哥德尔数n的某些算术性质来表示。显然,如果能说明n的哥德尔数可被分解为 这种因式,就能说明 的首字符为 了。即,要说明n能被2^1整除,但不能被2^2整除。即,要说明:存在一个数a,使得2a=n;但不存在一个数b,使得4b=n。而这就是一个纯粹的算术命题了。这是一个直观的例子,展示了如何建立算术和PM系统的元层面之间的关系。
一个推导就是公式组成的序列,它也可以被一个哥德尔数表示,表示的方法是:如果这一推导中的公式对应的哥德尔数分别为a,b,c... 那这个推导本身就对应着哥德尔数 ,这个很大很大的数记为x。这个推导有个最终的结论公式,假设这个结论的哥德尔数是z,那么显然,x和z之间会存在一些算术上的关系(如x^2+4=z,当然要比这种复杂得多)这个关系我们记为prove(x, z)(意为x对应的序列证明了z对应的公式)。
prove(x, z)表示x是z的证明,因此,“存在x,prove(x, z)” 就表示“数z对应的那个命题(在PM系统内)可证”。这样,我们就把“可证性”这个元层面的性质也用算术表达出来了。当然,可证性对应的算术性质是非常非常复杂的,但理解起来并不难。同样的,不可证性就也表示出来了——“不存在x,prove(x, z)”。简便起见,把z的可证性表示为“provable(z)”,z的不可证性为unprovable(z)。z取不同的数,对应着不同的真假。如对于上述 的哥德尔数n,provable(n)就是假的,因为系统推不出n对应的这一公式。
由于provable是一个算术性质,因此可以被PM系统所表达。(被PM系统所表达,意为存在一个公式对应着这个性质,这不意味着PM能推出这个公式。)这个表达可能很复杂,但我们并不需要考虑这个表达的内部结构,只要抽象地表示为PROVABLE就行了。即,provable(z)这个算术层面的性质,可以找到一个系统中的很复杂的公式相对应,这个公式简记为PROVABLE(Z)。对应地,unprovable(z)对应的系统内公式记为UNPROVABLE(Z)。
上一篇:学逻辑学的真正用途是什么?
下一篇:返回列表
相关链接 |
||
网友回复(共有 0 条回复) |