皇帝新脑-17

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