基于直觉主义和维特根斯坦对哥德尔不完全定理的评论

http://www.77cn.com.cn/journal.htm 逻辑与认知 Vol.5, No.2, 2007

基于直觉主义和维特根斯坦对哥德尔不完全定理的评论*

庄朝晖

(厦门大学计算机科学系，厦门，福建，361005)

摘要：本文首先从形式主义的角度介绍了哥德尔不完全性定理，提出“哥德尔不完备性定理”的说法是容易混淆的，说明一阶算术有非标准模型，哥德尔的证明是基于标准模型的，可以推出一阶算术在标准模型上的不完备。接下来，引入了维特根斯坦对于哥德尔定理的评论。Floyd和Putnam从非标准模型的角度来解读维特根斯坦的评论，然而Bays对此提出了有力的批评，表明从非标准模型来解读维特根斯坦的评论是困难的。本文引入了直觉主义的思想，对维特根斯坦的评论进行了新的解读，指出哥德尔证明中所基于的一阶算术的解释是模糊的。对于维特根斯坦，可以接受的是一阶算术上的可证性，所以在他看来，自然数系统上的真，如果要有意义的话，只能定义为一阶算术上的可证性。然后，进一步基于直觉主义和维特根斯坦的观点，批评了康托尔的“对角线”方法，提出康托尔证明中基于可数集定义的康托尔数是一直处于构造之中的，而且可数集与康托尔数的展开是相互追随的。在定义这个数的时候，已经决定了后面想把这个数放回可数集，就会产生矛盾。因此，矛盾不是来自于前提错误，而是来自于不正当的对康托尔数的定义。同样，在直觉主义者看来，哥德尔定理证明中得到的矛盾，是来源于哥德尔对哥德尔数的不正当定义。这个结论还可以推广到递归函数和图灵机等这些等价的计算模型之上。比如，在直觉主义者看来，停机问题是没有意义的。

关键词：哥德尔不完全性定理；对角线方法；直觉主义；维特根斯坦；停机问题

中图分类号：B81 文献标识码：A

1 引言

哥德尔不完全性定理，是20世纪最重要的定理之一，在逻辑学、计算机科学、数学和哲学领域都有广泛的影响。

哥德尔[1]在罗素系统上构造了一个公式（这个公式不妨称为哥德尔语句，本文也用P表示），证明了著名的哥德尔第一不完全性定理：如果罗素系统是一致的，那么这个公式在罗素系统中是不可证明，这个公式的否定在罗素系统中也是不可证明的。哥德尔的这个定理具有相当的一般性，在包含一阶算术的形式系统中都适用。在《数学家的逻辑》[2]这本书中，基于一阶算术，也给出了哥德尔不完全性定理的证明过程。基于罗素系统，还是基于后来的一阶算术，来讨论哥德尔不完全性定理，效果都是一样的。

2 形式系统的不完全与不完备

本节的讨论，基于形式主义，澄清一些概念问题。

“哥德尔不完全性定理”，有时也称为“哥德尔不完备性定理”。我认为“哥德尔不完备性定理”这样的说法是容易混淆的。 *收稿日期: 2007-06-27;

基金项目：无

作者简介：庄朝晖(1976-)，男,福建南安人，厦门大学讲师,工学硕士，研究方向为数理逻辑。

基于直觉主义和维特根斯坦对哥德尔不完全定理的评论

在形式系统中，“完全性”与“完备性”，这两个概念要区分清楚。所谓形式系统的完全性（complete）指的是形式系统中所有的语句，要么它的肯定形式可证要么它的否定形式可证。所谓形式系统的完备性(adequacy，有时也用completeness)，则与形式系统的模型密切相关，指的是在所有模型下为真的语句，在形式系统中也可以得到证明。完备性与完全性并不一样，比如在形式主义者看来，命题逻辑和一阶逻辑都是完备的但不是完全的。

但是完备性与完全性容易被混淆，中文如此，英文也如此。事实上哥德尔得到的是不完全性定理。基于不完全性定理之上，当把一阶算术的模型指定为自然数系统时，又推出一阶算术在自然数系统上的不完备性。

这里有个地方值得思考。根据哥德尔第一不完全性定理，一阶算术如果是相容的，则一阶算术是不完全的，那么一阶算术至少有两个实质不同的模型。也就是说一阶算术除了自然数系统之外，还可能有第二个模型。 如果把自然数系统称为一阶算术的标准模型，那么一阶算术还可能有非标准模型。

所谓一阶算术是完备的，指的是在一阶算术的所有模型中为真的语句，在一阶算术中都可以得到证明。所谓一阶算术是不完备的，指的就是存在一个在一阶算术的所有模型中为真的语句，在一阶算术中是不可证的。

那么，如果我们要说一阶算术是不完备的，我们要讨论的不能仅仅在自然数系统之上，我们还要考虑一阶算术其他可能的模型。这样来看，现在常用的“哥德尔不完备性定理”这样的说法，是不严谨的或者说是容易混淆的。哥德尔事实上得到的是“哥德尔不完全性定理”。然后，可以推论得到一阶算术相对于自然数系统而言是不完备的。如果要说“哥德尔不完备性定理”，精确点应该说“一阶算术在自然数系统上的不完备性定理”。

澄清这一点，我们就注意到在哥德尔不完全性定理的证明中，一直针对的就是自然数系统，或称一阶算术的标准模型。哥德尔不完全性定理的证明，依赖于我们对自然数系统的直觉。另外，一阶算术还有许多非标准模型，比如引入无穷大的常元。

3 解读维特根斯坦的评论

有趣的是，维特根斯坦对哥德尔不完全性定理进行过评论[3]。哥德尔读了维特根斯坦（以下简称维氏）的评论后，认为维氏没有理解他的定理。此后，维氏的这段评论在数学哲学界，普遍被认为是“臭名昭著”的。维氏评论的中文翻译可参考文献[4] 。然而，维氏是罗素最优秀的学生之一，他不可能不熟悉罗素的形式系统。于是，一些学者也倾向于为维氏评论寻找好的解读方式。

2000年，Floyd和Putnam写了一篇论文“A Note on Wittgenstein’s “Notorious Paragraph” about the Gödel theorem” [5]，给出了他们对维氏评论的解读。他们从非标准模型的角度来解读维特根斯坦的评论。以下用P来指哥德尔构造出来的那个公式，表达“本公式是不可证明的”。 根据哥德尔第一不完全性定理：如果一阶算术是一致的，那么P在一阶算术下是不可证的；如果一阶算术是ω一致的，那么﹁P在一阶算术下是不可证的。

现在，不妨从另一方面解读，假设﹁P在一阶算术下是可证的，那么一阶算术不是ω一致的。当然，依然还要假设一阶算术是一致的。也就是说，一阶算术可能是一致的但不是ω一致的。

这样会导致自然数系统N不满足一阶算术，也就是说一阶算术只有非标准模型。这样的话，对于P的解释就不能还是照原来理解，应该放弃原有的理解方式。

逻辑与认知 Vol.5, No.2, 2007

针对Floyd和Putnam的解读，Bays写了一篇论文“On Floyd and Putnam on Wittgenstein on Gödel” [6]对此进行了批评：Floyd和Putnam对于“﹁P在一阶算术下是可证的”，没有给出适当的理由。其次，不承认自然数系统满足一阶算术，这点是很难接受的。另外，如果﹁P在一阶算术下是可证的，则数学家要做的事大概是修改一阶算术，也不会用非标准模型来解释一阶算术。

Bays的回复是有说服力的， 使用非标准模型来解释一阶算术，确实与创立一阶算术的本意是相反的。Floyd和Putnam的思路，说服力并不够。

所以，从非标准模型来解读维氏的评论，这条路不好走。那么，我们不妨从另一个方向入手。一般认为，自然数系统当然是满足一阶算术的呀。然而，对于自然数系统是什么，依然不是很清晰。

我们引入一阶算术，本来 …… 此处隐藏：11808字，全部文档内容请下载后查看。喜欢就下载吧 ……