人工智能时代：破解人机共存密码（套装共10册）

哥德尔证明不完备定理的四个步骤如下：

1.先考虑相对比较容易的数论的自洽性问题；

2.发现数论中的真理在数论中不能定义，这与数论取自哪个形式公设系统无关；

3.从真实性转向可证性，构造了一个不可判定论断；

4.发现完备性陈述自身也是不可判定的。

哥德尔那20页的著名证明极为紧凑，它有46个预备定义，另外还要证明5条预备定理，才开始正式的证明：构造一个既为真但是在所考虑的形式系统内部又不能证明的算术命题。虽然哥德尔的原始证明晦涩难懂，但他的策略却极为简单，一个离自相矛盾如此接近但并不是自相矛盾的证明，不是证明“这句话是错的”，而是去证明一个为真却不可被证明的算术命题，“这个陈述在这个形式系统中不可证明为真”。哥德尔的聪明之处在于，他把每个人都知道的两千多年前就被提出来的逻辑问题，巧妙地变成了一个算术问题。

“这个陈述在这个系统中不可证明为真”与“这句话是错的”，二者有着本质的区别。“这个陈述在这个系统中不可证明为真”（我们称之为哥德尔陈述，用符号G–S来代替），即“G–S在这个系统中不可证明为真”，G–S是一个有着确定真值的句子，它“真”，只不过它不可证明为真。而“这句话是错的”，没有确定的真值。这样G–S的否命题就是“G–S在这个系统中是可证明为真的”

如果G–S在这个系统中可证明为真，那么它的否命题“这个陈述在这个系统中可证”就是真的，因为它陈述的就是这件事。它是真的。那么G–S就是假的，因为当一个命题的否命题是真的，它本身就是假的。因此，我们要求一个系统是自洽的，因为不自洽的系统可以推出任何结论。G–S就是这样一个陈述，如果可证明它为真的证明存在，它就不得不既是真的又是假的，这与系统自洽的要求矛盾。为了维护系统的自洽性，我们只能放弃对G–S的真实性证明的存在这一要求，即，G–S不可证明为真，或者说，不存在对G–S的证明。这正是哥德尔的结论，如果我们要求系统是自洽的，在系统中就存在可以表述为真却不可以证明为真的命题。并且G–S有直接的算术意义，如果系统是自洽的，那么哥德尔的证明表明算术真理在算术的形式系统中不可证。对算术系统而言，它要不不自洽，要不不完备，总存在某些真理，无法被证明。

问题并没有停留在这里，哥德尔同样表明，即使把G–S当作公理加入系统，来试图通过“无须证明”挽救系统不完备的时候，这样会产生一个新的、扩展过的形式系统，那么在这个系统中一样可以构造出G–S的对应陈述，它为真，但不可证。结论是，在任何即使包含算术这样简单形式的系统中，如果系统是自洽的，没有矛盾，那么就一定存在不可证但为真的命题。一个有丰富内容的逻辑系统，不能既自洽又完备。

这个结论看起来很神奇，我们尝试着探索一下它的细节，这应该是本书最艰难的部分，但是值得我们以朝圣的心态，重新来一遍。

第一步：构建一个形式逻辑系统

哥德尔的大量陈述是基于罗素的《数学原理》，所以他先用了WFF，WFF指有效陈述，被用来指代符合形式逻辑的陈述，即从公设出发，通过逻辑推导得出来的陈述。为了简化逻辑推导，罗素和他之前的数学家们把逻辑推导简化成几个基本概念以及相应的符号。比如，“陈述P和陈述Q为真”，可以等同于“陈述P为假或陈述Q为假”

不对。

$$
\begin{array} { r } { \frac { \partial \ v { r } } { \partial \ v { r } } \frac { \partial \ v { r } } { \partial \ v { r } } \ v { x } : \quad \mathrm { ( \boldsymbol { x } ) } \quad \mathrm { ( \boldsymbol { x } ^ { \prime } ) } \quad \mathrm { [ \textbf { s } ^ { \prime } ( \boldsymbol { x } ) \ = \mathtt { s } \nabla \mathrm { \Omega ( \boldsymbol { x } ^ { \prime } ) } \ \ v { x } \to \nabla \mathrm { \Omega ( \boldsymbol { x } = \mathtt { x } ^ { \prime } ) } \mathrm { ] } } } \end{array}
$$

上面这个命题就是一个有效陈述WFF，它表明如果两个数有同样的后继，那么它们就是同一个数。它读作：任何x和任何x'，当x的后继等于x'的后继，那么x=x'。这里符号“（）”代表了“任何”这个概念。

第二步：哥德尔配数

哥德尔发明了一套算术方法，自动给形式系统中的每一个命题配一个独一无二的数。对一个有效陈述WFF，它的哥德尔配数表述为GN（WFF）。在今天看起来这一点都不难理解，我们可以给每一个汉字配一个数来代表这个汉字。1980年，为了使每一个汉字有一个全国统一的代码，我国颁布了第一个汉字编码的国家标准：GB2312–20。在这个标准中“清华”可以用“3969 2710”来代表。

罗素的形式系统中包含各种类型的对象：字母表中的符号、符号组成的有效陈述WFF以及WFF的特定序列（证明），这一切都建立在这个字母表的基本符号上，WFF是这些符号的序列，证明又是WFF的序列。哥德尔配数从给字母表中每一个基本符号指定一个数开始，根据规则给每一个WFF指定一个数字，继而可以给WFF所组成的证明序列一个数字。这样，一旦给每一个WFF都指定了一个数字，我们只需要分析命题的相应配数之间的算术关系就能分析命题之间的关系。反过来也一样。比如说，如果两个WFF的哥德尔配数正好以某种方式的算术关系相关，则一个WFF就是另外一个WFF的推论。换句话说，算术描述——阐述形式系统内可以表达的数之间的关系；元语句——阐述系统内WFF之间的逻辑关系，这两个不同类型的描述在哥德尔配数的帮助下是同构映射的。这里这些元语句是纯粹语法式的，因为它们纯粹是形式系统的语法，即推导规则。

哥德尔配数规则同时确保同一个哥德尔配数不会被指配给不同的对象，不会发生一个数字既指向某个WFF（命题），又同时指向一个WFF的序列（证明），任何一个WFF或WFF的序列都指向唯一的哥德尔数。给定一个哥德尔数，我们可以知道它代表着系统中的哪一个有效命题。它还保证了一个进一步的条件，由系统中WFF之间的逻辑关系翻译出来的算术命题同样是一个有效的命题。

举例来说，一个命题WFF2，它对应的哥德尔数为GN（WFF2），如果它可以由有效陈述WFF1——对应哥德尔数为GN（WFF1）——推导出来，那么GN（WFF1）就是GN（WFF2）的一个因子。这时我们可以用两种方式来表达这个证明：我们可以依据形式规则从WFF1开始推导出WFF2，我们也可以证明GN（WFF1）同某一个整数相乘可以得到GN（WFF2）。假设 $G N \ ( \ W F H 2 ) \ = \ 2 2 8 6 5 3 8 9$ ，而 $G N \ ( \ W F H ) \ = 3 1 1 9$ ，那么$G N \ ( \mathit { W F P 2 } ) \ = G N \ ( \mathit { W F P 1 } ) \ \times 7 3 3 1$ ，WFF2就是WFF1的一个推论，当然，这里7331也应该是一个有效命题的哥德尔数。

这样，哥德尔实现了元语法和算术的相互重叠。一旦有了这种逻辑含义和算术关系的重叠，命题的可证性这个元语法关系将成为一个算术关系，一组WFF将是某种算术关系的属性，只有可证明的WFF（命题）才能具有某种算术演算的属性，不可证的命题，即使它是有效命题也不能具有这种算术属性。

表5–1 基本逻辑符号的哥德尔配数（简化版）

首先考虑逻辑公式：

$$
\begin{array} { r l } { ( \exists \mathrm { x } ) } & { { } \left( \vphantom { A } _ { X } = S y \right) } \end{array}
$$

它的意义是：存在着一个数x，它是数y的直接后继。其中x、y是两个数值变量，用大于10的质数来表示；令x=11，y=13；再用表中相

应数字来替换逻辑公式中的其他符号。这样一来，逻辑公式（∃x）$\scriptstyle ( \mathrm { { } } _ { \mathrm { X } } = \mathrm { { S y } } )$ 经过编码，成为数的序列：

$$
[ 8 , \ 4 , \ 1 1 , \ 9 , \ 8 , \ 1 1 , \ 5 , \ 7 , \ 1 3 , \ 9 ]
$$

这个序列唯一地确定了逻辑公式 $\begin{array} { r l } { ( \exists \mathrm { x } ) } & { { } \left( \vphantom { A } _ { X } = S y \right) } \end{array}$ ，这些数称为哥德尔数。因为算术是研究数的性质的，所以我们希望用一种更明确的单个的数来表达这个公式。根据算术基本定理，我们知道，所有的自然数都可以唯一地分解成质数的乘积，即：

$$
N = 2 ^ { r _ { 1 } } \times 3 ^ { r _ { 2 } } \times 5 ^ { r _ { 3 } } \dots \dots \times p ^ { r _ { s } }
$$

于是，哥德尔取质数中的前10个质数（逻辑公式经过编码后由10个数表示），对每一个质数，求其在公式中所对应成分的哥德尔数次幂。这样，逻辑公式就定义为下面的数：

$$
( 3 x ) ( x = 5 y ) \Rightarrow 2 ^ { 8 } \times 3 ^ { 4 } \times 5 ^ { 1 1 } \times 7 ^ { 9 } \times 1 1 ^ { 8 } \times 1 3 ^ { 1 1 } \times 1 7 ^ { 5 } \times 1 9 ^ { 7 } \times 2 5 ^ { 1 3 } \times 2 9 ^ { 9 }
$$

所得的积就是逻辑公式 $\begin{array} { r l } { ( \exists \mathrm { x } ) } & { { } \left( \mathrm { x } { = } S y \right) } \end{array}$ 最终的哥德尔数，大概等于1. $4 5 6 7 \times 1 0 ^ { 8 6 }$ 。虽然这个数字非常大，但它总是存在的。

第三步：构造一个命题，它为真是因为它说它不可证明为真

Pr（x）是一个关于数的属性。形式系统中所有WFF都通过哥德尔配数被赋予了一个数，对于每个有效陈述 $p ,$ ，都有 $G V \left( p \right)$ 的自然数与之对应。对于这其中的可证明为定理的有效陈述，定义 $\scriptstyle n = G N \ ( { \boldsymbol { p } } )$ ，这时 $P r \ ( \boldsymbol { \eta } )$ 为真（即数字n对应的陈述P是provable，可证的）。这对应的就是在说，有这个自然数n，作为哥德尔配数，它对应于一个定理$p ,$ ，因为 $p$ 是可证明为真的。所以 $P r \left( \chi \right)$ 只有两个值，或为真，或为假。换句话说：

$P r \ [ G N \left( p \right) \ ]$ 当且仅当p可证。

这句话的意思是，当且仅当陈述 $p \mathrm { , }$ 是可证的，对应p陈述的哥德尔数具有Pr的性质，或者说这个哥德尔数的Pr值为真。

那么如果我们定义这样一个数的属性 $\widetilde { P r } _ { \mathrm { ~ \tiny ~ ( ~ x ~ ) ~ } }$ ，它是 $P r \left( \chi \right)$ 的反命题。它为真的时候，对应于命题x不是一个定理，换句话说，就是：

［GN（p）］当且仅当p不可证。

这句话的意思是，当且仅当p是个不可证的有效命题，对应p陈述的哥德尔数 $\widetilde { P r }$ 为真，即哥德尔的不可证性为真。哥德尔先证明了一条对角线引理，我们这里直接引用这条引理。对角线引理声称，对于任意单变量命题函数 $F \left( \mathrm { x } \right)$ ，都存在一个数n使得 $F _ { \mathrm { ~ } } ( \mathrm { n } )$ 的哥德尔配数正好就是n本身。既然对角线引理对于任意命题 $F \left( \mathrm { x } \right)$ 都成立，我们自然可以定义 ${ \cal F } \left( { \bf { \boldsymbol { x } } } \right) = \widetilde { P r } _ { \mathrm { ~ \tiny ~ \left( ~ x ~ \right) ~ } }$ 。这样，我们引入一个数 $^ { g , }$ ，它应用$_ { F \mathrm { ~ ( ~ x ~ ) ~ } } { \widetilde { P r } } _ { \mathrm { ~ ( ~ x ~ ) ~ } }$ 这个函数的对角线引理得出， ${ } _ { g = G N \ [ ] } \widetilde { P r }$ $( g ) ]$ 。这个公式宣称 $\scriptstyle { \cdot g } ^ { \prime }$ 是陈述 $g \bar { \gamma }$ 不具有 $\operatorname* { P r }$ 属性命题的哥德尔数。由于哥德尔配数，我们要记得 $\cdot \vec { g _ { \bar { \cdot } } }$ 其实也是一个很大的自然数。那么 $g _ { \lambda }$ 是哪个命题的哥德尔配数呢？这个命题是 $\widetilde { P r } _ { \textit { c } ) }$ ，我们用G来代表这个命题，它在说 $\bar { g \gamma }$ 不具有可证的属性，即 $g { = } G V \mathrm { ~ ( ~ g ~ ) ~ }$ ，考虑：

$\widetilde { P r } _ { \left[ G N \left( p \right) \right] }$ 当且仅当p不可证。

其实这里可以让p=G代入，即：

$\widetilde { P r } _ { \textit { c } ) }$ 当且仅当g不可证。

这句话的意思是，当且仅当G是个不可证的有效命题，对应G陈述的哥德尔数 $\ . g _ { \bar { \jmath } }$ 具有 $\widetilde { P r }$ 的性质，或者说这个哥德尔数 $\widetilde { P r } _ { \mathit { \Phi } ( g ) }$ 为真。也就是G为真当且仅当G不可证。

哥德尔展示的不仅在我们所讨论的算术形式系统中，而且也在所有包含了算术的形式系统中如何构造一个为真但又不可证的命题。因此，如果我们想扩展G为公设，构造一个新的形式系统，一个新的类似命题又可以从那个系统中构造出来。这样下去，直到任何数量的有限条公设被列入都不能最终解决这个问题。在任何包含了算术规则的形式系统中，只要系统是自洽的，总存在不可证但为真的命题。

这就是哥德尔第一不完备定理。

定理1 形式系统如果是自洽的则是不完备的。

换句话说，哥德尔第一不完备定理是说，如果算术的形式系统是自洽的，那么就存在命题G为真但不可证。

这句话分为两部分：一是条件，如果算术的形式系统是自洽的；二是结论，存在命题G为真但不可证。但如果算术形式的自洽性可以被证明，那么这句话本身就是结论的证明，所以“如果”这个条件是不成立的。因此算术的形式系统的自洽性在这个系统中是不可被证明的。

这就是哥德尔第二不完备定理。

定理2 形式系统不能证明自身的自洽性。

G是不可证明的事实，说明元数学描写G的命题是真，它对应着这命题G的含义为真。《数学原理》里一个表达真理的命题G，不能在《数学原理》里被证明，说明《数学原理》是不完备的。

是不是在《数学原理》里加上这个不可判定的命题作为公设，系统扩张后就可以让它完备起来？哥德尔说，这也不可能！即使加上新的公设，按照相同的逻辑，还可以证明有新的不可判定的命题，这让公设化的原始设想完全落空。该命题简单的推论是：数论里有无穷多个真理不能用数论里的公设和定理来证明。不断引进数论外的定理后，总是还有不能用形式逻辑证明的数论真理。

不幸的是，自洽是不可能在形式系统中得到证明的。系统自洽性的要求是系统里的一个命题和它的否定命题不能同时是定理，这是数学系统无矛盾性的要求。如果不是这样，在系统里就可以证明任何命题都成立。所以“自洽性”等价于要求“系统存在着一个命题，它是不可证明的”。

对角线证明法

我们换一种程序员更加熟悉的证明方式，这里不需要引入哥德尔的对角线引理，但用到了类似的证明思路。即使是我们认为严格的证明，也存在大量没有明确表述出来的推演规则，而我们通常认为这些是默认的真理（共识）而无须证明，它们这是显而易见的。为了明确，我们重新定义一下要用到的名词。

逻辑术语

定义：一个证明系统是自洽的，如果在这个系统中的陈述，S或者其反命题 $\widetilde { S }$ 可以被证明，但我们事实上并没有要求这个推导出来的陈

述为真。

定义：一个形式系统是完备的，如果为真的命题可以在这个系统中被证明，我们没有要求所有为真的命题或陈述都能被证明。

哥德尔不完备定理：不存在一个证明形式系统，同时满足自洽和完备。回顾一下我们前面提到的问题，怎样构成一个形式化证明？

一个形式化证明系统П包括以下3个要素：

1.有限的可用于证明的词汇组

2.有限的公设

3.有限的推演规则

“足够丰富”，指形式系统可以对任何x的值做出判定。

定义：如果一个命题系统里，f可以确定为真命题或假命题，那么这个系统就是我们说的足够丰富。

定义：我们使用 来代表这样一个方程集合——输入任意正整数，通过计算，输出结果是0或1。这样如果一个方程f是属于 的，任何一个正整数x输入到f（x），都会得到0或1。

定义：可计算。方程f是可计算的，也就是说如果可以用计算机语言（python、c语言等等）写出一个有限长的程序，在一个可以执行的计算设备上（比如个人计算机或者云中心）计算f。这样，给定任意的正整数x，程序总能在有限时间内运行完毕，给出结果f（x）。

定义： 是 中所有可计算方程f的集合。