Any mathematical system containing all the theorems of arithmetic is an incomplete system.

数学是建立在公理化的体系之上的。首先我们有一些基础的、无法更进一步解释的定义例如「点」、「线」、「相等」，之后有基础的公理如「过不在直线上的一点只能做一条该已知直线的平行线」，从这里我们又可以推出各种定理。这样由定义、公理、定理所组成的称为数学系统。最经典的数学系统即是欧几里得几何。

然而后来发现，公理并不一定是对的。例如上述的平行公理，完全可以否定这一公理从而得出非欧几里得几何。那么我们该如何保证公理为真？形式主义数学家希望将这种直觉的公理排除出数学，单纯地从形式的角度来理解数学。即公理只是一种符号记号，数学只是按照既定的规则从一些符号串得到另外一些符号串。

Whitehead 和 Russell 在 1910 年出版的《Principia Mathematica》里就试图使用符号系统来建立起整个算术理论，并通过这样的方式来解决数学系统中一致性的问题，即系统中不应出现自相矛盾的情况。例如最经典的 Russell’s Paradox

设 $S$ 为所有不包含自身元素为集合的集合，即 $S=\{X \mid X\notin X\}$。则 $S\in S$ 或 $S\notin S$，但由定义可以导出悖论。

在《数学原理》中，Whitehead 与 Russell 为了避免这一悖论，引入了「集合类型」。首先他们定义了一些基础的元素，称为「类型 0」；任何包含类型 0 元素的集合称为「类型 1」；任何包含类型 0 或 1 的集合称为「类型 2」，以此类推，只有满足这样的定义的可以被称为集合。这一方法的确避免了罗素悖论。实际上，这种方法是将对数学系统一致性的证明转移到了对一些基础逻辑系统一致性的证明。如果能够证明该逻辑系统的一致性，则任何从中导出的数学系统也是一致的，从而其中的命题都是可以被证明或是证伪的。

1931 年，哥德尔发表了论文"On Formally Undecidable Propositions of Principia Mathematica and Related Systems"阐述了哥德尔不完备定理。

任何包含了所有算术定理的数学系统都是不完备的，即系统中存在命题不能被证明也不能被证否。

下面给出哥德尔定理的简单证明。

首先对基本符号赋值哥德尔数

symbolmeaningGödel number
$0$zero1
$f$successor3
$\neg$not5
$\lor$or7
$\forall$for all9
$($left parenthesis11
$)$right parenthesis13

其它符号如 $\land$，$\exists$ 和 $=$ 都可以从上述的基本符号导出。有了符号的哥德尔数之后，公式的哥德尔数用质数的指数乘积表示，如要得出下列的哥德尔数

$$ fff0 $$

首先写出公式中每个符号的哥德尔数 $3,3,3,1$，则这个公式的哥德尔数为

$$ 2^33^35^37^1 $$

通过这种方法，对于每个命题我们有一一对应的哥德尔数。对于含 $k$ 个命题的命题集来说，首先得出每个命题的哥德尔数 $n_1, n_2, \dots, n_k$，之后将 $2^{n_1}3^{n_2}5^{n_3}\cdots p_k^{n_k}$ 设为该命题集的哥德尔数，其中 $p_k$ 是第 $k$ 个质数。

假设我们系统中所有的公式都只含一个变量 $x$，并将它们按照哥德尔数从小到大进行排列，令 $R(n)$ 表示其中的第 $n$ 个公式。用自然数 $n$ 的符号记法 $fff\cdots f0$ 替换 $R(n)$ 中的变量 $x$，我们将之记为

$$ \DeclareMathOperator{\PR}{PR} \DeclareMathOperator{\SUBST}{SUBST} \SUBST[n,R(n)] $$

如果这一新公式是可以被证明的，则记为

$$ \PR(\SUBST[n,R(n)]) $$

设 $Z$ 是包含所有使得 $\PR(\SUBST[n,R(n)])$ 为真的整数 $n$，则对于任意一个整数，它或属于或不属于集合 $Z$。考虑公式 $\neg(x\in Z)$，哥德尔证明了在这个系统中存在表示这一公式的基本符号串，则这一公式也有一个哥德尔数，假设其为第 $q$ 个公式，即 $R(q)$。

最后我们考虑 $\PR(\SUBST[q,R(q)])$，称为公式 $G$。下面可以看到，不论是 $G$ 还是 $\neg G$ 都是无法证明的。

**证明：**假设 $G$ 可以被证明，则根据假设，$q\in Z$，而 $R(q)$ 说明了 $\neg(q\in Z)$，矛盾。同理 $\neg G$ 也无法被证明。

由于 $G$ 与 $\neg G$ 必定有一个为真，但两者都无法被证明，这表明在我们的系统中至少存在一个命题为真，但无法被证明。

图灵将哥德尔不完备定理应用在计算机上，证明了不存在一般的算法能正确判断任意一段程序是否能够被正确运行。也就是著名的”停机问题。

用数学语言描述，其问题为：是否存在过程 $H(P,I)$ 对于任意程序 $P$ 和输入 $I$ 都能判断 $P$ 在 $I$ 的情况下是否停机。

**证明：**由于程序本身也是数据，因此可以将程序作为输入。构造一个新过程 $U(P)$ 如下

1
2
3
4
5
6
7
8

int H(Procedure,Input); // H 返回值为 1（死循环）或 0（停机）
int U(P){
    if (H(P,P) == 1){ // 如果 H 死循环
        return 0;     // 停机
    }else{            // 否則
        while(1){}    // 死循环
    }
}

现在考虑 $U(U)$，无论其是否停机，都存在矛盾，则证明 $H(P,I)$ 不可能存在。

参考

  1. Gödel’s incompleteness theorems
  2. Halting Problem
  3. Proof That Computers Can’t Do Everything