摘要：本文基于直觉主义和维特根斯坦的观点，批评了康托尔的“对角线”方法，提出康托尔证明中基于可数集定义的康托尔数是一直处于构造之中的，而且可数集与康托尔数的展开是相互追随的。在定义这个数的时候，已经决定了后面想把这个数放回可数集，就会产生矛盾。因此，矛盾不是来自于前提错误，而是来自于不正当的对康托尔数的定义。康托尔提出对角线方法后，这种方法被应用到各种计算模型之上。本文以停机问题作为实例，介绍了停机问题的证明，并基于直觉主义的观点，对停机问题进行了评论，认为停机问题的证明是没有说服力的。
关键词：对角线方法，直觉主义，维特根斯坦，停机问题
1、对角线方法
1891年，康托尔使用对角线方法证明：实数集是不可数的。[1]以下是证明过程。
设M为所有形如：
(x1, x2, x3, x4……) ，其中的xi是0或1。
的元素的集合。
假设M可数的。那么我们可以枚举M中的元素。例如：
E1=(0, 0, 0, 0, ……)
E2=(1, 1, 1, 1, ……)
E3=(0, 1, 0, 1, ……)
……
为了证明的方便，我们将这些元素表示为如下形式：
E1 = (a1.1, a1.2, a1.3, ……)
E2 = (a2.1, a2.2, a2.3, ……)
E3 = (a3.1, a3,2, a3.3, ……)
……
Eu=(au.1, au.2, au.3, ……, au.u, ……)
……
在此基础上，定义E0 = (b1, b2, b3, ……bu,……) ，其中b1与a1.1不同, b2与a2.2不同, 一般地, 对于所有的n，bn与an.n不同。 (本文中，有时候称E0 为康托尔数)
在上例中，E0=(1, 0, 1, ……)。
E0显然是M中的元素。现在，不妨设E0等于某一个Ei。然而，根据E0的定义，bi与ai.i不同，因此E0不等于Ei。矛盾。
因此，假设是错误的，集合M是不可数的。因为集合M与实数集之间可以建立一一映射，因此实数集也是不可数的。
2、直觉主义视角下的对角线方法
对于康托尔的“对角线”方法，直觉主义者是不赞同的。布劳维尔评论道：形式主义者作出结论：“连续统的势，即介于0与1之间的实数的集合的势，大于阿列夫零”，这是一个对直觉主义者来说没有意义的命题。[2]因为直觉主义者只接受潜无穷，不接受实无穷。在康托尔的证明中，依赖于可数集之上定义了康托尔数，这个思路是把可数集当成一个已完成的实无穷来考虑。然而，在直觉主义者看来，这个过程是可疑的。因为可数集始终处于构造之中，并不是已经完成的一个集合。所以，康托尔数可以说是一直处于构造之中的，处于永远未完成的状态。康托尔在证明中，又把这个随可数集的展开而变化的数试图放入已展开的可数集中，这样当然就产生矛盾了。
维特根斯坦也强调构造性的观点，他提到：“因此有这样的争论：一个不是构造的存在证明是否真的是对于存在的证明。即是说，它问的是：如果我没有可能发现它存在于什么地方，我懂得命题‘有……’吗？” [3]
对于对角线法证明，维特根斯坦指出，根据对角线方法，依赖于下一行的实数，才能确定康托尔数的下一位。这个过程是一直处于构造之中的，并不是已经完成的状态。“序列中始终有一个，它是否不同于对角序列这一点是不确定的。人们可以说：它们相互追随，趋于无穷，但总是原来的序列位居前面。” 康托尔的对角线方法包含了这种相互追随的序列，却又试图使本应在后的康托尔数倒放回来，这才导致了矛盾。
因此，维特根斯坦也是反对康托尔的对角线方法，认为康托尔证明中出现的矛盾，其实不是来自于假设的错误，而是来自于证明中使用了不适当的证明方法，这才导致了矛盾的出现。对于康托尔证明，维特根斯坦评论道：当一个证明所证明的东西超出了它的方法所允许的，我们总是应该保持怀疑。这可以叫做“夸大的证明”。
康托尔认为矛盾来自于假设错了，所以实数集不是可数集。然而在直觉主义者和维氏看来，康托尔数与一般的数是不相同的，康托尔数依赖于其定义所基于的可数集，并且与可数集中的任何一个元素都不相同。在定义康托尔数的时候，已经决定了后面想把康托尔数放回可数集，就会产生矛盾。因此，矛盾不是来自于假设前提的错误，而是来自于不正当的对康托尔数的定义和使用。
在直觉主义者和维氏看来，可数集应该是不断膨胀的集合，永远处于一个不断展开的过程。这样来理解的话，康托尔数是始终处于展开状态的，永远未完成的，我们只能根据当前的集合，得到当前的康托尔数。当某一时候康托尔数要反过来等于当前集合之外的某个数，这是可能的，并不会产生矛盾。因此，在直觉主义者看来，是因为康托尔证明中，在实无穷的意义，对康托尔数进行了过分的定义，并且在已完成的意义上来使用康托尔数，才导致了矛盾的产生。因此，应该放弃的是康托尔对康托尔数的定义，而不是像康托尔那样推断出假设的前提是错误的。如此，康托尔得出的结论是不适当的，对于直觉主义者是不可接受的。
综上，康托尔基于可数集上，在实无穷的意义上，定义了康托尔数，并且认为康托尔数也是集合中的一元，这样就产生了“非直谓性”（Impredicativity）。如果单单是“非直谓性”，也并不一定会导致矛盾。依据定义，康托尔数又不同于所依赖可数集中的任何一个元素，这个性质不妨称为“外在性”。康托尔数定义中的“非直谓性”和“外在性”合起来导致了矛盾。从直觉主义的角度，不承认实无穷，只承认潜无穷，因此就消解了“非直谓性”，康托尔数可以是一直处于构造之中，随着当前展开的可数集而变化，可以一直带有“外在性”，可以等于当前已展开的可数集以外的某一元素。所以对于直觉主义者，康托尔对角线方法的问题根源在于，对于可数集作了实无穷意义上的理解。
3、停机问题
康托尔提出对角线方法后，这个方法被应用到数理逻辑的各个领域。哥德尔1931年证明著名的不完全性定理时，也借鉴了对角线方法，构造出奇特的不可证明也不可否证的哥德尔语句。[4]从直觉主义的角度来看，也可以认为哥德尔语句是没有意义的。在一阶语言的应用中，我们不会用到哥德尔语句，正如我们不会在日常生活中说“我现在在说谎”这样没有意义的句子。作为直觉主义者，可以认同的是哥德尔定理中用到的递归函数论和哥德尔编码。[5]
哥德尔证明不完全性定理后，剑桥的图灵仔细研读了哥德尔的证明，在自己提出的图灵机计算模型上，平行地引入了不可计算的停机问题。[6]可以参考文献[7]。通俗的讲解可以参考戴维斯的《逻辑的引擎》[8]。以下简单介绍证明主要过程。
通过哥德尔编码，所有图灵机可以编码成自然数。假设所有的图灵机是M1,M2,……，它们对应的编码则是<M1>,<M2>,……。现在设想以<Mi>作为输入来运行图灵机Mi(i=1,2,…….)，可想而知，在i的不同取值下，有一些会停机，有一些则不会停机。不妨设情形如下图：
<M1> <M2> <M3> …
M1 不停机 停机 停机 …
M2 不停机 停机 不停机 …
M3 停机 不停机 不停机 …
… … … … …
现在定义自然数集合D={<Mi>|以<Mi>作为输入运行Mi不停机, i=1,2,……}如上例，可知D={<M1>, <M3>……}。
可以证明，集合D不是任何图灵机的停机集合。反证法：假设集合D是某台图灵机M的停机集合，那么考虑以<M>作为输入来运行M，会不会停机呢？考虑下图：
<M1> <M2> <M3> … <M>
M1 不停机 停机 停机 … …
M2 不停机 停机 不停机 … …
M3 停机 不停机 不停机 … …
… … … … … …
M 停机 不停机 停机 … ?
假设以<M>作为输入来运行M不停机，根据D的定义，<M>是D的元素，D又是M的停机集合，因此以<M>作为输入来运行M停机；假设以<M>作为输入来运行M停机，根据D的定义，<M>不是D的元素，D又是M的停机集合，因此以<M>作为输入来运行M不停机。矛盾。
因此假设错误，集合D不是任何图灵机的停机集合。进一步可以证明，集合D不是图灵可判定的，甚至不是图灵半可判定的。关于停机问题的其他证明，都可以归结到关于集合D的判定问题。
4、直觉主义视角下的停机问题
停机问题的证明过程，很明显地利用了对角线方法。因此，直觉主义和维特根斯坦对于对角线方法的评论都可以应用到停机问题。
在停机问题的证明中，基于实无穷的意义定义了集合D，然后证明了D不是任何图灵机的停机集合。
然而在直觉主义者和维氏看来，所有图灵机的数目是潜无穷的，它们的展开序列是一个潜在的不断构造出来的序列。而集合D是定义在图灵机的展开序列之上的，应该认为集合D中的元素也是潜在的处于不断的构造中的。
类似于维特根斯坦对于对角线方法的评论，图灵机序列与D中元素的展开序列是“相互追随，趋于无穷”的序列。依赖于下一行的图灵机，才能确定集合D的下一个元素。这个过程是一直处于构造之中的，并不是已经完成的状态。
这样来理解的话，我们只能根据当前的图灵机展开序列，得到当前集合D中元素的展开序列。当某一时候集合D要反过来等于当前图灵机序列之外的某个图灵机的停机集合，这是可能的，并不会产生矛盾。因此，在直觉主义者看来，是因为停机问题的证明中，在实无穷的意义，对集合D进行了过分的定义，并且在已完成的意义上来使用集合D，才导致了矛盾的产生。因此，应该放弃的是集合D在实无穷意义上的定义，而不是推断出假设的前提是错误的。如此，停机问题的证明是不适当的，对于直觉主义者是不可接受的。
5、结束语
以上基于直觉主义和维特根斯坦的思想，对于对角线方法和停机问题进行了反思。我们也可以从一般推理过程来看对角线方法。在对角线方法的反证过程中，都是基于某一可数集合，在实无穷的意义上，定义了一个新的元素，这个元素在可数集合之外。在潜无穷的意义上，我们可以有不同的看法。假设论域是一个可数集，我们可以说，任意一个有限的集合，存在一个元素，这个元素可以始终在集合之外。但是我们不能反过来说，存在一个元素，对于任意的集合，这个元素在集合之外。
在第三次数学危机后，对于经典数学产生了怀疑。在此基础上，基于对构造性直觉性的要求，产生了计算科学。因为计算科学是从数学中发展出来的，所以经典理论一般是从经典数学来观察计算科学，把计算科学纳入经典数学的一部分。这篇论文的观点是相反的，是站在构造性数学或计算科学的角度，反过来观察经典数学的基础。
作为形式主义者，沉醉于古典数学，不易接受直觉主义的观点，然而对于计算机科学，以能行性构造性为特征的科学，本身也是发源于构造主义数学和有穷可证性的科学，倒应该是与直觉主义接近的。令人惊讶的是，没有看过一本计算理论的书，尝试从直觉主义的角度来评论停机问题。在直觉主义者看来，停机问题没有意义，那么通过各种途径归约到停机问题的不可判定问题也将失去意义。
参考文献：
[1] Georg Cantor, Uber ein elementare Frage der Mannigfaltigkeitslehre, Jahresbericht der Deutsche Mathematiker-Vereinigung, vol. I (1891), pp. 75-78. (Original German text, as well as English translation, Available at http://uk.geocities.com/frege@btinternet.com/cantor/diagarg.htm)
[2] 贝纳塞拉夫,普特南编, 朱水林等译. 《数学哲学》. 商务印书馆，2003年
[3] 维特根斯坦著, 徐友渔,涂纪亮译.《维特根斯坦全集》第七卷. 河北教育出版社，2003年（第一篇附录三）.
[4] Kurt Gödel, “On formally undecidable propositions of Principia mathematica and related systems”, in Jean van Heijenoort (eds.), From Frege to Gödel, Cambridge, Massachusetts: Harvard University Press, 1967, pp. 596-616.
[5] 庄朝晖，《基于直觉主义对哥德尔不完全性定理的评论》，《厦门大学学报（哲社版）》2008年第2期
[6] Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. (online version: http://www.turingarchive.org/browse.php/B/12)
[7] Hopcroft等著，刘田等译，《自动机理论、语言和计算导论》，机械工业出版社，2005年8月
[8] 戴维斯著，张卜天译，《逻辑的引擎》，湖南科学技术出版社，2005年5月
背景介绍
直觉主义
20世纪初关于数学基础的讨论中，出现了三个大的流派，一个是弗雷格和罗素倡导的逻辑主义，一个是布劳维尔倡导的直觉主义，一个是希尔伯特倡导的形式主义。关于直觉主义，布劳维尔说道：“并不存在非经验的真理，逻辑也并非是发现真理的绝对可靠的工具。这个观点被数学所接受，远比被实际生活和被科学接受来得晚。严格地依照这个观点来进行探讨，并且专用内省构造的方法来推演定理的数学，叫做直觉主义数学。”直觉主义的主要特点是：反对实无穷，认为只有潜无穷；反对基于无穷集上排中律的证明，强调构造性的证明。
直觉主义的先驱是克罗内克和彭加勒等。直觉主义有句著名的口号：“存在等于被构造”。
希尔伯特纲领
直觉主义的思想给经典数学提出了挑战，希尔伯特为了应对直觉主义的挑战，提出了希尔伯特纲领：将古典数学表述为形式系统，并证明该形式系统的无矛盾性。在自然数系统方面，他的目标是使用一阶算术来保证自然数系统，并证明一阶算术的无矛盾性，来说服直觉主义者。然而哥德尔不完全性定理表明，如果一阶算术是一致的，那么一阶算术是不完全的，并且一阶算术的一致性在一阶算术内部是不可证明的。
哥德尔不完全性定理从形式主义的内部宣告了希尔伯特纲领的失败。
维特根斯坦对于直觉主义的发展
前期维特根斯坦：1918年写作《逻辑哲学论》，认为自己已经解决了所有可以解决的问题，“对于（其余）不可说的东西，只有保持沉默”，因此就到小学去当老师。
1928年，维特根斯坦曾经听过布劳维尔在维也纳关于“数学、科学和语言”的讲座，这次讲座把他又带回了哲学界。哥德尔当时也在场，这是他唯一一次见过维特根斯坦。据说，哥德尔致力于数理逻辑的研究，也是受到了布劳维尔讲座的影响。后期的维特根斯坦，可以说他有所批判地发展了直觉主义的观点。
后期维特根斯坦：《哲学研究》、《论数学的基础》等。有趣的是，维特根斯坦对哥德尔不完全性定理进行过评论。哥德尔读了维特根斯坦的评论后，认为维氏没有理解他的定理。此后，维氏的这段评论在数学哲学界，普遍被认为是“臭名昭著”的。维氏评论的中文翻译可参考文献 。近年来，一些学者也倾向于为维氏评论寻找好的解读方式，这些解读往往了是从形式主义的角度。另外也很有趣的是，维特根斯坦在剑桥开一门《数学基础》的课程，图灵参加了课程。在这门课程中，维特根斯坦极力想说服图灵接受他的观点。然而，显然图灵没有接受维特根斯坦的观点，反而在不可计算的道路上越走越远，跑到美国跟Church读博士提出了不可计算的层次性。
可以认为，维特根斯坦发展了布劳维尔的直觉主义。他的一些著名的话：
“数学家是发明者，不是发现者。”
“当然，数学在某种意义上是知识的一个分支，――不过它也仍然是一种活动。”
逻辑不是数学的基础……“数理逻辑只是数学的内容。罗素的演算体系并不是基本的；它只是另一种演算体系。”
“一个词在语言中的用法就是它的意义。”
倘罗素尚未在弗雷格的数学体系中发现那种矛盾之前，可以说那种矛盾并不存在，因为一种矛盾只有当它出现时才成为一种矛盾。只要还没有提出一种用以发现矛盾的程序，“我们的推理是否最终会导致矛盾”这样一种猜想是没有意义的。
“逻辑和直觉各有其必要的作用。二者缺一不可。唯有逻辑能给我们以可靠性，它是证明的工具；而直觉则是发明的工具。”
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 理论计算机科学 』 → 基于直觉主义对对角线方法和停机问题的评论[原创]
(订阅本版)
2008/6/2 15:34:00
顶端 
基于直觉主义对对角线方法和停机问题的评论[原创](12275字) － chzhuang，2008年6月2日
新浪微博
