希尔伯特的希望是，对于任何一串代表一个数学命题的符号，譬如讲P，人们应能证明或者P或者～P，依P是真的还是伪的而定。我们在这里必须假定该符号串在构造上是语法正确的， 也就是满足所有形式主义的记号法则，诸如括号必须正确地配对等等――使得P具有定义清楚的真的或伪的意义。如果希尔伯特的希望能被实现，这甚至使我们不必为这些命题的意义忧虑！P仅仅为一语法正确的符号串。如果P为一道定理（也就是可在系统内证明P），则符号串P的真值就可被赋于真。另一方面，如果能证明～P为定理的话，则可被赋于伪。为了使这些有意义，我们除了完备性外还需要一致性。也就是说，不应有P和～P都为定理的符号串P。
否则P会同时是真的和伪的！
把数学陈述中的意义抽走，只把它们当成某种形式数学系统的符号串是形式主义的数学观点。有些人喜欢这种观点，而数学就变成一种“无意义的游戏”。然而，我不欣赏这种观点。确实是“意义”而非盲目的算法计算才赋于数学以实质。庆幸的是，哥德尔给了形式主义以毁灭性的打击！让我们看看他是怎么做的！哥德尔定理哥德尔论证的部分是非常繁琐和复杂的。然而我们没有必要去考察那纷乱的部分。另一方面，其中心思想是简单、漂亮和深刻的。这就是我们可能鉴赏的部分。其复杂的部分（其中不乏许多巧妙之处）仔细说明如何把形式系统的个别步骤法则以及不同公理的使用实际地编码成算术运算。（意识到这是一个富有成果的可进行的工作正是其深刻部分的一个方面！）为了实现编码，人们需要找到用自然数来对命题编号的某种方便方式。一种方法就是简单地对形式系统每个特定长度的符号串使用某种“字典”顺序，按照串的长度还有一个总的顺序。（这样，长度为1的串可按字母顺序排列，接着的是按字母顺序排列的长度为2的串，再后面是长度为3的串等等）。这叫做字典顺序①。哥德尔原先用的编号顺序更复杂，但是这种差异对我们不重要。我们将特别关心依赖于单变量的命题函数，譬如上述的G（w）。令应用于w 的第n个这样的命题函数（在选定的符号串顺序下）为Pn（w）。
如果我们愿意的话，可以让编号稍微有点“草率”，这样我们的一些表式可能语法上不正确。（这可使算术编码比在试图略去这种语法不正确的表式时容易得多。）如果Pn（w）是语法正确的，它就是关于两个自然数n和w的定义好的特定的算术陈述。准确的为哪一个算术陈述应依所选取的特定编号系统的细节而定。那是属于论证的复杂部分，在此不予关心。构成系统中的某一定理的证明的一串命题在选定的编序方案中也可用自然数编号。令n ？表示第n个证明。（这里我又一次使用“草率的编号”，对于某些n的值，可能表示式“ ”的语法不正确，并因此没有证明什么定理。） n ？现在考虑如下的依赖于自然数w的命题函数～ 证明 （ ） 。 ？ x＇ P w ＇ x w在方括号中的陈述的一部分使用了文字，但它是完全精确定义的。它断言第x个证明实际上是Pw（）应用于值w本身的命题的证明。方括号之外的被否定的存在量衡用以移走一个变量（“不存在一个x使得……”），这样我们得到了一个只依赖于一个变量w的算术的命题函数。此整个表达式断言不存在Pw（w）的证明。我假定它的语法是正确的（甚至如果Pw（w）
的语法不正确――在这种情形下该陈述仍然是对的，因为一个语法错误的① 存在以日常术语来表述罗素佯谬的十分好笑的方法。想象一个图书馆中有两本目录书，一本目录书刚好列出了所有引用过它们自己的书，另外一本是刚好所有不引用它们自己的书。试问第二本目录书应列到那一本目录书中？表达式是不能被证明的）。由于事实上我们已假设将其转换成算术，所以上面实际上是关于自然数的某一算术的陈述（方括号中的部分为定义得很好的关于两个自然数x和w的算术描述）。该陈述是可以被编码成算术，但这一点并不假设是明显的。为了说明这样的陈述的确可被编码，涉及到哥德尔论证的复杂部分的主要“困难工作”。正和前面一样，它究竟为那个算术陈述将依赖于编号系统的细节，并大大地依赖于我们形式系统的公理和法则的结构细节。由于所有那些都属于复杂的部分，我们在这里不关心其细节。
我们已将所有依赖于单变量的命题函数编号，所以我们刚刚写下的必须赋予一个数。让我们把这个数记作k。我们的命题函数是在表上的第k个。这样～ 〔 证明 （ ）〕＝ （ ）。 ？ x P w P w w k x现在对特殊的w值即w＝k来考察这一个函数。我们得到～ 〔 证明 （ 〕 （ ）。 ？ x P k ＇ = P k k k x这个特定的命题Pk（k）是完好定义（语法正确）的算术陈述。它是否可在我们形式系统中有一个证明呢？它的反命题～Pk（k）有证明吗？这两个问题的答案都是“否”。从考察作为哥德尔步骤基础的意义可以看到这一点。虽然Pk（k）仅仅是一个命题，我们已经把它这样的构造，使得写在左边的断言为“在这系统中不存在命题Pk（k）的证明”。如果我们非常仔细地设定好我们的公理和步骤法则，并假定做了正确的编号，则在这系统中不能存在这道Pk（k）的证明。因为如果存在这样的证明，则Pk（k）实际断言的陈述的意义，也就是不存在证明，将是错的，这样作为一个算术命题的Pk（k）就必须是错的。我们的形式系统不应构造得这么坏，使得它在实际上去允许证明错的命题！所以情况只能是Pk（k）在事实上无法证明。而这正是Pk（k）要告诉我们的。所以断言Pk（k）必须是一真的陈述，这样Pk（k）作为算术命题必须为真。这样，我们已经发现了在该系统中没有证明的真的命题！
关于它的反命题～Pk（k）我们可以说些什么呢？最好我们也不能找到它的证明。我们刚刚建立了～Pk（k）必须是错的（因为Pk（k）是真的），而我们假定不能在此系统中证明错的命题！这样无论Pk（k）还是～Pk（k）
在我们的形式系统中都是不可证明的。哥德尔定理就这样地被建立起来了。数学洞察请注意，在这里发生了某种非常奇异的事情。人们经常把哥德尔定理当作某种负面的东西――显示了形式化数学推理的不可避免的局限性。不管我们自以为是多么有智慧，总有些命题漏网。但是，我们是否要为这一特殊的命题Pk（k）忧虑呢？在上述的论证过程中，事实上我们已建立了Pk（k）是一个真的陈述！尽管在该系统中不能形式地证明这个事实，不管怎么样我们已设法看到了这一点。真正需要忧虑的人倒是严格的数学形式主义者。这是因为从这推理我们已确定形式主义者的“真理”概念不可避免地是不完备的。不管把哪一个（一致的）形式系统应用于算术，总存在一些命题我们可以看到是真的，但用形式主义者提出的上述过程不能赋予真理值为真的命题。一个严格的形式主义者试图躲开这个情况的可能方法也许是根本不提真理的概念，而仅仅讲在某一固定的形式系统中的可证明性。然而，这显得非常局限。由于哥德尔论证的基本点利用关于何者实际上为真的何者不真的推理，人们甚至都不能作出上述的论证2。一些形式主义者采用更“程序化”的观点，断言不去忧虑诸如Pk（k）这样的陈述，由于它们作为算术命题来讲极端复杂和乏味。这些人会宣称：
是的，存在一些诸如Pk（k）的古怪的陈述，对于这些陈述我的可证明性或真理的概念不和你们的真理的内禀概念相符合。但是那些陈述却不会在严肃的（至少在我所感兴趣的那种）数学中出现。这是因为作为数学而言，这样的陈述是荒谬绝伦地复杂和不自然。的确，像P（k）这样的作为关于数的数学描述的命题，被全部写出时，会是极端繁琐和古怪的。但是近年来，人们提出了一些具有非常可接受特性的相当简单的陈述，它们实际上等价于哥德尔类型的命题3。这些命题不能从正常的算术公理得到证明，而是从公理系统本身所具有的 “显然正确”的性质而来。
对我来讲，形式主义者对“数学真理”缺乏职业的兴趣，似乎是对数学哲学所采取的非常古怪的观点。而且，也确实不是那么切合实际。当数学家在进行推理时，他们没必要继续不断地检查他们的论证是否可按照某个复杂的形式系统的公理和步骤法则来表达。他们只要肯定其论证是确定真理的有效方法即可。哥德尔的论证是另一类有效步骤。这样我似乎认为，Pk（k）正和能利用预先给出的公理和步骤法则更传统地得到的数学真理一样好。
建议进行如下步骤。我们把Pk（k）接受为真正有效的命题，并简单地表示为G0；这样可以把它作为一个额外的公理加到系统中去。当然，我们新的修改的系统又有了它自己的哥德尔命题，譬如讲G1，它又是一个完全有效的关于数的描述。我们相应地又把G1加到我们的系统，由此得到进一步修改的系统，它又有自己的哥德尔命题G2（又是完全有效的），我们又把它合并进去，得到了下一个哥德尔命题G3，再合并等等，无限次地重复这一过程。当我们允许使用整列的G0，G1，G2，G3……作为附加的公理时，结果的系统是什么呢？它可以是完备的吗？由于现在我们有了一个无限制（无限）的公理系统，哥德尔步骤能否适用也许不太清楚。然而，不断附加哥德尔命题是一个完全系统化的方案，我们可将其当作通常的公理和步骤法则的有限的逻辑系统来重述。这一系统又有它自己的哥德尔命题，譬如讲Gw，它又能被用来作为公理去附加，而形成了所得到的系统的哥德尔命题Gw＋1。正如上面那样重复，我们得到了命题Gw，Gw＋1，Gw＋2，Gw＋3……的表，所有都是关于自然数的完全有效的陈述，并可附加到我们的形式系统中去。这又是完全系统化的，它导致一个包罗这一切的新系统；但是它又有自己的哥德尔命题，譬如讲Gw＋w，我们可将其重写成Gw2，而整个步骤又可重新开始，我们得到一个新的无限的、却是系统的公理Gw2，Gw2＋1，Gw2＋2等等的表，它又导致一个新的系统以及一个新的哥德尔命题Gw3。重复这整个过程，我们得到Gw4然后还有Gw5等等。现在这一步骤又是完全系统化的，并具有自身的哥德尔命题Gw2。
这会有终结吗？在一种意义上讲没有；但它导致我们进入不能在此作细致讨论的某些困难的数学考虑。1939年阿伦？图灵在一篇论文4中讨论了上面的步骤。事实上，令人印象深刻的是，任何真的（但普适量化的）
算术命题都可由这类重复的 “哥德尔化” 步骤得到！ 可参阅飞费曼 （1988）。
然而，这在一定程度上依赖于我们如何实际上决定一个命题真伪的问题。
在每一阶段关键的问题是如何把哥德尔命题的无限族合并，从而提供一个单独的（或有限数目的）附加公理。这就要求我们的无限族能以某种算术的方式被系统化。为了保证正确地完成所预想的系统化，我们要使用系统之外的直觉――正如我们首先为了看到Pk（k）是一道真的命题所做的那样。正是这些直觉是不能被系统化的――它必须超越于任何算法行为！
我们利用直觉得出哥德尔命题Pk（k）实际上是算术中的真的陈述，是被逻辑学家称之为反思原理步骤的普遍类型的一个例子：这样，由“反思”公理系统和步骤法则的意义，并使自己坚信这些的确是得到数学真理的有效方法，人们可能把这直觉编码成进一步的真的、不能从那些公理和法则推导出来的数学陈述。正如上面概述的，推出Pk（k）的真理性依赖于这样的一个原则。另一个与原先哥德尔论证相关（虽然在上面没提及）的反思原则依赖于如下的事实去推出新的数学真理，即我们已经相信能有效得到数学真理的公理系统实际上是协调的。反思原理经常涉及有关无限集合的推理，人们使用的时候一定要小心，不要过于接近会导致罗素类型佯谬的论证。反思原理为形式主义推理提供了反题。如果人们很小心的话，就能使他跳出任何形式系统的严格限制之外，并得到原先似乎得不到的新的数学洞察。在我们的数学文献中会有许多完全可接受的结果，其证明需要远远超越原先的算术标准形式系统的法则和公理的洞察。所有这些表明，数学家得到真理判断的心理过程，不能简单地归结为某个特别形式系统的步骤。虽然我们不能从公理推出哥德尔命题Pk（k），却能看到其有效性。这类涉及反思原理的“看见”需要数学的洞察力，而洞察不是能编码成某种数学形式系统的纯粹算法运算的结果。我们将在第十章再回到这个论题上来。
读者也许会注意到在建立Pk（k）“不可证明性”的真理和罗素佯谬的论证之间的相似性，还和图灵解决停机问题的图灵机不存在的论证也有相似性。这些相似性不是偶然的。在这三者之间存在有强大的历史连接的脉络。图灵是在研习哥德尔工作之后才找到它的论证的。哥德尔本人非常熟悉罗素的佯谬，并能把这一类将逻辑延伸得这么远的佯谬的推理转化成有效的数学论证。（所有这一切论证都起源于前一章100页描述的康托的“对角线删除法”。）
为什么我们应该接受哥德尔和图灵的论证，而必须排斥导致罗素佯谬的推理呢？前者更直截明了得多，作为数学论证而言更出人意表，而罗素佯谬则依靠牵涉到“巨大”集合的更为模糊的推理。但是必须承认，其差别并不真像人们以为的那么清楚。弄清这些差别的企图是整个形式主义观念的强大动机。哥德尔的论断表明，严格的形式主义者的观点是不能成立的，但他没有向我们指出另外完整的可信赖的观点。我认为这问题仍未解决。当代数学中为了避免导致罗素佯谬的“巨大的”集合的推理的类型所实际采用①的步骤不能完全令人满意的。而且，它仍然试图以明晰的形式主义的术语来表达，换句话说，按照我们并不完全相信不会出现矛盾的术语来描述。无论情况如何，依我看来，哥德尔论证的清楚推论是，数学真理的概念不能包容于任何形式主义的框架之中。数学真理是某种超越纯粹形式主义的东西。甚至即使没有哥德尔定理，这一点也是清楚的。在我们去建立一个形式系统任何试图中，如何决定采取什么公理和步骤法则呢？我们在决定采取法则的指导总是，在给定系统的符号的“意义”下对何为“自明正确”的直觉理解。根据关于“自明”和“意义”的直观理解，我们如何决定采用哪个形式系统是有意义的，哪个是没意义的呢？以自身具有一贯性的概念来决定当然不够。人们可以有许多自身具有一贯性但在含义上没有“意义”的系统，它们的公理和步骤法则具有错误的意义，或者根本没有意义。甚至在没有哥德尔定理时，“自明”和“意义”的概念仍然是需要的。
然而，若没有哥德尔定理，人们可能想象“自明”和“意义”的直觉① 虽然费马的全部命题F 的真伪性仍然未知， 但是个别命题G（0）， G（1）， G（2）， G3S（3）， …直到大约G（125000）的真理性是�
小提示：按 回车 [Enter] 键 返回书目，按 ← 键 返回上一页， 按 → 键 进入下一页。
赞一下
添加书签加入书架