哥德尔使计划落空

与弗雷格和康托尔对实证主义的局限性的不满相呼应，哥德尔承认，正是通过拒斥那些思想，他才有可能看到被其他逻辑学家所忽略的联系，并且做出那些伟大的发现。

有效推理

罗素所阐述的全部的数学都可以用一个形式逻辑系统来表示，以及其学生维特根斯坦所强调的在语言内言说语言的问题，影响了年轻的哥德尔的研究方向。维特根斯坦所关注的这些东西与希尔伯特的立场相当一致，他们都认为形式逻辑系统不仅可以在系统内部表达数学推理，而且还可以从系统外部用数学方法加以研究。

在希尔伯特在哥廷根所教授的逻辑课程中，他所采用的逻辑演绎的基本规则源自费雷格的《概念文字》以及怀特海与罗素合著的《数学原理》。在他1928年的逻辑教科书中，希尔伯特提出了在这些规则之间是否存在间隙的问题，也就是说，演绎推理应当是正确的，但规则本身却并不足以保证从前提能够得出结论。他相信并不存在这样的间隙，但他要求对规则本身是完备的进行证明。哥德尔选择了这个问题作博士论文。他很快就得到了希尔伯特所想要的结果，并且所运用的技巧是当时的逻辑学家们相当熟悉的。

演绎逻辑是从前提到结论的过程。当我们使用弗雷格－罗素－希尔伯特的符号逻辑时，每一个前提和结论皆由一个逻辑公式表示，也就是相当于一个符号串。这些符号中有些表示纯粹的逻辑概念，有些只是标点符号，还有一些是指相关的特定主题。下面是一个逻辑推理的理智：其中前两行是前提，第三行则是结论。

任何一个恋爱中的人都是快乐的。
威廉爱着苏珊
------------------------------
威廉是快乐的

运用第三章所介绍的逻辑符号系统，我们可以把它翻译成逻辑语言：

（∀x）（（∃y）L（x，y）⊃H（x））（*）
L（W，S）
------------------------------------
H（W）

在这个推理中所使用的逻辑符号是⊃，∀和∃，其含义见下表：

⊃如果……，那么……
∀所有
∃某个

字母x，y是变元,它们（就像代词一样）表示被考察人群中的任一个体，而其他符号L，W，H和S所具有的含义则与特定的主题相关。如下所示：

L＝恋爱关系
H＝快乐这一属性
W＝威廉
S＝苏珊

由此我们可以把这一推理表示成如下形式：

对于所有s，如果有一个y为x所爱，则x是快乐的。
威廉爱着苏珊
-----------------------------------------
威廉是快乐的。

说这个推理是有效的就意味着，无论我们所选择的这些个体所处的群体是什么，无论用字母L表示这些个体间的什么关系，无论用字母H表示这些个体所具有的什么属性，以及无论选择把哪些特定的个体指定给字母W和S，只要我们在推理时保证两个前提皆为真陈述，那么结论就必然为真。为了进一步阐明什么叫做一个推理是有效的，我们不妨用一种完全不同的主题对前面的符号推理做出解释：

肉食动物有着锋利的牙齿。
狼捕食羊。
----------------------
狼有着锋利的牙齿。

为了说明这个例子也可以用前面的符号推理(*)来表示，我们可以用变元x，y来表示哺乳动物的任意种类，并对其他字母作如下解释：

L＝物种之间的捕食关系
H＝有锋利牙齿这一属性
W＝狼
S＝羊

于是，这一符号推理就可以表示为：

对于所有的x，如果有一个y是被x捕食的，则x有锋利的牙齿。
狼捕食羊
-----------------------------------------------------
狼有锋利的牙齿。

以上解释了推理是有效的是什么含义。希尔伯特希望证明，任何一个有效的推理都可以用弗雷格－罗素－希尔伯特的规则从前提到结论逐步得到证明。换句话说，希尔伯特期望这样一种证明：如果一个推理具有如下属性，

无论对公式中的字母作何种解释，只要其前提是真陈述，则它的结论就是真的。

那么我们就可以用弗雷格－罗素－希尔伯特的规则从前提推演出结论。哥德尔在其博士论文中成功地给出了希尔伯特所期望的证明。

皮亚诺算术

PM系统过于复杂，我们在这里难以详述。故此，我们用较为简单的系统PA来显示在构造不可判定命题时所涉及的一些因素。PA可以用16个符号建立起来：

⊃ ¬ ∨ ∧ ∀ ∃ 1 ＋x X y z ( ) ` =

符号1，＋，X，＝是为了强调它们将仅仅被视为符号，同时也暗示它们原有的含义。字母x，y，z是表示自然数的变元，由于所需要的变元不只3个，所以我们可以把符号’加在那些字母上方，从而可以产生出任意多个变元。于是，y’和z’'’都是变元。由于这里的符号超过了10个，我们将使用一种编码表，其中每一个符号都被一对十进制数字所替代：

⊃  ¬  ∨  ∧  ∀  ∃  1  ＋ X  x  y  z  (  )  `  =
↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
10 11 12 13 14 15 21 22 23 31 32 33 41 42 43 44

自然数本身又被特定的字符串所表示，这些字符串被称为数字符号（numerals），如下所示：

数字符号	被表示的数	代码
1	1	21
(1+1)	2	4121222142
((1+1)+1)	3	4141212221422222142
(((1+1)+1)+1)	4	41414121222142222142222142
…	…	…

某些被称为句子的字符串可以被用来表示关于自然数的真假命题。于是，字符串

((1+1)X(1+1)=(((1+1)+1)+1))

的代码是

414121222142234121222142444141412122214222214222214242

它表示真命题2乘2等于4.而

((1+1)X(1+1) = ((1+1) + 1))

则表示假命题2乘2等于3.句子

(∀x)(¬(x=1)⊃(∃y)(x=(y+1)))

的代码是

4114314241114131442142104115324241314441322221424242

它表示除1以外的所有自然数都有前趋。

为了完成我们对PA的描述，有必要把某些特定的句子指定为公理和用于从公理推出可证句子的推理规则。从公理开始，到PA中的一个可证句子结束，其间的整个步骤被称为该句子的证明。虽然仔仔细细做完此事会把我们带得太远，但哦我们还是考虑一个简单得例子：

(∀x)¬(1=(x+1))

它表示这样一个命题：1不是任何自然数得直接后继。这个句子完全可以被选为一条公理。既然句子开头得符号∀表示某种属性对于所有自然数都适用，那么一条自然的推理规则就是，允许用一些数字符号来替换x（除去全程量词（∀x）之后）。这只是从一个普遍陈述推出它的一个特殊情形。下面是一个简单的例子：

(∀x)¬(1=(x+1))
--------------
¬(1=(1+1))

该结论是PA中的一个可证句子，它是通过用1替换变元x而得到的，它表示1和2是不等的这一事实。

除了用来表示命题的字符串外，还有其他一些被称为一元字符串，它们可以被用来定义自然数的集合。这些字符串将包含符号x，但不包含“量词”（∀x）或（∃x）（虽然它可以包含像y或x^n这样的关于其他变元的量词）。此外，一元字符串有一种至关重要的性质：假如所有x都被某个数字符号所代替，那么由此得到的字符串将是一个句子。一下是一元字符串的一个例子：

(∃y)(x=((1+1)Xy))

它的代码是

4115324241314441412122214223324242

假如x被数学符号（1+1）所替代，则我们就得到了真句子

(∃y)((1+1) = ((1+1)Xy))

假如x被数学符号1所代替，我们就得到了假句子

(∃y)(1 = ((1+1)Xy))

可以认为这个一元字符串为偶数集提供了一种定义。一下是一个更为复杂的一元字符串：

(∀y)(∀z)((x = (yXz))⊃((y=1)∨(y=x)))

它的代码是

41143242411433424241314441322333424210414132441421241324431424242

它定义了由1和全部质数所组成的集合。

给定一个一元字符串A和自然数n，我们将用符号［A：n］来表示用表示数字n的数字符号来替换A中的x所得到的句子.例如：

[(∃y)(x=((1+1)Xy)):2]

表示句子

(∃y)((1+1)=((1+1)Xy))

现在，我们就可以解释如何用哥德尔的方法生成PA中的一个句子U，该句子表示U本身在PA中是不可证的这一命题。使用被分配给一元字符串的码数，我们就可以依照它们的代码大小将其全部排列起来。在这种排序中，代码最小的一元字符串是（x＝1），即使连它的代码也是4131442142,超过了40亿。我们用A1来表示这个一元字符串，并想象所有的一元字符串都依照它们代码的大小排成一个序列：

A1, A2, A3, ...

因为这些都是一元字符串，所以对于任意的自然数n，m，字符串［An:m]就将是一个句子。这些句子中的某一些在PA中将是可证的，另一些则是不可证的。对于每一个n，我们都可以考虑由那些使得字符串［An:m］在PA中是不可证的m所组成的集合。

回忆一下我们对康托尔的对角线方法所作的讨论，我们看到这样一个集合可以被看成一个以n为标签的包裹。运用对角线方法，也就是说，把包裹中的一个元素当作标签，我们就可以构造出一个由那些使得［An：n］在PA中不可证的n所组成的集合K。利用PA中的可证明性可以在PA中进行定义这一事实，我们就可以找到一个一元字符串B，它在PA中定义了集合K。现在必然存在着某个数q使得B＝Aq，因为所有的一元字符串都包含在As的序列中。于是，对于每一个自然数n，句子［Aq：n］都表示命题

[An:n]在PA中是不可证的

特别地，当n被赋予q值时，我们可以看到，[Aq:q]表示命题

[Aq:q]在PA中是不可证的

因此，[Aq:q]是PA中的一个句子，它表示它本身在PA中不可证这一命题。

不可判定命题

在希尔伯特于1900年所列的著名问题中，第二个问题是对实数算数的一致性进行证明。当时，没有人知道这样一个证明会是什么样子，特别是不知道它如何才能摆脱循环论证，也就是说，如何在证明中避免用到证明所要捍卫的方法。

就像我们在前面的章节中所看到的那样，希尔伯特在20世纪20年代介绍了他的元数学纲领：一致性有待证明的公理将被包含在一个形式逻辑系统之内，而证明仅仅是有限数目的符号的一种排列而已。接着，证明这个系统的无矛盾性就要用到希尔伯特所说的有限性方法，该方法甚至比布劳威尔愿意接受的还要严格。当哥德尔完成了他的博士论文转而研究这些问题时，希尔伯特饿纲领的胜利似乎遥遥在望。

1928年，希尔伯特曾在波伦亚所举行的国际数学大会上谈到了这个系统，今天该系统被称为皮亚诺算术（PA），它包含了关于自然数1，2，3，……的基本理论。当哥德尔开始思考希尔伯特纲领时，希尔伯特的学生阿克曼和冯·诺伊曼二人都已经为PA的一个有限的子系统找到了这样的证明。

哥德尔本人决定去证明那些较之PA更强的系统的一致性。由于已经有了一些重要的关于相对一致性的证明，所有这是一个很自然的想法。哥德尔曾经希望用有限方法把这种可以包含实数算术的更强系统的一致性还原为PA的一致性。在很大程度上是在遵循希尔伯特的路线：希尔伯特曾经把欧几里得的一致性还原为实数算术的一致性，现在哥德尔希望把这种还原继续进行下去。如果哥德尔成功了，那么希尔伯特的追随者们对PA的一致性的额证明就将自动为实数算术的一致性提供证明，这样就满足了希尔伯特在1900年提出的第二个问题的要求。然而这是做不到的。哥德尔不仅在这项努力中失败了，他还证明了他是不可能成功的。

当哥德尔开始思考这些问题时，他重新思考了从外部而不是从内部考察一个形式逻辑系统的意思。罗素和怀特已经相当令人信服地表明，所有的普通数学都可以在这样一个系统内部发展出来。希尔伯特在他的元数学中试图运用严格受限的数学方法去从外部研究这样的系统。那么，为什么元数学自身不能在一个形式逻辑系统内部发展出来呢？从外部看，这些系统包含着符号串之间的关系。从内部看，这些系统能够表达关于不同数学对象（比如自然数）的命题。而且，用自然数来为符号串编码并不困难。啊哈！通过使用这样的代码，外部就可以被带到内部了。为了说明这些代码的用处，让我们再来看看“任何一个恋爱的人都是快乐的”这个前提是图和被符号化的：

(∀x)((∃y)L(x, y)⊃H(x))(*)

我们这里所有的只是10个符号的一个排列或串，这10个符号是：

, L H ⊃ ∀ ∃ x y ( )

我们可以采用一种简单的编码方案，其中每一个符号都被一个十进制的阿拉伯数字所替代，例如：

, L H ⊃ ∀ ∃ x y ( )
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 1 2 3 4 5 6 7 8 9

对于(*),用上面所示的数字代替那些符号，我们便得到了码数

846988579186079328699

请注意，不仅从符号串到数字的编码是容易的，反过来也同样容易。当然，如果符号超过了10个，我们就必须使用一种不同的编码方式，但这并不会带来什么困难。录入，倘若给每一个符号配上两个十进位的数字，那么我们就可以为多达100个的符号编码。从本质上讲同样的方法可以被用于任何形式逻辑系统。因此，各种不同的这种系统（所有这些系统从外部看都呈现为符号串）都可以用自然数来编码。

当一串0被放在一个十进位制表示的自然数之前时，该自然数并不会改变。例如：17=017=0017，以此类推。所以字符串Ly和,Ly和,,Ly都可以用17这个数来编码。然而，由于我们对以逗号开头的字符串没有兴趣，所以这种含糊不清就无须考虑。虽然它并不真的重要，但这里仍然可以提到，在哥德尔用来为字符串编码的实际技巧中，他并没有使用十进制的数字来表示数。根据一个自然数可以被唯一地分解为素因子的乘积这一事实，他把分配给符号的码数作为指数加在了相应的素数上。一个简单的例子将使我们看清楚其中的区别。字符串L（x，y）在我们的方案中将被编码为186079，在哥德尔的方案中，其码数将是2^13^85^67^011^713^9.

如何在那些极其相似的系统中用代码去发展出形式逻辑系统的元数学，这对哥德尔来说是不成问题的。哥德尔发现存在着这样的命题，它们从系统外部看是真命题，但却无法在系统内部获得证明。哥德尔认为：一种有意义的数学真理的观念不仅是存在的，而且其范围是超出了任何给定的形式系统的证明能力。从像PA那样的相对较弱的系统到怀特海和罗素的《数学原理》（PM）那样囊括了全部古典数学的系统，这个结论适用于相当广泛的形式逻辑系统。在哥德尔1931年发表的那篇卓越的论文——“论《数学原理》及有关系统的形式不可判定命题”中，他选择对形式系统PM给出了他的结果，从而说明即使强逻辑系统也不可能把全部数学真理包含在内。

在哥德尔的证明中，关键的一步在于他证明了：一个自然数作为PM中可证命题的一个代码，这一性质本身可以在PM中表现出来。根据这一事实，哥德尔可以在PM中构造出一些命题，在那些已经获知特殊编码的人看来，这些命题可以被看作表达了这样一个断言，即某些命题在PM中是不可证的。也就是说，他能够构造出这样一个命题A，该命题经译码后，可以断言某一命题B在PM中是不可证的。A表示这样一个命题，即某个符号串B表示一个在PM中不可证的命题。A和B通常是不同的命题。哥德尔问，它们是否有可是相同的呢？事实上，它们可以是相同的。哥德尔能够用他从格奥尔格·康托尔那里学到的一种数学技巧——对角线方法来证明这个结论。运用这种技巧，我们可以使被断言为不可证的命题和那个作出这一断言的命题是同一个命题。换句话说，哥德尔发现了如何获得这样一个非凡的命题，我们将称之为U，它有如下性质：

U说某个特殊的命题在PM中不可证。
那个特殊的命题就是U本身
因此，U说：“U在PM中不可证。”

在维也纳学派内部，人们普遍认为，对于一个类似于PM的系统中所表达的命题来说，命题为“真”的意义就是它根据该系统的规则是可证的。命题U的上述性质使得这一新年不再能够成立了。如果我们承认PM不会撒谎，也就是说在PM中证明的任何命题都是真的，那么我们就发现U是真的，但它在PM中不可证。如下所示：

为了避免使用像“真理”这样的在哲学上受到怀疑的概念，哥德尔诉诸于一种技术上的替代物，他称之为ω一致性，它是一种加强了的一致性。于是，他的定力的正确表述就是：如果PM是ω一致性的，那么就存在着一个命题U，U和¬U在PM中都是不可证的。几年以后，J.B.罗塞尔说明了如何用普通的一致性假设来替代ω一致性假设，从而作出了重要的改进。

与同时期的其他一些工作（特别是阿兰·图灵的工作，这将在下一章讨论）结合在一起，我们就可以以一种吸引人的形式把哥德尔的结论表述出来：无论在PM中加入什么样的附加公理，只要新的公理是通过一种算法来指定的，而且它们不会导致一个可证明的矛盾，那么系统中就必定存在着一个不可判定的命题U。

U是真的。假定它是假的，那么它所表述的内容就是假的，那么它就不是不可证的，而一定是可证的，既然是可证的，从而是真的。这就与开始的假定即U是假的相矛盾了。所以它一定是真的。
U在PM中是不可证的。既然它是真的，那么它所表述的内容必定为真，所以它在PM中不可证。
U的否定（记作¬U）在PM中不可证。因为U是真的，¬U必定为假，从而在PM中也不可证。

U具有这样的性质：它和它的否定在PM中都不可证。为了强调这种性质，我们把U称为不可判定命题。但这也不能强调得太过分，因为这种不可判定性只与系统内部得可证性相关。从我们外部得观点来看，U显然是真的。

现在这里出现了一个难题：我们知道U是真的，尽管它在PM中不可证。既然PM包含了所有得普通数学，那么U为真为什么在PM内部不可证？哥德尔认识到这一差一点就是可能的了，但这里存在着一个意想不到的障碍。在PM内部，我们可以证明：

假如PM是一致的，那么U

因此，正是PM是一致的这一额外假定，才使U在PM内部得不到证明。既然我们知道U在PM内部是不可证的，我们就必须得出结论说，PM的一致性在PM中不可证。然而，希尔伯特纲领的主要目的就在于：用被认为仅仅构成PM的一个非常有限的子集的有限性方法来证明像PM这样的系统的一致性。然而哥德尔却证明了，即使就PM的全部能力而言，它也不足以证明其自身的一致性。因此，至少如最初所设想的那样，希尔伯特纲领走到了尽头！

库尔特·哥德尔，计算机程序设计师

今天，我们知道有这样一种实际的物理装置，它的功能相当于一个通用的信息处理可编程计算机。但在1930年，实现这一切还要再等几十年。不过，那些熟悉现代程序设计语言的人只要看一下哥德尔在那年写的关于不可判定性的论文，就会看到一连串45个编了号的公式，它们看起来非常像一个计算机程序。这种相似绝非偶然。

哥德尔曾经证明，作为PM中的一个证明的代码，这种性质是可以在PM内部表示出来的。在证明的过程中，哥德尔不得不解决许多问题，这些问题与那些在设计程序语言和用这些语言编写程序时所面临的问题是相同的。在最基础的层次上，当代的计算机仅能通过由0和1所组成的一些短的字符串来执行简单的基本运算。那些所谓高级程序语言的设计师们面临着这样的任务，他们要向程序员们提供包含非常复杂的运算语句，而且还得使这些程序员们喜欢用它。要想让用这些语句所写出的程序被一台计算机执行，它们就必须被翻译成机器语言——翻译成执行它们所需的详细的基本运算清单。此项工作由特殊的翻译程序来完成，它被称为解释程序或编译程序。

在哥德尔对不可判定命题的存在性的证明中，其重点在于这一事实，即在PM中的可证明性可以在PM内部表现出来。哥德尔非常清楚自己要把这一革命性的结果提交给一群极富怀疑精神的读者，他希望能够消除任何疑虑。于是他就面临着这样一个问题，即把与PM的公理和推理规则相对应的字符串的代码的复杂运算分解开来，并把它们转化成用PM的符号语言所写成的表达式。为了解决这个问题，哥德尔实际上创造了一种特殊的语言，通过这种语言，所需的运算就可以被一步步地表示出来。每一步都是由一种对数的运算的定义组成的，经过哥德尔所使用的代码的转换，这种运算与PM表达式的一种平行的运算相对应。这些定义利用了在前面的步骤中已经定义过的项，由哥德尔的特殊语言表达出来。这样设计这种特殊的语言，就可以保证通过这样一种定义而被引入的运算能够在PM内部被恰当地表示出来。

那些主要被用于软件业的程序设计语言（比如C语言和FORTRAN语言）通常被说成是命令式的，这是因为可以认为用这些语言编写的一行行程序就是计算机所执行的命令。像C++这样的模件式语言也是命令式的。在那些所谓的功能程序设计语言（比如LISP语言）中，程序的字符行就是操作的定义。它们不是告诉计算机做什么，而是定义计算机将要提供什么。哥德尔的特殊语言非常像一种功能程序设计语言。

莱布尼茨曾经建议发明这样一种精确的人工语言，能够把人类的大多数思想还原为计算。弗雷格在其《概念文字》中说明了如何能够把握数学家们通常使用的逻辑推理。怀特海和罗素用一种人工逻辑语言成功地发展出了实际的数学。希尔伯特已经建议对这些语言进行元数学的研究。但在哥德尔以前，没有人能够说明如何才能把这些元数学的概念植入这些语言本身。

回到我们所建议的那种特殊编码方式的PA的例子，我们可以考察在把元数学概念翻译成数值运算的过程中所涉及的一些问题。我们可以提出的第一个问题是，给定某一字符串的码数，我们如何能够说出该字符串的长度？

现在，由于我们用两个阿拉伯数字来表示一个符号，所以答案很简单：字符串的长度等于代码中的数字数目的一半。对于一个码数r，我们将把相应的字符串的长度记为ζ（r）。给定两个字符串，我们总是可以通过把第二个字符串放到第一个字符串后面来构成一个新的字符串。

第二个问题是，如果给定的两个字符串分别是r和s，那么所组成的新的字符串的代码是什么？

答案可以通过公式r10^(2ζ(s))+s来计算。这是因为，r乘以10的2ζ（s）次幂可以表示在r后加了多少个0，这也就是s中的数字的个数。遵循哥德尔的方法，我们把它写成r*s。现在假定r和s是两个橘子的代码，如果我们在这两个句子之间插入符号⊃，并将结果用括号括起，那么这样得到的新句子的代码是什么？通过查译码表，我们知道答案是41*r*10*s*42。按照这种方法不断进行下去，即使是更复杂的元数学概念也可以被翻译成算数运算。

除了构造出一个不可判定命题U以外，哥德尔还希望证明该命题的陈述并不需要异乎寻常的数学概念。为此，哥德尔使用了基本数论中的一个定理——中国剩余定理。通过该定理，哥德尔说明了所有能够用他的特殊语言表示出来的运算如何能够用自然数算术的基本语言表示出来。

中国剩余定理显然可以追溯到公元11世纪时的中国。该定理可以用如下的练习加以说明：试找出一个数，它被6除余2，被11除余5.经过一番简单的试验之后，可知这个数是38.中国剩余定理保证我们总可以找到一个数，它被给定的数所除后余数是另一个给定的数，只要这些给定的除数两两之间没有公因数（当然不包括1）。例如，肯定存在着这样一个数，当它被67，17，25，91所除后，余数分别为13，7，10，11.但是假如我们把7换成14，那么这个结论就不能保证成立了（因为10和14有公因数2）。哥德尔把中国剩余定理用作一个编码装置：设计一组两两之间没有公因素的除数，然后让它们都除以同一个数，我们就可以定出一连串数字。由于“余数”在算数的基本语言中是容易定义的，所以它可以被用来表示在该种语言中包含自然熟序列的关系。

由此可知，不可判定命题U本身也可以用这种基本语言表示出来。这就意味着，U可以用这样一个词汇表写出来，组成这个词汇表的变量的值只能是任何自然数，算术运算＋和x，＝以及弗雷格逻辑中的基本运算¬，⊃，∧，∨，∃和∀。这里的非凡结论是，即使是局限于这个如此贫乏的词汇表，在PM内部不可判定的命题也可以被构造出来。

柯尼斯堡会议

柯尼斯堡会议的第三天有一个关于数学基础的圆桌会议。在会上，哥德尔向众人宣布了他那个惊人的发现。他用了相当长的时间试探性地讨论了从类似PM这样一个系统的一致性证明中可以得到什么。

他断言，即使已经知道这样一个系统是一致的，我们也完全有可能在该系统内部证明一个关于自然数的命题，该命题从系统的外部看是假的。因此，一个形式系统的一致性不足以保证系统内被证明的命题是正确的。

哥德尔进而宣称，如果假定像PM这样的系统的一致性，“我们甚至能够给出一些有着简单算术形式的命题的例子”，它们是真的，但在这样一个系统中却是不可证的。“因此”，他继续说道，“假如把这样一个命题的否定加入”PM，那么我们就可以得到一个一致的系统，但在该系统中有一个假命题是可证的。

逻辑和数学基础曾经是冯·诺伊曼的主要兴趣之一。他对逻辑的兴趣体现在了硬件上：通用数字计算机。

德国科学家和医生协会在柯尼斯堡举行的大会。在圆桌会议的第二天，大卫·希尔伯特就发表了开幕演说。正是在这里，希尔伯特明确地喊出了他的口号：“我们必须知道，我们将会知道”，他相信所有数学问题都必须得到回答，而且将会得到回答。这一口号后来刻在了他的墓碑上。哥德尔的不完备性定理表明，如果数学被局限在像PM那样的特殊的形式系统中，那么希尔伯特的信念就是徒劳的。对于任何一个特定的形式系统，都会有数学问题超越于它。

另一方面，从原则上讲，每一个这样的问题都会导向一个更强的系统，在该系统中能够得到这个问题的解答。我们可以想象出更强系统的等级体系，每一个较强的系统都可以解决较弱的系统所遗留的问题。虽然所有这些作为理论问题是无可争议的，但是它在何种程度上会成为数学实践，这个问题却是模糊不清的。

哥德尔为数学家们留下了这样一份遗产，即学会用这些更强的系统来解决棘手的问题。

希尔伯特的宣言

在希尔伯特1900年的问题列表中，排在首位的就是康托尔的连续统假设。它断言由实数组成的无穷集合只有两种大小。小的无穷集合是那些与自然数集同样大的集合，也就是说集合能够与集合{1, 2, 3, …}一一对应起来。大的无穷集合是那些能够与实数集一一对应起来的集合。连续统假设说，任何一个由实数组成的无穷集合必定是这两种类型当中的一种，因此绝不存在一个实数无穷集，它的大小介于这两者之间。（用康托尔无穷基数的语言来表达，就是任何一个由实数组成的无穷集的基数要么是א0，要么是C）希尔伯特在他的讲演中称，连续统假设“似乎非常真实”，但“尽管付出了最为艰辛的努力，还没有人能够成功地证明”它。

哥德尔开始相信，从能够作为数学基础的可能的形式系统来看，连续统假设是不可判定的。这样的系统不仅包括罗素和怀特海的PM，而且也包括建立在集合论公理的基础之上的系统。但他只能部分地证明他的信念：1937年，他证明了连续统假设在这些系统中是不可能被否证的。

更精确地说，哥德尔说明的是：如果像PA这样的系统或者那些建立在集合论公理上的系统是一致的，那么即使是把连续统假设作为一条新的公理加进去，它也仍然是一致的。因此，如果这些系统是一致的，那么在其内部连续统假设就不可能被否证。

哥德尔所发现的包含自然数的不可判定命题在所讨论的形式内部是不可判定的，但正如我们已经看到的那样，从外部来看，它们显然是真的。

数学家们通常处理的单个的实数，比如π和√2，可以在像PM这样的形式系统中被定义。但人们在康托尔的时代就已经很清楚，在这样的系统中，由所有能够被定义的数所组成的集合的基数是א0，而由全部实数所组成的集合的基数是C。我们知道后者更大。因此，大多数实数没有定义：它们是不可判定的。这是很奇怪的，你如何能够数出那些你不能定义的东西？谈论一个其中有许多数字不可判定的实数集，这有意义吗？也许连续统假设的不可判定性（哥德尔作此猜想，后来保罗·科恩给出了证明）告诉我们，它并没有一个清楚的意义，它本来就是含糊不清的。解决这个问题，就是顽强地面对实无限在数学中扮演着什么角色的问题。

杰出的逻辑学家所罗门·费弗尔曼称，连续统假设“本来就是含糊不清的”。在经历了最初的一些摇摆不定之后，哥德尔终于认为连续统假设绝不是含糊不清的，实际上，它是一个完全有意义的断言，并且很可能是错的。

1951年圣诞节期间在罗德岛的普罗维登斯所作的一个讲演。讲演的题目是“关于数学基础的一些基本定理及其哲学内涵”。在这个讲演中，哥德尔实际上是把希尔伯特关于任何一个数学问题的可解性的宣言放在了人的心灵本性的背景之下。哥德尔提出了这样一个问题，即人的心灵从本质上讲是否等同于一台计算机。直到现在，当人们谈到人工智能的前景时，仍要对这个问题进行激烈的争论。哥德尔只是说任何一个答案都是“与唯物论哲学截然对立的”。假如人的心灵的全部能力都能被一台有限的机械装置模仿出来，那么哥德尔本人的不完备性定理就可以被用来说明某个关于自然数的命题虽然是真的，却不能被人类证明，它是一个绝对不可判定的命题。

而另一方面，哥德尔推理说，如果人的心灵不能被还原为机械装置，而物理的大脑却可以被如此还原（他认为是显然的），那么就说明心灵超越了物理实在，这同样与唯物论不相容。与其说这则论证完全令人信服，不如说它是把理论逻辑，人类生理学，计算机的最终潜力以及基础哲学放在一起加以考虑。哥德尔再次展示了他那令人惊叹的独辟捷径思考问题的额能力。