哥德尔不完备定理证明简介

哥德尔不完备定理证明简介

姓名：李嘉蔚 学号16020520034

【嵌牛导读】:随着计算机科学尤其是人工智能的发展，各种新理论层出不穷，一些有关不可计算数比如蔡廷常数之类的问题也受到了很多关注，而这最有名的莫过于哥德尔不完备定理了，关于它的证明是什么思路呢？我找到了证明并大概表达了证明的思想。

【嵌牛鼻子】:素数，素数乘积，形式符号，形式系统，命题，哥德尔编码，哥德尔数，递归可计算，元数学。

【嵌牛提问】：哥德尔编码与哥德尔数是什么？作用是什么？证明的大概思想是什么？（忽略细节吧）

【嵌牛正文】:

主要就是用了个哥德尔编码，把命题都变成素数编码，再变成这些素数的乘积（哥德尔数），这样每一个命题与哥德尔数就一一对应，再用哥德尔编码构造一个命题:“该命题（这个命题自身（涉及自指））不可被证明”。

于是人类可以看出这是个真命题（用所谓的元数学证明），但在该形式系统内不可证明。

2 + 3 = 5 这个表达式属于数学（算术），完全是由初等算术的符号构建的。另一方面， ‘2 + 3 = 5’是一个算术公式 这样一个命题却是对所展示的表达式做出的某种宣称。这个命题并不表达某种算术事实，也不属于算术的形式语言；它属于元数学，因为它将某个算术符号串定性为一个公式。下面的语句也属于元数学： 如果符号‘=’用于算术公式，则这个符号的左右两边都应是数字表式。 这个命题给在算术公式中使用某个算术符号规定了一个必要条件，即如果算术公式含有这个符号的话，必须要有什么样的结构。 再考虑下面三个公式： x  =  x 0 = 0 0  ≠  0 它们都属于数学，因为每一个都是完全用数学符号构建出来的。但是命题 ‘x’是一个变量。 属于元数学，因为它将某种算术符号定性为归属于一类特定的符号（即变量类）。同样，下面的语句也属于元数学： 公式‘0 = 0’可从公式‘x  =  x’导出，只要用数字‘0’代入变量‘x’。 这个命题规定了用什么样的方法就能从一个数学公式得到另一个公式，因而描述了两个公式如何相互发生关联。相似地，命题 ‘0  ≠  0’不是形式系统X的定理。

也属于元数学，因为它说的是某个公式无法从指定的形式演算的公理中导出，因而对这个系统来讲所给出的公式与公理之间不存在某种关系。最后，下面的命题也属于元数学： 形式系统X是一致的。 （即是说，不可能从系统X的公理推出形式上矛盾的公式——例如，公式‘0 = 0’和公式‘0  ≠  0’）。这个命题显然是关于一个形式演算系统的，它宣告说一对特定类型的公式，和构成这个演算的公理的公式之间，某种特定关系不能成立。

命题逻辑（常叫做“命题演算”）的词汇（或“原始符号”

列表）是极为简单的。它由变量和常量符号构成。变量可用命题

代入，因而称作“命题变量”。它们是字母“ ”，“ ”，

“

p q

r ”，等等。而常量符号，或者是“命题联接符”或者是标点符

号。命题联接符是：

“~”，它是“非”的缩写（称为“波折号”）；

“

∨ ”，它是“或者”的缩写；

“

⊃ ”，它是“如果…那么…”的缩写；

“•”，它是“与”的缩写。

标点符号则分别是左和右圆括号“（”和“）”。

形成规则通常用于将原始符号组合成被称为“公式”的命题

形式。每一个命题变量也被视为一个公式。而且，如果字母“ ”

代表一个公式，那么它的形式否定，即

S

~ (S)也是一个公式。

固定符号 哥德尔数 通常含义

~                    1                  非

∨                    2              或

⊃ 3 如果…那么…

∃ 4 存在一个…

= 5 等于

0 6 零

s 7 …的直接后继

（ 8 标点

） 9 标点

， 10 标点

+ 11 加

× 12 乘

（ ∃ x ） （ x = s y ）

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

8 4 13 9 8 13 5 7 17 9

然而关键是要给这个公式赋予唯一的一个数而不是一个数

的序列。幸好这样做并不困难。我们约定将这个公式联系到唯

一的一个数，它是按大小顺序排列的头十个素数的乘积，其中

每一个素数各加一个对应于相应符号的哥德尔数的指数。所以

与此公式相对应的哥德尔数是

2^8*3^4*……*23^17*29^9

让我们将这个非常大的数设为m。类似地，每一个基本符

号组成的有限序列，特别是每一个公式，都有一个唯一的哥德

尔数，它可写为与其符号个数相等的一系列按顺序的素数的乘

积，其中每一个素数各加一个等于其对应的符号的哥德尔数的

指数。

考虑一 个简单的公式“~（0 = 0）”，它表达了一个明显的错误即零不

等于它自己。现在我们看一个简单的元数学命题：这个公式的

第一个符号是“~”。如果通过哥德尔编码，元数学判断确实能

被忠实地映射到整数的集合及其性质上去，那么这个真实的命 题一定会映射为一个真的数论命题。这个数论命题到底是哪一

个？为了寻求答案，首先需要这个公式的哥德尔数—即 2^1*3^8*……*11^6*13^9，我们将称其为“a”

现在将注意力转向一个更为复杂的元数学命题：“具有哥德尔数 x 的公式序列是哥德尔数为 z 的公式（在 PM 中）的证

明”。借助于元数学的算术化，这个关于某些字符串之间排列

关系的命题，通过一个关于两个数 x 和 z 之间纯数字关系的命

题而被映照到数论之中。

稍想一下我们就会认识到，在证明

的哥德尔数 k 和结论的哥德尔数 n 之间有确定的，但并不意味

着是简单的算术关系。）我们将用缩写“dem（x, z）”来表示

整数 x 和 z 之间的算术关系。之所以选择小写的字符串

“dem”，是为了提醒我们这个数论关系所对应的元数学关

系——即“哥德尔数为 x 的公式序列是哥德尔数为 z 的公式在

PM 中的证明（demonstration）”。

注意，“dem”所指的数量关系，隐含地依赖于所有的公

理和 PM 的演绎规则。如果我们多少动了一下 PM，则“证明”

也多少有所变动，因而也会映射为一个多少有所不同的数量关

系，但是仍会非常相似于 dem，并且也会像 dem 在 PM 中所起

的作用一样在变化后的系统中起作用。

哥德尔在他的论文中用了极大的努力使读者相信“dem（x,

z）”是数 x 和 z 之间的原始递归关系，并且从这个事实（这一

点我们就此接受下来）出发，通过哥德尔对应引理，在 PM 中

有一个形式符号组成的公式表达了这个关系。我们用缩写“Dem（x, z）”来指此公式，之所以用大写“D”，表明它是

形式化的公式。

此处要小心地看到，“dem（2, 5）”虽说是关于整数 2 和

5 的有意义的命题（有意义但显然是假的，因为 2 不会是任何证

明的哥德尔数，而 5 也不会是一个完整公式的哥德尔数），它

的形式对应物“Dem（ss0, sssss0）”却仅仅是PM的一个字符

串，因此严格地说既不为真也不为假，而是无意义的。28 但是

哥德尔的对应引理再次进入视野，它为我们保证，任何时候当

数论述语 dem （ x, z ）为真时，形式为 Dem （ sss…sss0,

sss…sss0）的字符串是（PM的）一个定理，式中第一个串中的

“

s”个数为x，第二个串中的“s”个数为z。

在 PM 中公式“Dem（x, z）”的存在告诉我们一个非常关

键的信息：具有“某甲用了 PM 的规则，证明出某乙”形式的

真的元数学命题，被忠实地反映在 PM 的定理之中。同样，每一个具有形式“某甲用了 PM 的规则，没有证明出某乙”的真

的元数学命题，都被忠实的映照为 PM 的具有形式“~Dem

（sss…sss0, sss…sss0）”的定理，和往常一样，串中各有适当

数量的“s”。这里我们再次看到，多亏了哥德尔映射，PM 可

被视为具有精确谈论自身的能力。

在陈述哥德尔证明的关键点之前，还需要了解最后一个特

殊概念及相应的记号。让我们先举一个例子。正如在前几页看

到的，公式“（∃x）（x = sy）”的哥德尔数 m 十分巨大，其中

有一个变量（y）的哥德尔数是 17。假如我们在此公式中用 m

替换哥德尔数为 17 的变量 y。结果是得到一个极长的公式

“（∃ x）（x = sss…sss0）”，其中串中有（m + 1）个“s”。

（翻成汉语，这个新的 PM 字符串的意思是存在一个数 x 是 m

的直接后继，或更简短地说 m 有一个后继。）

这个长长的公式本身又有一个哥德尔数，当然这个数非常

大，但不管它有多大，原则上讲它的计算方法相当直截了当。

先不管其计算的细节或精确的结果，我们可以一种毫不含糊的

元数学方式简单地刻画出这个结果数：它是在一个哥德尔数为

m的公式中，用m本身去替换其中哥德尔数为 17 的变量而得到

的新公式的哥德尔数。这一刻画，唯一地确定了一个作为数m

和 17 的函数的正整数。

正如我们将要看到的那样，将一个字符串的哥德尔数代入

这个字符串本身（然后取结果的哥德尔数）这么个看似绕圈子

的概念是哥德尔关键性的想法之一，他也付出极大的努力来使

读者确信这个函数是直接可计算的，因而是原始递归的，并在

对应引理的适用范围之内。我们将用记号“sub（x, 17, x）”来

代表新哥德尔数，它是老哥德尔数x的函数。尽管说起来有些绕

舌，我们还是可以准确地讲出这个数是什么：它是取一个哥德

尔数是x的公式，其中凡是有变量y出现的地方均用数x的数字替

换而得到的新公式的哥德尔数。

哥德尔表明（1）如何构造PM的一个公式G，使其表达以

下元数学命题：“使用PM的规则，公式G不可证”。34 因而从

字面上看，这个公式讲的是它自身不可证明。在某种程度上，

G是模仿理查德悖论构造的。在理查德悖论中，表述“理查德

性质”是和某一数n相联系的，从而构造出“n是理查德数”这

样的命题。在哥德尔的论证中，公式G同样地和某一数g——即

它本身的哥德尔数——相联系，并且G是这样构造出来的，其

意思是说“具有哥德尔数g的公式是不可证明的”。

接着哥德尔证明，（2）G是可证明的，当且仅当它的否定

形式～G是可证明的。证明中的这一步也还是模仿理查德悖论

中的步骤，那里证明的是n是理查德数当且仅当n不是理查德

数。然而，如果一个公式及其否定都是形式可证明的，那么PM

就是不一致的。反过来，假设PM是一致的，则G和～G两者都

不可能从PM的公理中形式推导出来。简言之，如果PM一致，

则G是一个形式不可判定的公式。

然后哥德尔表明，（3）尽管 G 是形式不可证明的，它却

是真的算术公式。G 之为真，是在下述意义上说的，即它声称没有整数会

具有哥德尔所定义的某种算术性质——正如哥德尔所证明的那

样。

步骤（4）进而表明，由于 G 是真的，又是形式上不可判

定的（在 PM 中），因此 PM 肯定是不完全的。换句话说，我

们不能用 PM 的公理和规则导出所有的算术真理。而且，哥德

尔进一步证明，PM 是在本质上不完全的：即使用附加的公理

（或规则）来扩大 PM，使真公式 G 在增强了的演算中成为形

式可推导的，也会有另一个用完全类似的方式构造出的真公式

G’，而 G’在增强的演算中是形式不可判定的。不用说，如果进

一步增强这个已经增强了的演算系统，使之能够导出 G’，却又

会引出了另一个在这个双重增强的演算中不可判定的公式 G”—

—如此等等，以至无穷。这就是所谓“在本质上不完全”的含

义。

在步骤（5）中，哥德尔描述了怎样构造一个 PM 的公式

A，它所表达的元数学命题是：“PM 是一致的”；并且证明公

式“A G”在 PM 中是形式可证明的。最后，他表明公式 A 在

PM 中是不可证明的，并从而得出推论，PM 的一致性是无法用

任何系列的逻辑推理来证明的，只要这些推理是可以被镜照在

PM 本身组成的形式演绎系统中。

哥德尔所证明的是，这个公式的某个特例是形式不可证明

的。为了构造这个特例，我们从公式（1）开始：

~（∃x）Dem（x, Sub（y, 17, y）） （1）

这个公式属于PM，但有一个元数学解释。问题是这个解

释是什么？读者应该还记得表达式“Sub（y, 17, y）”是表示一

个数。这个数，是在哥德尔数为y的公式中，用y的数字代入哥

德尔数为 17 的变量（即所有字母“y”的地方）而得到的公式

的哥德尔数。36 由此，公式（1）显然表达了元数学命题：“哥

德尔数为sub（y, 17, y）的公式不可证明”。尽管这是个挑逗人

的命题，但仍然是未封口的、不明确的，因为它仍然包含变量“

y”。为了使其确定下来，我们需要将变量换成一个数字。应

该选什么数？这里且看哥德尔怎么做。

因为公式（1）属于 PM，它有一个从原则上讲可计算的

（很大的）哥德尔数。幸运的是，我们（哥德尔也一样）不需

要进行实际的计算，而可简单地将其值用字母“n”来表示。下

一步，我们用数 n（更准确地说，是用数 n 的数字，我们乐于

将这个数字写为“n”，就象当我们写“17”时，知道我们实际

上是指“sssssssssssssssss0”）替换在公式（1）中变量“y”的

每一次出现。这样做，将产生一个新的公式，我们将其称为

“G”：

～（∃x）Dem（x, Sub（n, 17, n）） （G）

这就是我们要找的公式。因为它是公式（1）的一个特

例，因此其元数学意义就是：“哥德尔数为 sub（n, 17, n）的公

式是不可证明的”。现在由于其中不再有（未量化的）变量，

G 的意义是确定的。

公式G属于PM，因此肯定对应于一个哥德尔数g。g的值是

多少？稍想一下就会知道g = sub（n, 17, n）。37 要知道为什

么，只需要回想一下，sub（n, 17, n）是当我们在哥德尔数为n的公式中用n（它的数字）替换哥德尔数为 17 的变量（即

“

y”）而得到的公式的哥德尔数。但公式G正是如此而获得

的！也就是说，我们从哥德尔数为n的公式出发；然后我们用n

的数字替换其中所有的“y”，这样一来，sub（n, 17, n）就成

为了G的哥德尔数。

现在我们一定会回想到 G 是下列元数学命题在 PM 中的镜

像：“哥德尔数为 g 的公式是不可证明的”。而这就表明公式

G 在 PM 中所表达的元数学命题是：“公式 G 是不可证明

的”。总之一句话，可构建 PM 公式 G，它断言其自身不是 PM

的定理。

（ii）我们现在来到第二步——即证明G事实上并不是PM

的一个定理。哥德尔对这一点的论证类似于理查德悖论的建

构，但是避开了错误的推理。38 他的论证相对来说是顺畅的。

它证明如果公式 G 是可证的，则它的否定形式（即公式

“（∃ x）Dem（x, Sub（n, 17, n））”，其解释为“在PM中存

在G的一个证明”）也是可证的；反过来，如果G的否定形式是

可证的，则G本身也是可证的。因而我们得到：G可证，当且仅

当，~G可证。39 正如我们早前注意到的，如果一个公式及其否定形式都可从某个形式演算中推导出来，那么这个演算就不是

一致的。转过来，我们可以推论说如果PM是一致的形式演算系

统，则公式G及其否定形式均不可证。简言之，如果PM一致，

则G是形式不可判定的。

后面还有一个令人吃惊的情况可以表明这个结果的深

刻含义。因为，虽然在 PM 是一致的条件下，公式 G 不可判

定，然而通过元数学推理却能够证明 G 是真的。（当然或者 G

或者~G 肯定有一个是真的，因为它们构成了关于数的一对对立

的判断；肯定其中有一个为真有一个为假，问题是哪个为真哪

个为假。）

不难看出 G 所说的为真。的确，正如我们早些时观察到

的，G 说的是“没有 G 的 PM 证明”。（这至少是 G 的元数学

解释；当在数论层次上时，G 所说的仅仅是不存在与数 sub（n,

17, n）有某种关系（即“dem”关系）的数 x。为了相信 G 为

真，仅考虑前一种解释就可以了。）但是我们刚才证明了 G 在

PM 中是不可判定的，特别是 G 在 PM 中没有证明。而这一

点，回想一下，恰恰就是 G 所说的！所以 G 所说的是真理。读

者应该细心地体会到，这里我们不是通过从形式系统的公理和

规则形式地进行推导，而是通过元数学论证证明了一个数论的

真命题。

（iv）现在我们要提醒读者注意在讨论命题演算时引进的

“完全性”概念。在那里曾提到，一个演绎系统被称作是“完

全的”，如果每一个能够在此系统内表示的真命题都是可以用

演绎规则从公理中推导出来的。如果不是这种情况，即不是每

一个系统中可表示的真命题都是可推导的，那么这个系统就被

称作“不完全的”。由于我们刚好表明G是PM的真公式但又是 在PM中形式不可推导的，因而PM是一个不完全的系统，当然

假定的前提是PM是一致的。41

而且，PM 的问题比人们最初想到的还糟，因为它不仅是

不完全的，而且是实质上不完全的：即使将 G 加上作为一条新

的公理，扩大了的系统仍然不足以形式地获得所有的算术真

理。原因在于，如果最初的公理集这样扩大之后，在扩大了的

系统中可以构建另一个是真的而又是不可判定的公式。这个公

式会涉及到一个更复杂一些的数论关系——比如说 dem’（x,

z）——因为新的系统增加了一个公理，因此新系统“可证性”

的概念会比 PM 中要复杂一些。在新系统中构造不可判定的公

式，只要仿效哥德尔在 PM 自身中确定一个真的却不可判定的

公式的方法就行了。不管初始的系统扩充多少次，这个产生不

可判定公式的方法均可以使用。它同样也不实质性地依赖于罗

素和怀特海的形式演算系统的特点。不管将何种系统作为起

点，只要那个系统是完全形式化的，只要它含有确定整数基本

性质的公理并包括加法和乘法，此方法都适用。

这就迫使我们认识到形式公理演绎系统能力的一个根本局

限性。和先前的信念相反，对算术真理的广袤天地，是无法通

过一次性地设定一组公理和演绎规则，从中形式地推出每一个真算术命题而建立起整体系统的秩序的。对任何倾向于相信数

学的实质就是纯形式公理演绎的人来说，这肯定是个令人震撼

的发现。

（v）我们终于接近哥德尔令人惊奇的智力交响乐的尾声

了。我们跟踪了他为其元数学命题奠定基础的各个步骤，这个

命题是：“如果 PM 是一致的，则它是不完全的”。但是，也

可以证明这个条件命题作为一体时可用 PM 中一个可证公式来

表示。

很容易构建这个关键性的公式。我们在第五章曾说过，元

数学命题“PM 是一致的”，等价于说“至少有一个 PM 的公式

在 PM 中是不可证的”。通过哥德尔映射将此元数学命题映射

到数的范畴，这对应于数论命题“至少存在一个 y，没有一个 x

能和它构成 dem 关系”。也可以说，“某数 y 具有这样一种性

质，即没有 x 能使关系 dem（x, y）成立”。这样我们就可以将

其翻成 PM 的形式：

（∃y）～（∃x）Dem（x, y） （A）

我们可以重述 A 的元数学解释如下：“至少存在一个公式

（其哥德尔数为 y），无法提出任何公式序列（其哥德尔数为

x）以构成 PM 中对它的证明”。

因此，公式 A 代表了元数学命题“如果 PM 一致，则它是不完全的。

将前面讲的归拢在一起，结论就是条件命题“如果 PM 一

致，则它是不完全的”在 PM 中可以表示成公式：

（∃ ∃ y）~（ x）Dem（x, y） ⊃ ~（∃ x）Dem（x, Sub（n,

17, n））

这就是证明，真有人想弄清细节的话，可以弄个纸质版的看下，电子版的看的话就是这么难受🤓。

哥德尔不完备定理证明简介