“哥德尔不完备定理”到底说了些什么？——（三）

已有 16254 次阅读 2017-7-18 19:03 |个人分类:科学|系统分类:科普集锦| 数学, 逻辑, 哥德尔, 不完备定理

    “哥德尔不完备定理”到底说了些什么？——（三）

第三重：“惊鸿一瞥”——“哥德尔不完备定理”的概要证明思路

首先恭喜开始修炼第三重神功的读者，相信你们已经对“哥德尔不完备定理”有了足够的理解了，现在我们开始进入到“哥德尔不完备定理”的证明思路中。

哥德尔在25岁就发表了这篇伟大的论文，但是哥德尔这个人却是一个很谨慎细致的人，他知道自己这篇论文可能带来的影响，因此他非常担心别人没有读懂它，或者引发什么误会。为此，在这篇论文的第一部分Introduction中，哥德尔概括但细致地给出了整个证明的思路。

不过，在我们理解哥德尔的证明思路之前，让我们先从更简单、更易懂的方式入手来逐步进入状态。

（一）悖论式语言

喜欢搞点逻辑类脑筋急转弯的读者可能了解一些悖论式的语言，譬如“这句话是谎话”。这句话到底对不对呢？如果说它对，那么它就真的是谎话了，既然是谎话，那么显然是不对的；如果说它不对，就意味着它不是真话而是谎话，显然它又对了。对可以推演出不对，不对却可以推演出对，这种语言可以称之为“悖论式语言”。由此，我们可以给出一个结论，能用语言表达的语句中，一定存在既不能说明它对也不能说明它错的句子。于是我们可以说，语言体系的逻辑表达是不完备的。

如果有人以为这就证明了“哥德尔不完备定理”，那未免太天真了。这种逻辑悖论在几千年前就被人们发现了，如果像希尔伯特、罗素等大数学家、逻辑学家连这个问题都搞不定，还有什么资格去推进数学公理化和公理体系形式化呢？

其实，这种悖论式语言在《数学原理》所定义的形式化公理体系中是无法表达的。设这句话（看作一个命题）为X，那么“这句话是谎话”就应该表达为“~X”。而悖论式语言需要把“~X”定义成X自己，也就是让“X=(~X)”，这是无论如何也不可能通过《数学原理》中的四条基本逻辑推演公理推演得到的结论。所以，这种悖论式语言只能证明“人类的语言体系逻辑表达不完备”，而并不能证明“公理体系不完备”。但是，这个思路和哥德尔的证明是有着相通之处的。

（二）罗素悖论

如果小时候对数学与逻辑感兴趣，也许会记得那个“只给不给自己理发的人理发”的理发师？这个悖论其实就是罗素悖论，只不过为了让人容易理解，把抽象的罗素悖论给改头换面了一下。罗素悖论是集合论中的一个经典悖论，我们把若干具有同一性质的对象划分为一个类，类中的这些对象被称为类的元素，当然，某些情况下类里面的元素也可能是一个类。现在我们设计某一种性质P(x)= x∉x ，也就是说具有性质P的对象不是自身的元素。那么，满足性质P的类为A={x|x∉x}。此时，如果我们想判定A这个类是否是A自身的元素时，悖论就出现了，如果A∈A，根据性质P，得到A∉A；如果A∉A，那么A就满足性质P，则A∈A。

罗素悖论是不能仅仅归因于语言表达的不严谨的，事实上这是一个实实在在的悖论，是关于类的公理体系必须要解决的问题。后来，人们修改了类的内涵公理，并提出了一个新的概念——集合。集合是能够成为某一个类的元素的那种类。由此，我们把类分成了两种，一种是集合，另外一种是真类（不能成为任何类的元素的类）。由于罗素悖论与“哥德尔不完备定理”的证明没有直接关系，因此本文不再讨论它了，有兴趣的读者可以自行深入了解。

之所以在这里谈到了罗素悖论，是因为希望读者知道，当公理体系引发了悖论之后，人们马上就会通过定义新的概念、提出或者修改公理来完善它。可是，当哥德尔的证明也构造出了类似悖论的命题之后，人们宁可接受这个命题是不可证明的，也没有试图通过修补公理体系来解决这个问题。因为通过哥德尔的方法构造的这类命题，使得人们无论定义多少个概念、补充或修补多少个公理，也无法消除它。

（三）哥德尔证明思路

哥德尔的证明思路和前面那些制造悖论的思路类似，都是要把命题自身引入到命题之中。区别在于哥德尔既不是利用了某种语言的不严谨，也不是简单地把命题变量直接代入到自身，而是严格按照公理体系形式化的要求，一丝不苟地把命题自身引入到这个命题之中，其论证过程天衣无缝、无懈可击！

需要说明的是，哥德尔的证明所使用的公理体系是基于《数学原理》中提出的形式化的公理体系，哥德尔在论文中把这个公理体系称为PM（Principia Mathematica），我们在后面也会沿用这个名字。

（1）建立命题表达式与自然数的对应（哥德尔对应）

哥德尔做的第一件事是把PM中的表达式和自然数对应起来。我们在讲解“一致性的重要意义”的时候，专门介绍了PM中的表达式和相应规则。PM中的表达式就类似下面的这些例子：

~ (∃z≤x ∙ (z≠1∧z≠x∧z|x))∧(x>1)    （判断x是否为质数的PM公式）

∀q∙p⇒(~p⇒q)         （我们证明过的公式，矛盾的体系可推出任何命题）

哥德尔说，这些表达式都是由一些基本符号组成的，是一组符号序列；而“证明过程”无非就是一组表达式组成的序列，是符号组成的序列的序列。按照希尔伯特的数学形式化思路，这些符号、表达式和“证明过程”都是无意义的，如果需要，可以赋予某种含义来表达一些现象。哥德尔指出，显然把这些符号赋予什么含义是与PM体系本身无关的，因此在这里哥德尔把这些符号对应为自然数。

于是，每一个基本符号都对应于一个自然数，每一个表达式则对应于一个自然数序列，每一个“证明过程”都对应于一个自然数序列的序列。反过来，每当给出一个合规的自然数序列，就可以唯一的对应一个PM表达式；每给出一个合规的自然数序列的序列，就可以唯一的对应一个PM证明过程。

再深入一步，有了这种对应后，就可以把一些对PM表达式或者证明过程的有含义性的判断对应成对于某一个自然数序列的判断，而这类对自然数序列的判断显然又可以使用PM中的表达式来进行。换句话说，通过哥德尔建立的对应，我们终于可以使用PM表达式来表达有含义的判断了。比如，根据事先对应关系的定义，一个合法的表达式对应的自然数序列一定满足某种规则，这种规则显然可以在PM中表达，于是我们就可以在PM中给出一个表达式，用来表达“某个表达式是否合规”这个含义。

由于这种对应（也被称为哥德尔对应）对于“哥德尔不完备定理”的证明非常关键，我们宁可不厌其烦地再举个很简单例子来使读者能够准确理解它。我们建立一种类似哥德尔说的对应关系，事先声明，我们建立的这个对应关系仅仅是为了容易理解下面的例子，实际上这个对应关系并不利于证明“哥德尔不完备定理”。我们建立的对应关系为，把PM体系中的全部合规表达式以及证明过程按照ASCII字符顺序排列，形成一个无限长的序列；然后从第一个表达式开始，我们把它对应到自然数1，第二个对应3，以此类推，直至无穷；然后再把全部不合规的表达式排列好顺序，从第一个开始，分别对应到自然数2、4、6、……。这样，PM中的任意表达式及证明过程都对应着唯一的自然数。我们再定义一个PM表达式，这个表达式用来判断某个表达式是否合规，设这个表达式为isFm(x)。显然，这种对应关系下的isFm(x)在PM中应为“~(∃z ∙ x=2z)”（注意PM中的任意数字变量都是0或自然数），这个表达式实际是判断x是否为奇数，如果是，则对应x的表达式合规，否则不合规。于是，一个“表达式是否合规的有含义的判断”被表示为PM中的一个表达式了。

当然，除了表示“表达式是否合规”外，也应该还可以表示“某个表达式是否在PM体系内可以证明”，哥德尔把这种表达式设为provable(x)，他表示自然数（或自然数序列，或自然数序列的序列，修炼第四重时会看到，哥德尔采用一种巧妙的方法把这些序列们都对应为唯一的自然数了）x对应的表达式是否可在PM体系内证明。

最后，再强调一点，哥德尔把PM中的表达式对应为自然数，并不是哥德尔为了研究自然数或者数论而做的什么工作，而是哥德尔为了构造某种特殊的PM表达式而提出的方法。通过把PM表达式映射为自然数，再利用PM体系自身本来具备的表达自然数间关系的能力，来实现把PM中的命题引入自身的目标。

（2）构造一个特殊的命题表达式

哥德尔定义，“在PM命题表达式中，只有一个自然数类型的自由变量的那种表达式称为class-sign（考虑到这只是哥德尔起的一个名字，就不翻译了）”，比如“x>10”、“∃z∙z<x”、“∀y<x,z<x∙ ~(x=y∙z)”等等，这些都是class-signs，都只有一个自由变量x且x是一个自然数。

下面，我们给每个class-sign分配一个序号，并设第n个class-sign为R_n。当我们把某个自然数k代入到某个class-sign的变量时，得到的表达式记为R_n(k)。例如，若R₉是“∃z∙z<x”，那么R₉(8)就是“∃z∙z<8”，R₉(9)就是“∃z∙z<9”。

再设provable(R)表示R这个命题表达式可以在PM中被证明（前面已经提到了）。大家知道，有些表达式是可以在PM体系中证明的，比如“3<9”、“~(x>10∧x<8)”，有些表达式是不可证明的，比如“3>9”、“(x>10∧x<8)”。因此，provable(3<9)为真，provable(x>10∧x<8)为假。

然后，我们定义一个集合K，K={n|～provable(R_n(n))}。也就是说，K是这样一组自然数的集合，集合中的元素n使得R_n(n)不可证（注意这里面的R_n(n)是把命题表达式R的序号带入到它的自由变量中得到的表达式）。

基于上述定义，必然存在一个命题表达式S(n)，它表示n∈K，而且显然这个表达式是一个class-sign。既然S也是一个class-sign，那么S也必然有一个对应的序号，设这个序号为q，则S就是R_q。如果我们把R_q的序号q带入到R_q中，就得到了表达式R_q(q)，这应该是一个可以在PM中表达的表达式。

最后，我们来考察表达式R_q(q)和~R_q(q)是否可以证明。根据上面的定义，我们可以得到下面的结论：

R_q(q) ⇔ S(q) ⇔ q∈K ⇔ ~provable(R_q(q))  …………………  （式1）

如果R_q(q)可以证明，意味着provable(R_q(q))为真，显然意味着R_q(q)也为真，根据（式1）可得到~provable(R_q(q))也为真，发生了“~provable(R_q(q))”和“provable(R_q(q))”同时为真的情况，也就是PM不一致了。换句话说，如果PM是一个一致的体系，那么只有R_q(q)不可证。

如果~R_q(q)可以证明，意味着~R_q(q)为真，根据（式1）得到~(~provable(R_q(q)))为真，也就是provable(R_q(q))为真，即R_q(q)可以证明，也即R_q(q)为真。这次又发生了R_q(q)与~R_q(q)同时为真的情况。于是，如果PM一致，那么~R_q(q)也不可证。

综上，对于R_q(q)这个命题，只要PM是一个一致的公理体系，那么在PM中既不能证明它，也不能否证它。换句话说，在PM体系之内，可表达的命题R_q(q)说不清楚对错。

（3）进一步的分析

哥德尔在论文中明确提到，这种构造思路是来源于两个有名的悖论——理查德悖论（Richard-antinomy）和说谎者悖论（liar-antinomy），后者就是我们最前面说到的“这句话是谎话”的悖论，而前者则与哥德尔的构造有类似之处，感兴趣的读者可以自行了解。

哥德尔证明的一个关键点，就是把“真”、“假”与“可证明”及“不可证明”区分开来了。这里谈到的可证明与否都是指在PM体系之内。我们日常生活与工作中，经常把“真假”与“是否可证明”等同起来，认为“真⇔可证明”，“假⇔不可证明”。其实，“真假”与“是否可证明”的严格关系应该是“可证明⇒真”、“假⇒不可证明”，但是它们的逆命题却不成立，也就是说“真命题未必可证明”，同时“不可证明的也未必就是假命题”。

前面我们给出了~R_q(q)和R_q(q)都是不可证明的论断，但这并不意味着R_q(q)的真假不确定。其实我们看一下（式1），就可以得到，R_q(q) ⇔ ~provable(R_q(q))，也就是说，命题R_q(q)说的其实是“R_q(q)不可证”，或者说，R_q(q)说的是“自己不可证”。那么根据我们前面的论断，R_q(q)确实是不可证的，也就是说R_q(q)这个命题为真。大家没有必要为此而感到惊讶，前面我们说了，哥德尔清晰的区分了“可证与否”与“真假”的关系，真命题不一定可证。

（4）再进一步分析——哥德尔第二不完备定理

哥德尔在论文的Introduction部分中介绍了自己的证明思路之后，特别指出，在详细的对R_q(q)为真这个结论进行分析时，会得出一个奇怪的结论——关于公理体系一致性证明的奇怪结论，哥德尔说将在论文的定理XI中进行讨论。

哥德尔论文中的定理XI就是我们今天常说的“哥德尔第二不完备定理”。

由前面的论证过程可知，当PM体系一致的时候，可以得到结论“R_q(q)不可证”，也就是“R_q(q)为真”。这里面并没有附加任何别的条件。因此，根据前面的论证，我们得到，

“PM体系一致”⇒R_q(q)

可我们知道，R_q(q)是不可证的。也就是说，“PM体系一致”也应该是不可证的，否则如果“PM体系一致”可证，那么就可以推出R_q(q)，这与R_q(q)不可证矛盾。（严格的讲，这样的说法是不准确的，他没有证明“PM体系一致”⇒R_q(q)是可在PM体系中推导出来的。修炼第四重时会给出哥德尔更严格的证明过程。）

通过上面的简单分析，我们得到了“哥德尔第二不完备定理”，简单表述为“一个蕴含了皮亚诺公理的公理体系，其一致性是不能在这个公理体系内得到证明的”。

以上就是哥德尔不完备定理的证明思路，对于绝大部分数学爱好者，修炼到这里应该满意了。因为修炼到第三重之后，已经比较深入的理解了“哥德尔不完备定理”的证明思路，足够准确、全面的理解了“哥德尔不完备定理”的意义。

对于愿意学习的读者，可能仍然会有各种疑问？有人会问，哥德尔把PM表达式对应到自然数，到底有什么用，是怎么通过这种方式表达出provable(x)之类的有含义的命题的？也有人会问，修炼第一重的时候说到的“ω一致”和“原始递归”到底是什么意思？可能还有读者会问，第三重介绍的证明思路难道不是一个严格的证明过程么，为什么还要修炼第四重？对于需要解开这些疑问的读者，请你们和我一起，开始修炼第四重神功吧。

转载本文请联系原作者获取授权，同时请注明本文来自赵昊彤科学网博客。
链接地址：http://blog.sciencenet.cn/blog-409681-1067021.html