按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
崖碜詈蠖ɡ怼笔且焕嗨频睦印８莶扯募酥本踔饕澹衷谡庖坏烂饧炔皇钦娴囊嗖皇俏钡模匆残砘岜涑善渲械囊恢帧６晕依唇玻д胬淼恼庵种鞴坌院褪奔湟览敌允遣豢衫碛鞯摹ＪЫ峁欠窕蚝问北唤邮芪健爸っ髁恕钡娜肥且桓鲋鞴鄣氖绿濉５鞘д胬聿挥θ【鲇谡庑┮览瞪缁岬呐芯荨６杂谌嗣窍Ｍ芸煽康赜美疵枋鑫锢硎澜绲氖В哂兴媸奔涠涞恼胬砀拍钪辽倏梢运凳寝限蔚暮筒涣钊寺獾摹２⒎撬械闹本踔饕逭叨疾捎貌扯茄苛业墓鄣恪＞」苷庋踔炼杂谀切┩楣乖熘饕宓哪康牡娜艘彩钦饷慈衔本踔饕骞鄣阆匀皇谴至拥摹＞徒鼋鲆蛭嗣强稍市硎褂玫氖评淼睦嘈凸诰窒薜脑颍苌俚贝Ъ以敢馊娜獾刈匪嬷本踔饕濉�
我已经简介了当代数学哲学的三个主流：形式主义、柏拉图主义和直觉主义。我并不掩饰自己强烈同情柏拉图主义的观点，也就是数学真理是绝对的、外在的、永恒的，并不基于人造的判据之上；数学对象具有超越时间的自身的存在，既不依赖于人类社会，也不依赖于特定的物体。我把这种观点贯穿于本节、上一节以及
第三章的结尾处。我希望读者准备在这
一点上和我大致同心同德。它对于后面要遇到的大量内容都很重要。从图灵结果到类哥德尔定理我在阐明哥德尔定理时忽略了许多细节，并且也忽略它的论证中或许在历史上的最重要的部分；这就是被叫做公理一致性的“不可决定性”。
我在这里的目的不在于强调这“公理一致性的可证明性的问题”。这个问题对于希尔伯特及其同代人是如此之重要。我只是表明，利用所考虑的形式系统公理和法则某个特殊的哥德尔命题既不是可证明的也不是可证伪的。但是利用我们对该问题中运算意义的直觉可以清楚地看到，它是一个真的命题！
我提到过，图灵在研究了哥德尔的著作后发展了自己后来的论证，以确立停机问题的不可解性。这两个论证有许多共同的地方，事实上，哥德尔结果的关键方面可利用图灵步骤直接推出。让我们看看这是如何进行的，并因此对哥德尔定理的背后的东西有某种不同的洞察。一个形式数学系统的主要性质是，决定某一给定的符号串是否构成该系统中给定的数学断言的证明应是可计算的事体。表达数学证明的全部要点毕竟在于对于什么是有效推理、什么是无效推理不必作进一步的裁决。
以完全机械的和原先预定的办法来检查一个想象的证明是否确实是一个证明应是可能的；也就是说必须有检查证明的算法。另一方面，为提出的数学陈述去找证明（或证伪），我们并不要求它必须是算法的事。
事实上，在任何形式系统中只要某种证明存在，就总有找到证明的算法。由于我们必须假定该系统是以某种符号语言来表达的，这种语言是按照符号的某些有限“字母”来表达的。正如以前一样，让我们把符号串以字典的方式编序。我们记得这表示对于固定的串的长度按字母编序，先取所有串长为1的，然后串长为2的，串长为3的等等（见122页）。这样，我们就把所有正确建立起来的证明按照这个字典方案进行编序。我们有了证明的列表，也就有了该形式系统的所有定理的列表。这是因为定理刚好是出现在正确构造的证明的最后一行的命题。这种列表完全是可计算的：由于不管系统的符号串是否有作为证明的意义，可以先考虑所有的串的字典列表，然后用我们的证明检查算法去检验其是否为一个证明，若不是则抛弃之；然后以同一方法检验第二个，若不是证明则抛弃之；然后第三、第四等等。如果有一个证明，我们则可用这种办法最终在这一列表的某一处找到它。
这样，如果希尔伯特已经成功地找到它的公理和步骤法则的数学系统，该系统足够有力到能使人们用形式证明决定任何在该系统中正确表达的数学命题的真伪――则就会有一般的算法方法去决定任何这种命题的真理性。为什么这样呢？因为用上述的步骤，如果最终在某个证明的最后一行遇到了我们所寻求的命题，则我们就证明了该命题。反之，如果我们最终遇到的一行是我们命题的否定，则我们就证伪了它。如果希尔伯特方案是完备的，这种或那种的终局就总会发生（并且，如果是协调的，两者永远不会同时发生）。这样，我们的机械步骤总会在某一阶段结束，而我们就应有一种决定系统所有命题真伪的普通算法。这就和第二章阐述的图灵结果相冲突，也就是说不存在决定数学命题的一般算法。因而我们实际上证明了哥德尔定理，就是说希尔伯特期望的方案在刚刚讨论的意义上不可能是完备的。
由于哥德尔所关心的形式系统的类型只对算术命题而不是对一般的数学命题足够，所以事实上哥德尔定理比上述的更特定。我们是否能安排只用算术的运算去实现图灵机的所有必须的运算呢？换句话说，是否所有自然数的可计算功能（也就是图灵机动作的结果，递推的或算法的功能）可按通常的算术表达呢？我们几乎真的可以，但还不是。我们需要在算术和逻辑（包括 和 ）的标准法则外加上一个额外的运算。这个运算简单地 〃选择为“使得K（x）成立的最小自然数x”，这儿K（）是任何给出的算术地可计算的命题函数――并假定存在这样的一个数，也就是 〔 （ ）〕为真的。（如果没有这样的一个数，则 x k x我们的运算在试图寻求所需的不存在的x时就会“无限地算下去”①。）无论如何，在图灵结果的基础上前面的论证确认了，把数学的一切分支归结为某个形式系统中的计算的希尔伯特规划的确是不成立的。
就此而言，这一步骤并没有这么清楚地显示，在这系统中我们具有真的、但不能证明的一个哥德尔命题（例如Pk（k））。然而，如果我们回忆在第二章给出的关于“如何超过算法”（参阅72页）的论证，我们就看到了可以做非常类似的事情。我们在那个论证中指出，如果有决定图灵机动作是否停止的任何算法，我们便能制造图灵机的一个动作，我们看到该动作不停止，但是该算法看不到这一点。（记得我们坚持过，当一台图灵机将要停止时，该算法必须正确地通知我们，虽然在图灵机动作不停止――它会永远运行下去的情形，有时它不能告诉我们。）鉴于上述的哥德尔定理的情形，我们具有利用洞察可以看到实际上必须为真的命题（图灵机的不停运行），但是给定的算法动作不能告诉我们这些。
① “ 集合”和“族”之间存在有差异，集合可允许集中在一起而形成另外的集合或族，但是族不能允许集中在一起而形成任何种类的更大的聚合，这被认为“太大”了。然而除了这种循环的论述，即集合是那种确能聚集成另外聚合的聚合之外，不存在决定何时聚合可被当作集合或只能被当作族考虑的法则。递归可列集存在一种按照集论的语言形象地描述图灵和哥德尔基本结果的方法。这就使得我们可以避免按照特别的符号主义或形式系统的任意描述，而使本质问题呈现出来。我们将只考虑（有限或无限的）自然数的集合0，1，2，3，4，…，这样我们将考察这些聚合，诸如｛4，5，8｝，｛0，57，100003｝， ｛6｝，｛0｝， ｛1，2，3，4，…，9999｝，｛1，2，3，4，…｝，｛0，2，4，6，8，…｝，甚至整个集合N=｛0，1，2，3，4，…｝或者空集φ=｛｝。我们将只关心可计算性的问题，也就是：“自然数的何种集合可由算法产生，何种不能？”
为了提出这样的问题，如果愿意的话，我们可把每一单独的自然数n，在一特别的形式系统中，以特定的符号串来表示。按照系统中（“语法正确”地表达的）命题的某一字典顺序，n表示“第n个”符号串，譬如讲Qn。则每一自然数代表一个命题。形式系统的所有命题的集合是由整个集合N来代表， 例如， 形式系统的定理可被认为自然数的某一个更小的集合，例如集合P。然而，命题的任何特殊编号系统细节不是重要的。为了在自然数和命题之间建立一种对应，我们需要的是能从任一个自然数n得到它对应的（在一种适当的符号记法中写出的）命题Qn的已知算法，以及从Qn得到n的另一个已知算法。假定已知这两种算法，我们就能随心所欲地把一个特定形式系统的命题集合和自然数集合N相等同。让我们选择一个形式系统，它是协调的，并广泛得足以包括所有图灵机的所有动作――并且在以下的意义上是“有意义的”，即它的公理和步骤法则可认为是“自明地真的”。现在，这形式系统的命题Q0，Q1，Q2，Q3，…中的一些实际上在该系统中有证明。这些“可证明的”命题有一些属于N的某一个子集的数字，这事实上就是上面考虑的定理的集P。我们事实上已经看到了在某一个给定形式系统中存在一种一个接一个产生具有证明的所有命题的 。（正如早先概述的，“第 个证明” 是从 算法 n n n ？
算法地得到的。所有我们要做的是去看第n个证明的最后一行，以发现在系统中可证明的第n个命题，也就是第n个“定理”。）这样，我们就有了一个接一个（也许会有重复――但这无所谓）产生P的元素的算法。
一个可用某种算法以这种方式产生的集合，譬如P， 叫做递归可列的。
注意，在系统中可被证伪――也就是其否定的命题可被证明的命题的集合也类似地为递归可列的，因为我们可简单地列举这可证明的命题。在此过程中取它们的否定。存在许多N的其他递归可列的集，我们不想介绍把它们定义出来的形式系统。递归可列集的简单例子