皇帝新脑-13

“不存在自然数w，x，z，z使得.”。其意思（到第一方括号的“非”符号处结束）为：“对于所有的自然数w，x，y，z下述不真.”。这和前面在逻辑上是相同的。我们需用字母来表示整个命题，为此目的我用大写字母P，Q，R，S，.。如下的一个命题事实上为上面的费马的断言：F $w，x，y，〔(x+1) w+3 +(y+1) w+3 =(z+1) w+3〕＝～z一个命题也可依赖于一个或更多的变量；例如，我们也许对某一特殊的一个命题也可依赖于一个或更多的变量；例如，我们也许对某一特殊的指数w+3下的费马断言感兴趣：G(w) =～$xyz 〔(x + )w+3 + (y + 1) w+3 = w +3,,1 (z + 1) 〕,这样G（0）断言“没有一个立方可代表正数立方之和”，G(1)对四次方作同样断言，等等。（注意之后的w没有出现。）现在费马断言是说，$G（w）对所有的w成立。G（）是一个所谓的命题函数，也就是依赖于一个或多个变量的命题的例子。系统的公理是由一般命题的有限罗列所构成，假定在符号的意义已给定的情形下，这些命题的真理性是不证自明的。例如，对于任何命题或命题函数P，Q，R（），在我们公理之中有其“自明的真理性”清楚地可由其意义所确定。（第一个简单地断言：“如果P和Q都为真，那么P为真”；第二个断言：“P不真的断言为不真”和“P为真”是等价的；第三个可用上面给出的“费马最后定理”的两种叙述方法的逻辑等价性作为例子）。我们还可包括基本的算术公理，诸如尽管人们也许宁愿从某些更初等的东西建立这些算术运算，并将这些陈述作为定理导出。步骤法则是诸如这样（自明）的东西：“从和P TQ我们可推出QP ”，x而得出的任何命题”。这些是告诉我们如何从已成立的命题引出新命题的方针。现在从公理开始，然后不断重覆应用步骤法则，就可以建立起一长串的命题。我们在任何阶段都可再使用这些公理，并且总可以不断使用任何我们已经添加到越来越长的表上的命题。任何正确地集合到表上的命题都被称作定理（虽然它们中有许多是相当无聊和无趣的）。如果我们有一个要证明的特定的命题P，则我们可去找一个表，这个表按照这些法则正确地集合起来，并用我们特定的命题P作为终结。这样的表在我们的系统中为我们提供了一个P的证明；而P就相应地成为一道定理。希尔伯特规划的思想是，对于任何定义好的数学领域，去找一足够广①一个集合表示事物的整体——可被整体地处理的物理对象或数学概念。在数学中，集合中的一个元素（也就是成员）自身经常为一集合、因为集合可以被收集在一起而形成集合。这样人们可以考虑集合的集合以及集合的集合的集合，等等。泛的公理和步骤法则的表，使得所有适合于该领域的正确的数学推理的形泛的公理和步骤法则的表，使得所有适合于该领域的正确的数学推理的形做诸如“费马最后定理”的陈述）。考虑比这更一般的数学领域在这里对我们并无益处。算术已经是足够一般到可以应用哥德尔步骤的地步。如果我们能够接受这样的事实，即这个公理和步骤法则的广泛系统，按照希尔伯特规划，的确把算术给予我们，那么它就为我们提供对算术中任何命题数学证明的“正确性”的确定判据。人们存在过希望，这样的公理和法则系统也许是完备的，也就是它会使我们在原则上决定任何可在此系统中表述的数学陈述的真伪。希尔伯特的希望是，对于任何一串代表一个数学命题的符号，譬如讲P，人们应能证明或者P或者～P，依P是真的还是伪的而定。我们在这里必须假定该符号串在构造上是语法正确的，也就是满足所有形式主义的记号法则，诸如括号必须正确地配对等等——使得P具有定义清楚的真的或伪的意义。如果希尔伯特的希望能被实现，这甚至使我们不必为这些命题的意义忧虑！P仅仅为一语法正确的符号串。如果P为一道定理（也就是可在系统内证明P），则符号串P的真值就可被赋于真。另一方面，如果能证明～P为定理的话，则可被赋于伪。为了使这些有意义，我们除了完备性外还需要一致性。也就是说，不应有P和～P都为定理的符号串P。否则P会同时是真的和伪的！把数学陈述中的意义抽走，只把它们当成某种形式数学系统的符号串是形式主义的数学观点。有些人喜欢这种观点，而数学就变成一种“无意义的游戏”。然而，我不欣赏这种观点。确实是“意义”而非盲目的算法计算才赋于数学以实质。庆幸的是，哥德尔给了形式主义以毁灭性的打击！让我们看看他是怎么做的！哥德尔定理哥德尔定理纷乱的部分。另一方面，其中心思想是简单、漂亮和深刻的。这就是我们可能鉴赏的部分。其复杂的部分（其中不乏许多巧妙之处）仔细说明如何把形式系统的个别步骤法则以及不同公理的使用实际地编码成算术运算。（意识到这是一个富有成果的可进行的工作正是其深刻部分的一个方面！）为了实现编码，人们需要找到用自然数来对命题编号的某种方便方式。一种方法就是简单地对形式系统每个特定长度的符号串使用某种“字典”顺序，按照串的长度还有一个总的顺序。（这样，长度为.. 1的串可按字母顺序排列，接着的是按字母顺序排列的长度为.. 2的串，再后面是长度为.. 3的串等等）。这叫做字典顺序①。哥德尔原先用的编号顺序更复杂，但是这种差异对我们不重要。我们将特别关心依赖于单变量的命题函数，譬如上述的.. G（w）。令应用于w 的第.. n个这样的命题函数（在选定的符号串顺序下）为..Pn(w)。如果我们愿意的话，可以让编号稍微有点“草率”，这样我们的一些表式可能语法上不正确。（这可使算术编码比在试图略去这种语法不正确的表式时容易得多。）如果.. P n（w）是语法正确的，它就是关于两个自然数.. n和.. w的定义好的特定的算术陈述。准确的为哪一个算术陈述应依所选取的特定编号系统的细节而定。那是属于论证的复杂部分，在此不予关心。构成系统中的某一定理的证明的一串命题在选定的编序方案中也可用自然数编号。令..n表示第.. n个证明。（这里我又一次使用“草率的编号”，对于某些n的值，可能表示式“.n ”的语法不正确，并因此没有证明什么定理。）现在考虑如下的依赖于自然数.. w的命题函数～$x[. x 证明Pw（）。w]在方括号中的陈述的一部分使用了文字，但它是完全精确定义的。它断言第.. x个证明实际上是.. P w（）应用于值.. w本身的命题的证明。方括号之外的被否定的存在量衡用以移走一个变量（“不存在一个.. x使得..”），这样我们得到了一个只依赖于一个变量.. w的算术的命题函数。此整个表达式断言不存在.. P w（w）的证明。我假定它的语法是正确的（甚至如果.. P w（w）的语法不正确——在这种情形下该陈述仍然是对的，因为一个语法错误的..①存在以日常术语来表述罗素佯谬的十分好笑的方法。想象一个图书馆中有两本目录书，一本目录书刚好列出了所有引用过它们自己的书，另外一本是刚好所有不引用它们自己的书。试问第二本目录书应列到那一本目录书中？表达式是不能被证明的）。由于事实上我们已假设将其转换成算术，所以上面实际上是关于自然数的某一算术的陈述（方括号中的部分为定义得很好的关于两个自然数x和w的算术描述）。该陈述是可以被编码成算术，但这一点并不假设是明显的。为了说明这样的陈述的确可被编码，涉及到哥德尔论证的复杂部分的主要“困难工作”。正和前面一样，它究竟为那个算术陈述将依赖于编号系统的细节，并大大地依赖于我们形式系统的公理和法则的结构细节。由于所有那些都属于复杂的部分，我们在这里不关心其细节。我们已将所有依赖于单变量的命题函数编号，所以我们刚刚写下的必须赋予一个数。让我们把这个数记作k。我们的命题函数是在表上的第k个。这样. xw （）。～$x〔证明Pw （）〕＝Pk w现在对特殊的w值即w＝k来考察这一个函数。我们得到x . k （）。～$ 〔x证明Pk （〕]=P k 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）忧虑呢？在上述的论证过程中，事实上我们已建立了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）是一道真的命题所做的那