首页 > 代码库 > 哥德尔不完备定理

哥德尔不完备定理

自从牛顿用物理的直觉,闯进无穷领域里大胆计算,铸造出犀利无比的分析工具后,许多人凭借着直观想象和聪明,也涌进去推导出许多互相冲突的结论,数学家花了两百多年的时间,才厘清了分析领域里的混乱,将整个数学建立在严格逻辑,而不是直观想象的基础上.

欧几里德几何一直是科学理论的范本,四条自明性的公理加上一条平行公设,通过逻辑演绎,推导出平面几何无穷数量的定理,一直到了近代还只有几何,被认为是具有坚实基础的数学分支,在这光辉的榜样下,人们尝试用这公理化的方法来规范整个数学,人们后来发现欧几里德也不够严谨,逻辑上的漏洞得以修补,但追到极致,要依赖于“数”的理论.

自然数的算术运算是数学的最基本的内容,自然数的性质曾经被中国先哲看成天道的机密,古希腊人作为宇宙的根本,在笛卡尔的哲学沉思里,认为我们无法判断自己是清醒还是幻觉.

1910-1913年,罗素和怀特海出版了三卷的<<数学原理>>,他们自信已将全部的数学建立在纯逻辑的基础上,为今后的所有数学打下了坚实的基础.

当时数学界领军人物希尔伯特,提出一个计划,根据<<数学原理>>的思想,将所有的数学形式化,称为形式公理系统,在这里用精确的形式符号语言来叙述数学命题,根据形式逻辑的规则来操作这些字符串的变换和生成,称之为“形式证明”.

这个系统如果有完备性,相容性,保守性和确定性,数学研究从此不再需要创造性的工作了,一切定理的发现和证明,归结为在这个形式公理系统下的机械运算.

这个形式公理系统计划,关键的一个环节是相容性的绝对证明,相容性指系统不能产生自相矛盾的结论,过去所有科学理论的相容性,实际上并没有得到过逻辑的证明,结论依赖于客观的经验来验证,客观的事实是确定的,不矛盾的,这保证了结论的相容性.

欧几里德几何虽然以公理化的方式,用逻辑推出所有的定理,它依赖这些公理是自明的,即符合直觉,也就是符合实际的空间经验,所以认为是真理,但这在逻辑上是不完全的,直觉只是经验的印象,怎么保证没有想象之外的事实?

希尔伯特用笛卡尔坐标的解析几何,将欧几里德几何的相容性,用代数系统的相容性来保证,但代数系统的相容性该怎么得到保证?这仍然没有得到最后的解决.

希尔伯特认为必须构建“绝对”的证明,即这个系统的相容性不再借助其他系统来保证,在抽去具体含义的形式化系统中,相信这个只包含逻辑结构和功能的系统,容易在一览无遗中寻找各个命题字符串之间的逻辑规律,而不需要依赖于不可靠的直觉和经验,从而来证明相容性,这个证明希望只用到有限次推理,每次只用到有限个数学的对象.

1931年,哥德尔发表了一篇论文,<<论数学原理及相关系统的不可判定命题>>,让这希尔伯特的计划成为泡影.

哥德尔根据<<数学原理>>构造出一个简单的包含着皮亚诺算术公理的形式演算系统,称之为PM,哥德尔定理有两个结论,这结论对任何包含有自然数加法和乘法的形式公理系统也成立:

1.PM如果是相容的则是不完备的.

2.PM不能证明自身的相容性.

相容的,或者译为“一致的”或者“自洽的”,意思是说在这个系统里不能推出互相矛盾的结论,因为,若有一对相反的命题(比如,a=b和a≠b)同时为真,那么由它们可以合乎逻辑地推出任何命题(为真),所以数学系统只有是相容的才有价值,相容的系统里至少有一个命题不能被证明(为真).

完备性,指所有的真理(语义上为真的命题),都能在这个系统里被形式证明(从系统里的定理或公理,按照形式逻辑的方法通过有限步骤推导出来).

这是数学里最具有革命性的定理,它告诉我们公理化固有的局限性,哥德尔虽然只证明了在那个包含有PA的简单PM系统,但是它适用于任何包含自然数加法和乘法的数学系统.

又有哪个足够大的数学系统不包括这算术运算?

哥德尔在琢磨这个提供了严谨的形式逻辑基础,将数学命题形式化的<<数学原理>>时,他发现了一个秘密,这形式逻辑的操作与算术运算极其相似,如果将形式符号的式子对应于一个自然数,那么形式逻辑的运算就对应于算术的运算,这系统用形式逻辑来描述算术,但算术也可以来描述形式逻辑的过程,它可以合法地自己来谈论自己,这让人想起“这句话是错的”这个古老的谎言悖论,那么,我们可以用<<数学原理>>的规则将“这个公式是不可证明的”,这个谈论数学公式的命题,形式化变成系统里的数学公式,造成一个恶性循环来摧毁这座精巧构建的纯洁的大厦.

哥德尔要在形式公理系统里,放进一个“自我纠缠”的魔鬼,用系统里的公式表达“这个公式是不可证明的”含义,构造一个不可判定的命题,如果他做到了,这系统若是相容的就是不完备的(这不难推出,读者可以想一想),他的想法来自于法国数学家理查德1905年的语义悖论.

理查德悖论的一个变种是这样的:

用语言描述一类自然数的算术性质,模仿公理化的方法,从基本概念开始,依定义过的内容来描述新的定义,这些定义的内容总是用有限个字符来表达,比如说,定义了整数,乘除法后,定义“平方数是某个整数的自乘”,“质数是只能被1和自己整除的数”等等,把这些定义按描述句子的长短和字典顺序排列成一个表,这里每一个定义,在表中的序号是一个自然数,例如“质数是只能被1和自己整除的数”的序号是19,“平方数是某个整数的自乘”的序号是50,对照定义和它的序号,不外乎有两种情况:一类是这序号恰好符合定义的描述,例如序号19,它是质数,有定义的性质,另一类是这序号不具有定义性质的情况,例如,50不是平方数,没这性质,将这些不具有定义性质序号的数定义为“理查德数”,这样,50是理查德数,19则不是,理查德数是在这系统中有明确数学性质定义的一类自然数,它的定义也可以在这表中,假设它的定义对应着序号n,问:n是不是理查德数?论证一下,若n不符合它所对应的定义,按照理查德数定义的描述,n应该是理查德数,这是说n是符合理查德数定义了,即n符合它所标号的定义,这就和初始的假设矛盾了.

这个悖论说明,即使对自然数的算术性质,用任何语言,包括形式语言来定义,也可能发生矛盾,这悖论有些疵瑕,但即使这个表长有限,矛盾仍在,重点是它与1901年的罗素悖论有着相同的逻辑结构,而罗素悖论与谎言悖论都是因为自我纠缠惹得祸.

哥德尔有一套计算可形式化的“原始递归函数”理论,将元数学里的命题:“哥德尔数为x的公式序列,是哥德尔数为z公式的形式证明”,对应着算术计算,映射成PM里的公式,这个带有自然数变量x和z的公式简记为Dem(x, z).

哥德尔用Dem(x, z),构造一个PM的公式G,它表达元数学的命题:公式G在PM内是不能被形式证明的.

在构造新公式前,还需要介绍一个关于哥德尔数的函数表达式,假如在哥德尔数为k的公式中,有个自然数变量y,哥德尔数是17,将自然数k的PM表达SSS…SSS0代入这公式中所有y变量出现的地方,这个新公式的哥德尔数记为sub(k, 17, k).

哥德尔努力显示这个置换操作是可计算的,sub(k,17, k)是原始递归函数,它对应的PM字符串的表达式,记为Sub(k, 17, k),比如说k对应的公式是?x(x=Sy),代入后的新公式Sub(k, 17, k)是?x(x=SSSS...SSS0),这里SSSS...SSS有k+1个S,他的哥德尔数是sub(k, 17, k).

在Dem(x, z)前加一个存在的量词(?x)Dem(x, z),对应着元数学里:存在着一个x,它是z的证明,简言之,z是可证的,其否定式~(?x)Dem(x, z)对应着z是不可证的.

将哥德尔数函数sub(y, 17, y)代入~(?x)Dem(x, z)中的z,有:

公式1: ~(?x)Dem(x, Sub(y, 17, y))

这PM公式直接的含义是数学命题:不存在着一个哥德尔数x,它满足dem(x, sub(y, 17,y))的算术关系,他对应着元数学里的命题:哥德尔数为sub(y, 17,y)的公式是不可证的.

设公式1所对应的哥德尔数是n,这是一个确定的自然数,将它代入公式1的变量y,便有

公式G: ~(?x)Dem(x, Sub(n,17, n))

记哥德尔数g = sub(n, 17,n),这也是一个确定的自然数,公式G对应着元数学里的命题:哥德尔数为g的公式是不可证明.

这g对应着哪个公式?

sub(n,17,n)是置换操作后新公式的哥德尔数,这新公式是将哥德尔数为n的公式,即公式1里的变量y用n代入,这正是公式G,公式G的哥德尔数是g.

因此,公式G对应着元数学里的命题:公式G是不可证明的,公式~G,即:(?x)Dem(x, Sub(n,17, n))则对应着元数学里的命题:公式G是可证明的.

我们已经把自我纠缠镶进了公式G,嘘一口气,慢慢消化这个公式和对应的含义,然后往下看这证明的辩驳,如果细心推敲,你可能会有些疑惑,这很正常,需要慢慢消化,哥德尔的证明手法很不寻常,当大数学家冯·诺依曼得知哥德尔证明时大为赞赏,细究之后,两次宣布找出了证明中的错误,后来他又两次修正了自己的错误,他惭愧地看到自己由这个插曲,轻易地改变了关于数学绝对真理的看法,而且相继改变了三次.

哥德尔用反证法证明在PM里,公式G是不可判定的,假如公式G可证,这件事的元数学陈述是:公式G是可证明的,~G对应的正是这句话,说明它是可证的,反过来,假如~G是定理,这公式对应的元数学命题“公式G是可证明的”为真,这元数学的判断是:PM里可以证明公式G,即公式G是定理,因此,公式G是定理,当且仅当公式~G是定理.

PM是相容时,这种情况是不允许的,所以上述导致矛盾的假设都不成立,G和~G在PM里都不可证,也就是不可判定的.

G是不可证明的事实,说明元数学描写G的命题是真理,它对应着这公式G的含义为真,PM里一个表达真理的公式G,不能在PM里被证明,说明PM是不完备的,这在元数学里就证明了.

下面证明:相容性是不可能在PM里证明的

回顾一下“相容性”的含义,它说系统里一个命题和它的否定不能同时是定理,这是数学系统无矛盾性的要求,如果不是这样,在系统里就可以证明任何的命题成立,所以“相容性”等价于,系统存在着一个命题,它是不可证明的.

证明:

我们构造一个新的公式:A (?z)~(?x)Dem(x, z)

这个公式对应着元数学的直接解读是,存在着一个公式z,不存在着公式序列x是它的证明,即,有一个公式,它是不可证明的,即,PM是相容的.

公式G是否也有类似的解读呢?它的直接元数学的解读是:公式G是不可证明的,我们已经从元数学证明:命题G是真的,它是真的又不能在PM里证明,这正是“PM是不完备的”的意思,所以,公式G的另一个解读是:PM是不完备的.

元数学里的定理说:如果PM是相容的,则PM是不完备的,对应着PM里的公式:

(?z)~(?x)Dem(x, z) ->~(?x)Dem(x, Sub(n, 17, n))

也就是说,如果我们能够在PM里证明它是相容的,(?z)~(?x)Dem(x, z)公式为真,按照上式和PM里三段论推理的分离规则,推出~(?x)Dem(x, Sub(n,17, n))为真,即在PM里证明了公式G,这与公式G在PM里是不可证的事实相矛盾,所以公式A不能在PM里被证明.

下面证明:PM不能证明自身的相容性

这里沿用了PM公式与元数学对应关系的简化证明思路,如果PM是ω-相容的,则是不完备的.

ω-相容的的定义是,对于算术谓词P,(?x)P(x)和每一个自然数k的~P(k)不能同时为真,而相容的则是,对于任何命题p和~p不能同时为真,ω-相容的是个较强的要求,它能够推出相容的条件,ω-相容的的定义里~(?x)P(x)和每一个自然数k ~P(k)在语义理解上是同一回事,但在形式系统里,因为没有一个能处理无限的规则(希尔伯特计划中有限主义的限制),所以,不能把他们看成是一样的.

证明:

假设G可证,这说明有个PM公式序列是G的证明,设这个公式序列的哥德尔数为k,这元数学命题对应着数论命题dem(k, g),已知g = sub(n, 17, n),所以有dem(k, sub(n, 17, n)),他陈述了一个算术的事实,表示为PM的公式Dem(k, sub(n, 17, n)),这说明它是PM里的定理,有一个具体的数k满足这关系,逻辑上说明存在着一个数x满足这关系,也就是(?x)Dem(x, sub(n,17, n))能够被证明,这公式是~G,这说明从G可证,可以推出它否定形式~G也可证,从而,如果PM是相容的,G在PM里不可证.

假设~G在PM里可证,如果G不可证,也就是对于所有的k,dem(k, g)都不是事实的,即~dem(k,sub(n, 17, n))都是真的,所以,~Dem(k, Sub(n, 17, n))对每一个的自然数k都是个定理,~G可证意味着(?x)Dem(x, Sub(n, 17, n))是PM里的定理,如果PM是ω-相容的,这是不可能的,从而,如果PM是ω-相容的,~G在PM里不可证.

因此,如果PM是ω-相容的,G是不可判定的,不可判定的命题,根据排中律,G和~G必有一真,但在PM里都不能证明它们,所以PM是不完备的.

哥德尔不完备定理