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

Http:///journal.htm 逻辑与认知 Vol.5, No.2, 2007 * 基于直觉主义和维特根斯坦对哥德尔不完全定理的评论 庄朝晖 (厦门大学计算机科学系，厦门，福建，361005) 摘要：本文首先从形式主义的角度介绍了哥德尔不完全性定理，提出“哥德尔不完备性定理”的说法是容 易混淆的，说明一阶算术有非标准模型，哥德尔的证明是基于标准模型的，可以推出一阶算术在标准模型 上的不完备。接下来，引入了维特根斯坦对于哥德尔定理的评论。Floyd和Putnam从非标准模型的角度来 解读维特根斯坦的评论，然而Bays对此提出了有力的批评，表明从非标准模型来解读维特根斯坦的评论是 困难的。本文引入了直觉主义的思想，对维特根斯坦的评论进行了新的解读，指出哥德尔证明中所基于的 一阶算术的解释是模糊的。对于维特根斯坦，可以接受的是一阶算术上的可证性，所以在他看来，自然数 系统上的真，如果要有意义的话，只能定义为一阶算术上的可证性。然后，进一步基于直觉主义和维特根 斯坦的观点，批评了康托尔的“对角线”方法，提出康托尔证明中基于可数集定义的康托尔数是一直处于 构造之中的，而且可数集与康托尔数的展开是相互追随的。在定义这个数的时候，已经决定了后面想把这 个数放回可数集，就会产生矛盾。因此，矛盾不是来自于前提错误，而是来自于不正当的对康托尔数的定 义。同样，在直觉主义者看来，哥德尔定理证明中得到的矛盾，是来源于哥德尔对哥德尔数的不正当定义。 这个结论还可以推广到递归函数和图灵机等这些等价的计算模型之上。比如，在直觉主义者看来，停机问 题是没有意义的。 关键词：哥德尔不完全性定理；对角线方法；直觉主义；维特根斯坦；停机问题 中图分类号：B81 文献标识码：A 1 引言 哥德尔不完全性定理，是 20 世纪最重要的定理之一，在逻辑学、计算机科学、数学和 哲学领域都有广泛的影响。 哥德尔[1]在罗素系统上构造了一个公式（这个公式不妨称为哥德尔语句，本文也用 P 表示），证明了著名的哥德尔第一不完全性定理：如果罗素系统是一致的，那么这个公式在 罗素系统中是不可证明，这个公式的否定在罗素系统中也是不可证明的。哥德尔的这个定理 具有相当的一般性，在包含一阶算术的形式系统中都适用。在《数学家的逻辑》[2]这本书 中，基于一阶算术，也给出了哥德尔不完全性定理的证明过程。基于罗素系统，还是基于后 来的一阶算术，来讨论哥德尔不完全性定理，效果都是一样的。 2 形式系统的不完全与不完备 本节的讨论，基于形式主义，澄清一些概念问题。 “哥德尔不完全性定理”，有时也称为“哥德尔不完备性定理”。我认为“哥德尔不完 备性定理”这样的说法是容易混淆的。 *收稿日期: 2007-06-27; 基金项目：无 作者简介：庄朝晖(1976-)，男,福建南安人，厦门大学讲师,工学硕士，研究方向为数理逻辑。 - 57 - 基于直觉主义和维特根斯坦对哥德尔不完全定理的评论 在形式系统中，“完全性”与“完备性”，这两个概念要区分清楚。所谓形式系统的完 全性（complete ）指的是形式系统中所有的语句，要么它的肯定形式可证要么它的否定形式 可证。所谓形式系统的完备性(adequacy，有时也用 completeness)，则与形式系统的模型密切 相关，指的是在所有模型下为真的语句，在形式系统中也可以得到证明。完备性与完全性并 不一样，比如在形式主义者看来，命题逻辑和一阶逻辑都是完备的但不是完全的。 但是完备性与完全性容易被混淆，中文如此，英文也如此。事实上哥德尔得到的是不完 全性定理。基于不完全性定理之上，当把一阶算术的模型指定为自然数系统时，又推出一阶 算术在自然数系统上的不完备性。 这里有个地方值得思考。根据哥德尔第一不完全性定理，一阶算术如果是相容的，则一 阶算术是不完全的，那么一阶算术至少有两个实质不同的模型。也就是说一阶算术除了自然 数系统之外，还可能有第二个模型。 如果把自然数系统称为一阶算术的标准模型，那么一 阶算术还可能有非标准模型。 所谓一阶算术