哥德尔不完备定理（解释二）

数学使徒（MathematicalApostle）

在1931年，哥德尔给冯诺依曼写的一封信中[1]曾经提到过这个问题。他解释了他的不完备定理中为什么构造一个“不可证”的命题而不是一个“为假”的命题。因为他发现，在一个形式系统中，“真假”这样的概念大概是没有办法严格描述的，然而“可证”则是一个形式系统中有严格定义的东西。

当然，他当时不知道的是，两年后，塔斯基发表了一个证明，证明了一个形式系统内部无法定义“真”。这个定理叫做“塔斯基不可定义定理”。如果在当时他已经有了证明，很遗憾，这位天才失去了这个定理的优先权。

对哥德尔本人而言 —— 他是一个死硬的数学柏拉图主义者 —— 他认为这个定理说明了一个简单事实：在数学中，“真”和“可证”是两码事，而不是像当时大行其道的形式主义所认为的，真=可证。哥德尔认为的数学真是因为它本来就是真的，是一个客观的、抽象的现实，而不是因为我们可以构建一个形式体系，在这个体系中可以把它证明出来。他有一句非常有名的话是这样说的[2]：

“要么，数学对我们来说高不可攀，要么，我们的大脑不仅仅是一台机器。”

也就是说，如果我们按照“形式框架中可以证明”这种“机器”模式来搞数学，那么必定会有深刻的数学真理不可能被我们理解。

说一点不可定义定理吧（我不是专家，有错误请大家批评）。这个定理的基本思路就是，如果我们允许一个形式系统内部存在“真”的定义，那么我们就可以构造出类似“说谎者悖论”这种东西。

比如说，一个形式逻辑的命题P，是这样的：

P≡(∃n) (~T(n))＆(Q(m，n))

对不熟悉这种符号的人，我这里有必要把其中的符号做一个简单的解释：

1. ∃，是一个反过来写的大写E，是英语“存在（Exist）”的首字母，它的含义是，“存在一个……使得……”。 (∃n) 的意思就是，存在一个n，使得后续的一串关于n的逻辑陈述是成立的。也就是说，这个命题断言，至少会存在一个n，它满足后续的逻辑条件。

2. &，是一个常见的逻辑运算，表示“并且”。也就是说，上述的n同时满足两个条件 (~T(n))、以及 (Q(m，n)) 。

3. 这里的n是一个哥德尔数。也就是说，它是某一个逻辑命题按照哥德尔的规则“编码”而成的一个自然数。它本身是一个数字，但是，如果我们按照哥德尔规则把它翻译成一种逻辑陈述，它就可以表达为一种逻辑命题。为了方便陈述，我这里约定一个规则，在本小节的逻辑陈述中，所有的小写字母，表示的都是一个哥德尔数，而大写字母，则是一个逻辑陈述。我们可以这样理解：哥德尔数是一种语言，它是以0到9十个数字为“字母表”、按照哥德尔规则为语法的一串符号。而我们根据哥德尔规则，可以把它翻译成用逻辑符号表达的逻辑陈述，这种逻辑陈述，就是哥德尔数的元语言。

4. 这里，关于n的两个条件的第一个， (~T(n))，其中的“~”在逻辑语言中表示的是“否定”。而这里的T(n)是一种关于n的逻辑陈述。这里我们定义T是这样的：“把n翻译成逻辑命题后的表达是真的”。而前面加上一个否定运算，就是“n的逻辑表达是真的”这件事是假的，也即是说，n所代表的逻辑命题不是真的。

5. 而第二个条件中，是一个叫做Q的关于m和n —— 按照我们的约定，m和n两个小写字母表示的是两个哥德尔数 —— 的陈述。这种陈述是什么含义呢？我们这样来定义它：把m翻译成逻辑表达，它是一个关于某个哥德尔数x的陈述，比如说M(x)。这时候我们把m这个哥德尔数代入x，得到M(m)，这个M(m)的哥德尔数就是n。简言之，Q的含义就是，把哥德尔数m代入m表达的逻辑命题M中得到的是一个由哥德尔数n所代表的逻辑命题。

好了，现在，我们有了一些关于符号逻辑和形式语言的基本知识，我们就可以进一步来构造那个“说谎者悖论”了。

现在，我们来看最初的那个逻辑命题P：

P≡(∃n) (~T(n))＆(Q(m，n))

它自己也有一个哥德尔数 —— 按照哥德尔的规则，每一个逻辑命题都可以编码成唯一一个哥德尔数。我们这里不会去用具体的规则去构造这个数字，它将会是一个无比巨大的自然数。我们现在只是假设说，这个哥德尔数为p。我们现在把p代入到上述命题中的m中去，于是我们就得到了：

P'≡(∃n) (~T(n))＆(Q(p，n))

那么，这个P’是真的还是假的呢？

首先，我们假设这个命题是真的。那么，它说的无非就是，存在这这么一个n，它同时满足两个条件：

1. “n所代表的逻辑命题是真的”这件事不成立，并且

2. 由于Q的操作中得到的是一个n代表的逻辑命题，所以，“n代表的逻辑命题是真的”成立。

所以我们得到了一个矛盾。于是这个命题不可能是真的。

现在，我们假设它是假的。那么，这意味着，对于任何一个n，两个条件件(~T(n))、以及 (Q(p，n))都至少有一个假的。也就是说，如下两个条件至少有一个是假的：

1、 n所代表的命题是假的，

2、 将p代入到它所代表的的命题P —— 也就是我们的原命题，我们得到一个由n代表的逻辑命题。

既然任何一个n都有上面的性质，那么，现在我们可以来看一看其中一个例子：就是n满足第二个条件的情况。也就是说，把p代入P，得到一个n所代表的命题。这个命题显然是存在的，那么它是什么呢？它就是我们的原命题P’啊 —— 因为这个命题就是吧p代入到P中得到的。

我们接着来推理，对于这个n来说，既然满足了第二个条件，而两个条件至少要有一个不满足，所以第一个条件就一定是假的。也就是说，“n所代表的命题是假的”这个命题是假的，也就是说，n所代表的命题一定是真的。而n所代表的命题是什么呢？他就是P’啊。所以说，P’一定是真的。

然而，这里我们假设的是P'是假的，所以我们就又产生了一个矛盾。

所以这个命题不可能是假的。

于是，我们就产生了说谎者悖论的情况。而这里的整个过程中，我们并没有在任何地方使用过自我引用。

其实，这里我发现一个非常非常巧妙的、不严谨但是直观的例子，是Hofstadter在“I am a strange loop"[3]这本书中构造的一句自然语言，用一种非自指的方式实现自我判定。这里我给它做一个小小的改造，简直就是一个天才的帮助理解的实例。

“接上引号中的词语后构成的句子是假的” 接上引号中的词语后构成的句子是假的。

这里面，引号中的那一段字符串，其实就是一种直观的命题和它的哥德尔数之间变换的类比：在形式语言中，我们根据逻辑规则运算的是各种各样的字符串，它可以是作为逻辑表达的字符串，也可以是作为“编码”的字符串。

参考

1. GDEL K.Collected works:vol.V[C]. FEFERMAN S,DAWSON Jr J W,GOLDFARB W,et al.Oxford:Oxford University Press,2003.

2. R. Goldblatt, Topoi: The Categorial Analysis of Logic. Dover Publications, 2006.

3. D. R. Hofstadter, I Am a Strange Loop. Basic Books, 2007

上一章 哥德尔不完备定理（解释一） 数学使徒（MathematicalApostle）最新章节 下一章 【离散数学-集合论】无穷集合的基数