06 哥德尔不完全性定理

在上一节的末尾我们提到，当我们用一阶逻辑写出“ZFC公理”这组sentence $\Phi$时，能够找到一个一阶逻辑sentence“连续统假设”$\varphi$，我们既能够证明$\Phi \vdash \varphi$不成立，又可以证明$\Phi \vdash \neg\varphi$不成立。这使得我们必须放弃把“ZFC公理系统”作为观念上的“数学的根本理论”，因为采用这套理论我们就永远也无法知道连续统假设是真命题还是假命题。作为一组公理，ZFC不具有“否定完全性(negation completeness)”。于是，令人痴迷的事是：能否找到一套逻辑、一套推导规则，在这套逻辑下写出一组公理，它不仅是一致的，而且是否定完全的，并且表达能力足以撑起整座数学大厦？或者至少，我们希望我们能够证明这样的一套系统是存在的。如果这件事达成了，就证明了数学存在一个根基。进而，所有关于数学证明的工作本质上都是机械化的，因为它们只需要在形式系统上完成。然而1931年，哥德尔证明了这样一套系统是不可能存在的。任何形式系统只要具备一定的描述数学的能力，就一定会失去“否定完全性”。

计算机

我们的研究对象是形式证明：形式系统在一个公理集合上的推理能力问题。形式证明的符号、语法和推导规则都是明确定义的，因此是完全机械化的。在形式系统得到明确定义之后，对任何的$\Phi$和$\varphi$“$\Phi\vdash \varphi$是否成立”都是一个物理事实，而不依赖于任何数学观念。尽管一个形式证明是否可能在观念上是清楚的，但当我们把它作为讨论的对象来研究时，引入一套更简单高效的语言是必要的。我们需要建立一套数学语言来描述形式化证明——符号的排列。比如，我们可以引入图灵的计算机模型。我们想象存在若干条纸带和可以移动的读写头，然后以此为基础来描述形式化证明中符号的排列。然后，我们就可以用已知的数学规律来预测这一物理模型的行为，从而得出形如“某一证明是否是可能的”这样的结论。

寄存器机

我们将采用“寄存器机(register machine)”这一模型来描述形式化证明。可以证明，在计算能力上寄存器机和图灵机是等价的（在任意一个给定的字母表下）。

我们总是假设逻辑系统的字母表是有限大的。它有$n$个寄存器(registers)，每个寄存器上可以存放一个逻辑系统的字符串（有限个字母表中的符号连成的串）。在寄存器机启动前，第一个寄存器上会被写入一个字符串，这称为输入(input)；其余寄存器在启动前都是空的。寄存器机启动后，会依照$m$条从小到大按照自然数标有序号的指令执行操作。指令分为五种：

• 一，指定一个寄存器，在该寄存器内的字符串末尾添加一个字符；
• 二，指定一个寄存器，如果该寄存器内的字符串不为空就删去其末尾的字符，如果为空则不做任何操作；
• 三，指定一个寄存器以及$|A|+1$个正整数$L_0,\cdots,L_{|A|}$，其中$|A|$代表逻辑系统字母表的大小。如果该寄存器内的字符串以$a_i$结尾，则跳转至第$L_{a_i}$条指令开始执行；如果该寄存器内的字符串为空，则跳转至$L_0$；
• 四，打印第一个寄存器上的字符串；
• 五，停机；

所有被打印出来的字符串按照打印顺序的排列称为输出(output)。

有限条寄存器机上的指令集合被称为一个寄存器机程序（program, 简称程序），如果其最后一条指令为停机。

可枚举性与可判定性的定义

设字母表为$A$，全体由$A$种字符构成的有限字符串集合为$A^*$（包括空串，空串记为$\square$）。

对于一个字符串集合$W \subseteq A^*$，如果存在一个寄存器机程序$P$满足“当$P$的输入为$\square$时，输出包含且仅包含所有$W$中的字符串（以任何顺序，且允许重复），就称集合$W$是寄存器机可枚举的(register enumerable)，简称可枚举的。

对于一个字符串集合$W \subseteq A^*$，如果存在一个寄存器机程序$P$满足“对于任意字符串$\zeta\in A^*$，当$P$的输入为$\zeta$时，如果$\zeta\in W$则输出$\square$，如果$\zeta\not\in W$则输出一个非空串“，就称集合$W$是寄存器机可判定的(register decidable)，简称可判定的。

现在我们想用寄存器机程序来处理逻辑系统的形式证明。我们以一阶逻辑为例，并总是假设符号集是至多可数的（否则命题将是不可列的，因此自然是不可枚举的）。

我们首先注意到，一阶逻辑的字母表是可数无穷的，原因在于变量名符号$v_1,v_2,\cdots$和符号集中的符号$s_1,s_2,\cdots$。而寄存器机只能处理有限大小的字母表。为此我们要引入一个特殊处理。我们在字母表中引入一个特殊字符“$|$”，在寄存器机中总是用两个字符“$v|$”表示$v_1$，三个字符“$v||$”表示$v_2$，依次类推。同理，用“$s|$”表示$s_1$，“$s||$”表示$s_2$，依次类推。

我们可以写出一个寄存器机程序枚举“所有符合语法的一阶逻辑term”（假设符号集至多可数并且已经给定）。我们像描述C语言程序一样来描述这个算法。由于我们知道寄存器机的表达能力和任何图灵机等价，所以我们知道这个算法一定可以还原为一个寄存器机程序。首先，我们可以按照一阶逻辑意义下的长度定义（与寄存器机意义下的长度做区分）按照长度枚举$A^*$中的所有字符串，其中相同长度的字符串按照字典序枚举。对于每个字符串，按照一阶逻辑term的语法树做parsing（比如移入归约分析）就可以在有限步内判定该字符串是否符合语法，如果符合语法则打印，否则考虑下一个字符串。这样我们就证明了“所有符合语法的一阶逻辑term”这一集合是可枚举的。同理可以证明“所有符合语法的一阶逻辑formula”、“所有符合语法的一阶逻辑sentence”是可枚举的。

下面证明一阶逻辑的永真式是可枚举的。也即集合$\{\varphi \in L^S\mid \ \vdash \varphi\}$是可枚举的。注意，我们需要指定符号集$S$是至多可数的。这里重要的观察是，所有合法的相继式演算是可枚举的。这里需要一个巧妙的枚举技巧，类似于康托证明有理数可数时那样。我们从小到大枚举正整数$n$，对于每个$n$我们只枚举sequence个数（包括横线以上和横线以下的）不超过$n$的相继式演算，其中每一行的sequence $\varphi_1\varphi_2\cdots \varphi_k \ \varphi$都满足$k < n$，且每个$\varphi_i$以及$\varphi$都只取自字典序排名在前$n$以内的formula。对于每个枚举而得的，我们只需应用相继式演算的推导规则检查每一行的推导是否合法，这可以在有限步内正确完成。这样我们就可以枚举所有合法的相继式演算了。于是，我们只需判断每一步枚举的相继式演算的横线以下是否是一个单个formula的sequence（不包含任何前件），如果是则打印这个formula。这样我们就证明了集合$\{\varphi \in L^S\mid \ \vdash \varphi\}$是可枚举的。

进而，一阶逻辑的永真sentence集合$\{\varphi \in L^S_0\mid \ \vdash \varphi\}$也是可枚举的。只需在枚举$\{\varphi \in L^S\mid \ \vdash \varphi\}$的过程中，在打印时增加对$\varphi$是否是sentence的简单判断程序即可。

可枚举性与可判定性的关系

任何可判定的集合$W\subseteq A^*$一定是可枚举的。只需按字典序从小到大枚举$A^*$中所有字符串，对于每个字符串调用判定程序，如果判定为真则打印即可。

集合$W\subseteq A^*$是可判定的，当且仅当集合$W$与$A^*\setminus W$都是可枚举的。左推右：因为可判定的都是可枚举的，所以$W$是可枚举的；我们可以这样枚举$A^*\setminus W$，枚举$A^*$中所有字符串，对每个字符串调用判定程序，如果判定为假则打印。右推左：我们“同时”枚举$W$和$A^*\setminus W$（“同时”指的是，枚举$W$的程序打印一个，然后换成枚举$A^*\setminus W$的程序打印一个，交替进行）。对于任何$\zeta\in W$，它一定会在有限步内被$W$枚举到或被$A^*\setminus W$枚举到。如果被前者枚举到，返回真；如果被后者枚举到，返回假。证毕。

停机问题

寄存器机可以对任意有限的字母表$A$定义。哥德尔首次观察到，寄存器机程序本身也可以在一个有限字母表$B$中被编码，然后作为寄存器机的输入。

一个寄存器机程序是有限条指令，显然所有指令都可以只由字母表$A$中的符号和有限个其他符号（包括分隔符）来表示。所有这些符号构成一个有限字母表$B$，那么当我们按照字典序枚举$B^*$中的所有字符串，就会枚举到每个寄存器机程序。对于字母表$A$上的字典序为$n$的寄存器机程序$P_n$，我们可以用$A$中字典序最小的字符$a_0$构成的字符串$\underbrace{a_0a_0\cdots a_0}_{n\text{ times}}$来“表示”程序$P_n$。“表示”的意思是，存在一个字母表$A$上的寄存器机程序$P_0$，当把字符串$\underbrace{a_0a_0\cdots a_0}_{n\text{ times}}$作为输入时，它能把这个字符串解析为$P_n$代表的指令，然后依照该指令执行。对于字母表$A$上的任何寄存器机程序$P$，我们把它在$B^*$中的字典序$n$称为这个程序的哥德尔编码(Gödel number)，记为$w_P$。

对于任何一个字母表$A$，现在既然已经可以把每个$A$上的寄存器机程序映射到一个独特的$A$上的字符串$w_P$，那么“全体$A$上的寄存器机程序”就可以表示为$A^*$的一个子集$\Pi=\{w_P\mid P\text{ is a program over }A\}$。下面我们证明，这个集合是可以被$A$上的寄存器机程序判定的：这个程序的输入一个$w_P$，也即输入一个形如$\underbrace{a_0a_0\cdots a_0}_{n\text{ times}}$的字符串时，总是可以调用那个把$w_P$解析为$B^*$上字符串指令的程序（当然，必须把字母表$B^*$重新编码为$A^*$，但这并不困难，比如通过二进制就可以实现）。于是，只需解析这些指令是否符合指令的语法即可。这又是一个parsing工作，因此是可判定的。

下面我们要构造一个$\Pi$的子集，并证明这个子集是不可判定的。首先，我们注意到尽管我们要求每个程序的最后一条指令都是停机，但并非所有程序都会真的停机。例如，一个程序可能每次执行到倒数第二步的时候就跳回第一步，造成“死循环”，因此永远不会停机。我们构造一个集合$\Pi_{\text{halt}}$，它包含所有满足这样条件的程序$P$的哥德尔编码$w_P$：$P$在输入为自身的哥德尔编码$w_P$时会停机。也即，$\Pi_{\text{halt}}:=\{w_P\mid P\text{ is a program over }A \text{ and }P:w_P\to \text{halt}\}$。这个集合就是停机问题(the Halting Problem)。下面我们证明停机问题是不可判定的，也即不存在一个$A$上的程序能够判定$\Pi_{\text{halt}}$。证明：假如存在判定这个集合的程序$P_0$。因为$P_0$是一个判定程序，那么它在任何输入上都会停机。假设输入的$w_P \in \Pi_{\text{Halt}}$，那么$P_0$会输出空串（表示判定为真）并停机；假设输入的$w_P \not\in \Pi_{\text{Halt}}$，那么$P_0$会输出一个非空串并停机。现在我们修改这个$P_0$程序，使得它满足：设输入的$w_P \in \Pi_{\text{Halt}}$，那么$P_0$会做死循环，永不停机；假设输入的$w_P \not\in \Pi_{\text{Halt}}$，那么$P_0$会输出一个空串并停机。显然这个修改后的程序$P_0'$依然是$A$上的一个程序。现在考虑$P_0'$在被输入$w_{P_0'}$时会发生什么：假设输入的$w_{P_0'} \in \Pi_{\text{Halt}}$，那么$P_0$会做死循环。但是根据$w_{P_0'} \in \Pi_{\text{Halt}}$，$P_0'$在输入$w_{P_0'}$时应当停机，矛盾；假设输入的$w_{P_0'} \not\in \Pi_{\text{Halt}}$，那么$P_0$会输出一个空串并停机。但是根据$w_{P_0'} \in \Pi_{\text{Halt}}$，$P_0'$在输入$w_{P_0'}$时应当不停机，矛盾。由此可见，不存在判定这个集合$\Pi_{\text{halt}}$的程序$P_0$。

这种把自身代入自身推出矛盾的证明技巧在计算理论中很常见，称为对角线方法(diagonal argument)。想象把程序作为横轴按字典序排列，输入作为纵轴按照字典序排列，列出一张表格。在上面的证明里就是利用这张表格的对角线推出了矛盾。

为了方便后续使用，我们再证明一个类似的集合$\Pi_{\text{halt}}':=\{w_P\mid P\text{ is a program over }A \text{ and }P:\square\to \text{halt}\}$也是不可判定的：首先证明，对于任意一个程序$P$，我们可以对$P$做修改得到$P^+$：$P^+$会在$P$开始之前在第一个寄存器上做$|w_P|$次“末尾附加$a_0$”的操作。注意到，如果$P$在输入$w_P$时会停机，那么$P^+$在输入$\square$时也会停机；如果$P$在输入$w_P$时不会停机，那么$P^+$在输入$\square$时也不会停机。所以，对于任何一个程序$P$，我们都可以仅在其指令上做一些调整得到一个程序$P^+$，满足$P^+:\square \to \text{halt}$当且仅当$P:w_P\to \text{halt}$。现在假设存在判定集合$\Pi_{\text{halt}}'$的程序$P_1$，我们证明可以修改$P_1$得到一个程序$P_2$，使得$P_2$能够判定原本的$\Pi_{\text{halt}}$。$P_2$在接受一个输入$w$时，首先调用$\Pi$的判定程序，判定是否存在一个程序$P$满足$w=w_P$，如果不存在就输出$a_0$并停机（返回假）。如果$P$存在，那么可以构造一个程序$P^+$，满足$P^+:\square \to \text{halt}$当且仅当$P:w_P\to \text{halt}$。程序可以计算$P^+$的哥德尔编码$w_{P^+}$，然后把$w_{P^+}$输入$P_1$。如果$P_1$返回真，我们就返回真；如果$P_1$返回假，我们也返回假。我们验证$P_2$确实能判定$\Pi_{\text{halt}}$。设输入的$w_P \in \Pi_{\text{Halt}}$，那么$P$在输入$w_P$时停机，因此$P^+$在输入空时会停机，因此$w_{P^+}$输入$P_1$会返回真，可见$P_2$判定正确；假设输入的$w_P \not\in \Pi_{\text{Halt}}$，那么$P$在输入$w_P$时不停机，因此$P^+$在输入空时也不停机，因此$w_{P^+}$输入$P_1$会返回假，可见$P_2$判定正确。综上，我们得到了一个程序$P_2$能判定$\Pi_{\text{halt}}'$，但这是不可能的。因此不存在程序能判定$\Pi_{\text{halt}}'$。

一阶逻辑的不可判定性

一阶逻辑的永真sentence是不可判定的

我们证明过集合$\{\varphi \in L^S_0\mid \ \vdash \varphi\}$是可枚举的，其中$S$至多可数。下面我们要证明，当选取下面这个特殊的可数无穷符号集$S_\infty$时，集合$\{\varphi \in L^{S_\infty}_0\mid \ \vdash \varphi\}$是不可判定的：$S_\infty$中包含可数无穷个常量符号$c_1,c_2,\cdots$，对每个$n \geq 1$都包含可数无穷个$n$元关系符号$R^n_1,R^n_2,\cdots$和$n$元函数符号$f^n_1,f^n_2,\cdots$。这样我们就给出了一个可枚举却不可判定的例子。

Remark: 特别强调，并不是对任意符号集都有$\{\varphi \in L^S_0\mid \ \vdash \varphi\}$是不可判定的，我们可以证明当$S$中只包含一元关系符号时$\{\varphi \in L^S_0\mid \ \vdash \varphi\}$是可判定的。同时也强调，$S_\infty$并不是使得可判定性成立的最弱条件，可以证明符号集只需包含单个二元关系符号，就可以证明不可判定。事实上，从下面的证明中我们只用到了四个符号$\{R,<,f,c\}$，它们是一个多元关系符，一个二元关系符，一个一元函数符，一个常量符。事实上，就如我们将会看到的，只要符号集有足够的能力来刻画寄存器机的停机行为，就可以证明这个符号集上的永真sentence集合不可判定。

$\{\varphi \in L^S_0\mid \ \vdash \varphi\}$是不可判定的这件事告诉我们，永远不可能找到一个计算机算法在有限时间内给出一个$S_\infty$-sentence是否是永真的判断。人们总是可以肉眼看出形如$\forall x(x\equiv x \to x\equiv x)$的命题是永真的，但无论怎样设计程序，这个程序都一定无法正确判定某个永真的一阶逻辑命题。这深刻体现出了计算机能力的有限性。

Remark1: 必须区分“永真式”和“相继式演算的起点”。相继式演算的起点一定是永真式$t\equiv t$或前件包含后件的sequence $\cdots \varphi \cdots \ \varphi$，但并不是所有永真式都会出现在相继式演算的开头。形如$\forall x(x\equiv x \to x\equiv x)$的永真式要经过复杂的相继式演算才能得到。

Remark2: 在证明“可枚举性”或“可判定性”时，对于寄存器机的字母表没有特别的要求。我们可以在一个特殊的字母表（比如单个符号的字母表）上做证明不存在枚举程序或判定程序，并由此说明任意字母表上都不存在这样的程序。这是因为寄存器机的计算能力并不受字母表的影响。就像我们先前指出的那样，关于任何字母表的寄存器机的计算能力都是和图灵机等价的。

Remark3: 人脑的计算能力是否超越了图灵机？这是一个长期受到争论的问题。如果我们相信丘奇-图灵论题是真的，也即如果图灵机定义了所有物理上可能的计算，那么人脑本身也无法超越图灵机的计算能力。在这种意义下，计算机能力的有限性也将意味着人脑认知能力的有限性。人脑无法正确判定所有永真的一阶逻辑命题。

要证明$\{\varphi \in L^{S_\infty}_0\mid \ \vdash \varphi\}$是不可判定的，可以这样做：给定集合$A=\{a_0\}$，我们为$A$上的每个程序$P$都分配一个一阶逻辑sentence $\varphi_P$，使得$\vdash \varphi_P\iff P:\square\to \text{halt}$。假设我们能做到这一点，并且在给定$P$时有一个寄存器机程序能够在有限步内还原出$\varphi_P$。那么如果$\{\varphi \in L^{S_\infty}_0\mid \ \vdash \varphi\}$可以被$P_1$判定，就可以构造一个$P_2$来判定$\Pi_{\text{halt}}'$：输入$P$时，如果调用$P_1$得知$\vdash \varphi_P$，则输出空串并停机；否则，输出$a_0$并停机。这就推出了矛盾，因此$\{\varphi \in L^{S_\infty}_0\mid \ \vdash \varphi\}$是不可判定的。因此我们只需给出如何构造$\varphi_P$。

提出这种证明方法，是基于一个深刻的观察：寄存器机程序在输入为空串时的停机行为是可以被一阶逻辑刻画的。寄存器机的工作方式在数学上尤为简单。设寄存器机的寄存器个数为$n$，那么其“运行状态”只取决于这$n$个寄存机上储存的字符串，以及当前即将执行的指令序号——一个$n+1$元组。而指令的执行就是$n+1$元组到$n+1$元组的状态转移（一个函数）。我们把这个$n+1$元组称为程序运行的格局(configuration)。格局定义为一个$n+1$元组$(L,m_1,\cdots,m_n)$，其中$L$表示即将执行的指令序号，$m_i$是一个自然数，表示寄存器$i$上当前存储的字符串为$\underbrace{a_0a_0\cdots a_0}_{m\text{ times}}$（注意，我们假定了字母表$A$中只有一个字符$a_0$）。设程序$P$共有$k$条指令$\alpha_1,\cdots,\alpha_k$。因为我们考虑$P$在输入空串时的行为，所以初始格局为$(1,0,\cdots,0)$。对于任何一个格局$(L,m_1,\cdots,m_n)$：

• 如果执行指令一，其操作为在寄存器$i$末尾添加$a_0$，那么格局转移到$(L+1,m_1,\cdots,m_i+1,\cdots,m_n)$；
• 如果执行指令二，其操作为在寄存器$i$末尾移除$a_0$，，那么格局转移到$(L+1,m_1,\cdots,\max(m_i-1,0),\cdots,m_n)$；
• 如果执行指令三，它会指定一个寄存器$i$，其上的字符串要么为空要么以$a_0$结尾，指令会为这两种情况分别指定序号$L_0,L_1$。如果是前者，格局转移到$(L_0,m_1,\cdots,m_n)$；如果是后者，格局转移到$(L_1,m_1,\cdots,m_n)$；
• 如果执行指令四，那么格局转移到$(L+1,m_1,\cdots,m_n)$；（因为我们只关心程序的停机行为，因此不关心程序的输出）
• 如果执行指令时格局为$(k,m_1,\cdots,m_n)$，说明程序即将停机；

下面我们就来对于任意给定的程序$P$构造$\varphi_P$：从符号集$S_\infty$中取出四个符号，构成符号集$S:=\{R,<,f,c\}$。令$\chi_{1}:=(\forall x\forall y(x\equiv y \lor x<y\lor y<x))$ $\land (\forall x \neg x<x)$ $\land$ $(\forall x\forall y\forall z((x<y\land y<z)\to x<z))$，它将用于描述“$<$是序关系”；$\chi_2:=(\forall x(c<x\lor c\equiv x))\land(\forall x(x<fx))\land(\forall x\forall y(x<y)\to (fx<y\lor fx\equiv y))$，它将用于描述“$c$是序关系上的最小元，$f$是序关系上的后继函数”。我们将用符号$\overline{0},\overline{1},\overline{2}\cdots$作为term $c,fc,ffc,\cdots$的缩写。我们将用“$RLm_1\cdots m_n$”表示格局$(L,m_1,\cdots,m_n)$是可达的(reachable)。初始格局$(1,0,\cdots,0)$是可达的。所以有$\psi_0:=R\overline{1}\overline{0}\cdots \overline{0}$。对于各个指令$\alpha \in \{\alpha_1,\cdots,\alpha_k\}$，我们把格局的转移用公式写出来：

• 若$\alpha$为指令一，设它的序号为$L$，对寄存器$i$操作，那么令$\psi_\alpha:=\forall y_1 \cdots \forall y_n(R\overline{L}y_1\cdots y_n\to R((f\overline{L})y_1\cdots f(y_i)\cdots y_n))$
• 若$\alpha$为指令二，设它的序号为$L$，对寄存器$i$操作，那么令$\psi_\alpha:=\forall y_1 \cdots \forall y_n(R\overline{L}y_1\cdots y_n\to((y_i\equiv \overline{0}\land R(f\overline{L})y_1\cdots y_n)\lor$ $(\neg y_i\equiv \overline{0}\land \exists u \ fu\equiv y_i\land (R(f\overline{L})y_1\cdots y_{i-1}uy_{i+1}\cdots y_n))))$
• 若$\alpha$为指令三，它指定一个寄存器$i$和序号$L_0,L_1$，那么令$\psi_\alpha:=\forall y_1 \cdots \forall y_n(R\overline{L}y_1\cdots y_n\to((y_i\equiv \overline{0}\land R\overline{L_0}y_1\cdots y_n)\lor$ $(\neg y_i\equiv \overline{0}\land R\overline{L_1}y_1\cdots y_n)))$
• 若$\alpha$为指令四，设它的序号为$L$，那么令$\psi_\alpha:=\forall y_1 \cdots \forall y_n(R\overline{L}y_1\cdots y_n\to R((f\overline{L})y_1\cdots y_n))$

最终，令$\varphi_P:=(\chi_1\land \chi_2\land \psi_0\land \psi_{\alpha_1}\land \cdots \land \psi_{\alpha_k})\to \exists y_1\cdots\exists y_n R\overline{k}y_1\cdots y_n$。我们证明$\varphi_P$满足$\vdash \varphi_P\iff P:\square\to \text{halt}$。左推右：我们可以构造一个$S$上的structure $\mathfrak{A}_P$，其中$A_P=\mathbb{N},<^\mathfrak{A}=<^\mathbb{N},f^\mathfrak{A}(n)=n+^\mathbb{N}1^\mathbb{N},c^\mathfrak{A}=0^\mathbb{N}$，$R^\mathfrak{A}(L,m_1,\cdots,m_n)$成立当且仅当程序状态$(L,m_1,\cdots,m_n)$是可达的。因为$\vdash \varphi_P$，所以任意structure都可满足$\varphi_P$，因此$\mathfrak{A}_P(\varphi_P)=true$，因此程序$P$在输入为空时能到达停机状态；右推左：假设$P$在输入为空时会停机，我们要证明对于任意$S$上的$\mathfrak{A}$都有$\mathfrak{A}(\varphi_P)=true$。记$\psi_P:=\chi_1\land \chi_2\land \psi_0\land \psi_{\alpha_1}\land \cdots \land \psi_{\alpha_k}$，即证对任意$\mathfrak{A}$，只要$\mathfrak{A}(\psi_P)=true$就有$\mathfrak{A}(\exists y_1\cdots\exists y_n R\overline{k}y_1\cdots y_n)=true$。因为$\mathfrak{A}(\psi_0)=true$，所以$(1,0,\cdots,0)\in R^\mathfrak{A}$。因为$P$会停机，所以寄存器机一定会到达程序状态$(k,m_1,\cdots,m_n)$。根据$\psi_P$的构造，也一定有$(k,m_1,\cdots,m_n)\in R^\mathfrak{A}$。因此$\mathfrak{A}(\exists y_1\cdots\exists y_n R\overline{k}y_1\cdots y_n)=true$；证毕。

这样我们就证明了$\{\varphi \in L^{S_\infty}_0\mid \ \vdash \varphi\}$是不可判定的。

一阶逻辑的可满足sentence是不可枚举的

“集合$\{\varphi \in L_0^{S_\infty}\mid\ \vdash \varphi\}$是不可判定的”这一结论还意味着“集合$\{\varphi \in L_0^{S_\infty}\mid\ \text{Sat }\varphi\}$是不可枚举的”。这再次体现出计算机能力的有限性。证明：因为集合$\{\varphi \in L_0^{S_\infty}\mid\ \vdash \varphi\}$是可枚举的，设枚举它的程序是$P_1$。假设$\{\varphi \in L_0^{S_\infty}\mid\ \text{Sat }\varphi\}$是可枚举的，设枚举它的程序是$P_2$。此时再次使用“同时枚举”的证明技巧，可以构造一个程序$P$来判定$\{\varphi \in L_0^{S_\infty}\mid\ \vdash \varphi\}$。输入任意公式$\varphi$，程序$P$轮流调用$P_1,P_2$枚举公式，如果$P_1$枚举到$\varphi$就返回真并停机，如果$P_2$枚举到$\neg\varphi$就返回假并停机。注意到，如果$\varphi$是永真的，那么它一定会在有限时间内被$P_1$枚举到$\varphi$，此时$P$正确判定了$\varphi$；假设$\varphi$不是永真的，那么意味着存在$\mathfrak{I}$使得$\mathfrak{I}(\varphi)=false$，也即存在$\mathfrak{I}$使得$\mathfrak{I}(\neg \varphi)=true$，这说明$\neg \varphi$是可满足的，因此有限时间内$\neg\varphi$一定会被$P_2$枚举到并返回假。可见，程序$P$一定在有限时间内停机并且正确做出判定。但是这是不可能的。因此不存在程序能够枚举$\{\varphi \in L_0^{S_\infty}\mid\ \text{Sat }\varphi\}$。

可枚举的一定是可判定的。既然可满足的一阶逻辑sentence是不可枚举的，自然也是不可判定的。因此我们也证明了不存在一个寄存器机程序来判定一个一阶逻辑sentence是否是可满足的。

必须区分，基于寄存器机定义的“可枚举”并不等价于基于集合的基数定义的“可数”，尽管这二者在名字听上去很像。$\{\varphi \in L_0^{S_\infty}\mid\ \text{Sat }\varphi\}$是一个可数的集合，因为它是$L_0^{S_\infty}$的子集。但是$\{\varphi \in L_0^{S_\infty}\mid\ \text{Sat }\varphi\}$是不可枚举的。这意味着，即便寄存器机可以列出所有符合语法的一阶逻辑sentence，但不存在一个程序能够从中筛选出所有可满足的sentence。作为一个可数集的子集，这个“子集关系”本身是程序无法刻画的。

自然数算术的一阶逻辑理论的不可判定性

接下来我们证明一阶逻辑的sentence集合$\text{Th}(\mathfrak{N}):=\{\varphi \in L_0^S\mid \mathfrak{N}(\varphi)=true\}$是不可判定的，其中$\mathfrak{N}$就是标准自然数算术模型$(\mathbb{N},+^\mathbb{N},\cdot^\mathbb{N},0^\mathbb{N},1^\mathbb{N})$。（符号集为$S_{\text{ar}}:=\{+,\cdot,0,1\}$）

我们采用和证明“一阶逻辑的永真sentence不可判定”相同的证明技巧：用自然数算术公式刻画寄存器机程序的停机行为。给定集合$A=\{a_0\}$，我们为$A$上的每个程序$P$都分配一个$S_{\text{ar}}$-sentence $\varphi_P$，使得$\mathfrak{N}( \varphi_P)=true\iff P:\square\to \text{halt}$。假设我们能做到这一点，并且在给定$P$时有一个寄存器机程序能够在有限步内还原出$\varphi_P$。那么如果$\text{Th}(\mathfrak{N})$可以被$P_1$判定，就可以构造一个$P_2$来判定$\Pi_{\text{halt}}'$：输入$P$时，如果调用$P_1$得知$\mathfrak{N}(\varphi_p)=true$，则输出空串并停机；否则，输出$a_0$并停机。这就推出了矛盾，因此$\text{Th}(\mathfrak{N})$是不可判定的。因此我们只需给出如何构造$\varphi_P$。

同样是想要构造刻画程序的停机行为的一阶逻辑公式，不同之处在于符号集由$S_\infty$被限定为了$S_\text{ar}$。这意味着我们不再可以使用一个$n+1$元关系符号来描述寄存器机的格局。为此，我们需要一些巧妙的编码技巧。

给定程序$P=\{\alpha_1,\cdots,\alpha_k\}$，在原来的证明中，我们用公式$Rzy_1\cdots y_n$来表达格局$(\gamma(z),\gamma(y_1),\cdots,\gamma(y_n))$是可达的（$\gamma$是具体对这个公式做出解释时为这些变量的赋值）。现在没有$n+1$元关系符号可供使用，那么我们必须构造一个公式来表达相似的含义。假如对于任意的初始格局$(1,l_1,\cdots,l_n)$和格局$(L,m_1,\cdots,m_n)$，我们都能用$S_\text{ar}$构造一个公式$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}$（下标表示自由变量），满足$\mathfrak{I}(\chi_{l_1,\cdots,l_n,L,m_1,\cdots,m_n})=true$（其中$\mathfrak{I}=(\mathfrak{N},\gamma)$，且$\gamma(x_i)=l_i$，$\gamma(z)=L$，$\gamma(y_i)=m_i$）当且仅当$P$从格局$(1,l_1,\cdots,l_n)$出发能有限步到达$(L,m_1,\cdots,m_n)$，那么我们就可以令$\varphi_P:=\exists v_1\cdots \exists v_n \chi_{1,0,\cdots,0,\overline{k},v_1,\cdots,v_n}$（其中$\overline{k}$是$\underbrace{1+\cdots+1}_{k\text{ times}}$的缩写），此时就有$\mathfrak{N}( \varphi_P)=true\iff$ $P:\square\to \text{halt}$。因此我们只需给出$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}$的构造方式。

我们意识到，在脱离了符号$R$以后，要描述可达性必须深入到寄存器机程序的具体执行过程：公式$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}$的组成结构必须反映出程序$P$的各个指令是如何引起各个寄存器内存储的值的变化的。具体而言，$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}$应当描述：存在一个有限长的格局序列$C_1=(1,x_1,\cdots,x_n),\cdots,$ $C_s=(z,y_1,\cdots,y_n)$，满足对于任意$1\leq i<s$，格局$C_i$在经过程序$P$的对应指令的执行后恰好会称为$C_{i+1}$。但是，把这件事用一阶逻辑语言写出来是困难的。首先，我们必须写量词$\exists s$，然后再用$\exists$写出至少$s$个量词。但我们必须事先确定一个一阶逻辑公式中要写多少个量词！在这里，我们无法通过写“足够多个”量词来解决问题。假设我们决定在公式$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}$中写$M$个量词，那么公式就一定无法描述$s=M+1$时的情况。

哥德尔提出了一个巧妙的方法来解决这个问题。他发现，每当我们想要写出任意多个$\exists a_i$时，我们可以把这串$a_i$看作一个关于$i$的函数。而要在自然数算术上完成这件事，只需引入两个辅助的变量$t,p$。

首先证明，存在一个$\mathbb{N}^3\to \mathbb{N}$的函数$\beta$，满足：对于任意$r \in \mathbb{N}$以及序列$(a_0,\cdots,a_r)$，存在$t,p \in \mathbb{N}$使得$\forall i \leq r$，$\beta(t,p,i)=a_i$。证明：给定$r$和$(a_0,\cdots,a_r)$时，因为质数可以大于任何有限值，可以取一个质数$p$使得$p>\max\{a_0,\cdots,a_r,r+1\}$。令$t$等于那个在$p$进制下从低位到高位表示为$1a_02a_1\cdots (r+1)a_r$的整数，也即令$t=1\cdot p^0+a_1\cdot p^1+2\cdot p^2+a_2\cdot p^3+\cdots+(r+1)\cdot p^{2r}+a_r\cdot p^{2r+1}$。于是，对于任意$a\in \mathbb{N}$（其中$a<p$），$a=a_i$当且仅当存在自然数$b_0,b_1,b_2$使得 ①$b_0<b_1$；②$b_1=p^{2m}$，其中$m\in \mathbb{N}$；③$t=b_0+b_1(i+1+ap+b_2 p^2)$。左推右：令$b_0=1\cdot p^0+a_1\cdot p^1+2\cdot p^2+a_2\cdot p^3+\cdots+i\cdot p^{2i-2}+a_{i-1}\cdot p^{2i-1}$，$b_1=p^{2i}$，$b_2=(i+2)+a_{i+1}\cdot p+\cdots+a_r\cdot p^{2(r-i)-1}$，代入即有$t=b_0+b_1(i+1+ap+b_2 p^2)$；右推左：假设右边的三条性质成立，那么代入可知$t=b_0+(i+1)p^{2m}+ap^{2m+1}+b_2p^{2m+2}$。现在，由于$b_0<b_1=p^{2m}$，$a<p$，$i+1<p$，那么由$t$的$p$进制表示的唯一性可知$p^{2m+1}$的系数应该相等，因此$a=a_{m}$。又由$p^{2m}$的系数应该相等可知$i+1=m+1$。由此可得$a=a_i$。证毕。这个函数$\beta$被称为哥德尔$\beta$-函数(Gödel $\beta$-function)。

下面证明，哥德尔$\beta$-函数是能用$S_{\text{ar}}$下的一阶逻辑公式表示的。存在一个公式$\varphi^\beta_{v_0,v_1,v_2,v_3}$满足：$\forall t,p,i,a\in \mathbb{N}$，令$\gamma(v_0)=t,\gamma(v_1)=p,\gamma(v_2)=i,\gamma(v_3)=a$，$\mathfrak{I}=(\mathfrak{N},\gamma)$，有$\mathfrak{I}(\varphi^\beta_{v_0,v_1,v_2,v_3})=true\iff$ $\beta(t,p,i)=a$。证明：给定$t,p,i$时，由上一段的证明我们知道，$\beta(t,p,i)=a$当且仅当“$a<p$，且存在自然数$b_0,b_1,b_2$使得①$b_0<b_1$；②$b_1=p^{2m}$，其中$m\in \mathbb{N}$；③$t=b_0+b_1(i+1+ap+b_2 p^2)$”。这可以推出，$\beta(t,p,i)$是满足“存在自然数$b_0,b_1,b_2$使得①$b_0<b_1$；②$b_1=p^{2m}$，其中$m\in \mathbb{N}$；③$t=b_0+b_1(i+1+ap+b_2 p^2)$；④$a<p$”的最小整数$a$。为了避免用一阶逻辑表示指数$p^{2m}$，我们把条件②等价替换为“存在$x$使得$b_1=x^2$，且对于任意$d$，$d\mid b_1$可以推出$d=1$或$p\mid d$”。还需要考虑这四个条件都不满足的情况（对应的，如果$t,p$对应的$\beta$函数能支持$i$以上的个数，则不会出现这种情况），此时我们可以直接令$\beta(t,p,i)$为$0$。由此我们可以构造（其中$x<y$是$\exists z(\neg z\equiv 0 \land x+z\equiv y)$的缩写）

$\psi_{t,p,i,a}:=\exists b_0\exists b_1\exists b_2(b_0<b_1)\land (\exists x(b_1\equiv x\cdot x\land \forall d(\exists u(b_1=d\cdot u))\to$ $(d=1\lor (\exists v(d = p\cdot v)))))$ $\land(t\equiv b_0+b_1\cdot(i+1+a\cdot p+b_2\cdot p \cdot p)\land (a<p)$

于是可以写出

$\varphi^\beta_{t,p,i,a}:=(\psi_{t,p,i,a}\land \forall a_0(\psi_{t,p,i,a_0}\to(a\equiv a_0 \lor a<a_0)))\lor(a\equiv 0 \land \neg\psi_{t,p,i,a})$

这就是满足要求的$\beta$-函数的构造。

于是，我们就可以利用$\varphi^\beta$构造$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}$了。首先构造描述程序$P$的单步状态转移的公式。以指令一为例。设$P$的第$i$条指令$\alpha_i$为指令一，它指定寄存器$w$，那么令$\lambda^i_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}:=(u\equiv \overline{i}\to(u'\equiv u+1\land u'_1\equiv u_1\land \cdots\land u_w'\equiv u_w+1$ $\land \cdots \land u'_n\equiv u_n))$。$\lambda^i_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}$将用于表示“格局$(u,u_1,\cdots,u_n)$能通过指令$\alpha_i$转移到格局$(u',u_1',\cdots,u_n')$”（$u$是变量，在$\chi$中将会由量词引入）。当然，如果$\alpha_i$是指令二，那么$\lambda^i_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}$必须按照指令二的转移方式来写。依次类推，我们根据$P$的指令依次写出刻画它们的$k$条公式$\lambda^1_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n},\cdots,$ $\lambda^k_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}$。现在，当我们想要表达“格局$(u,u_1,\cdots,u_n)$能单步到达格局$(u',u_1',\cdots,u_n')$”，只需写出$\lambda_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}:=\lambda^1_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}$ $\land \cdots \land$ $\lambda^k_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}$。有了$\lambda$，就可以直接写出$\chi$：

$\chi_{x_1,\cdots,x_n,z,y_1,\cdots,y_n}:=\exists s\exists t\exists p(\varphi^\beta_{t,p,0,1}\land \varphi^\beta_{t,p,1,x_1}\land \cdots \land \varphi^\beta_{t,p,\overline{n},x_n}$ $\land \varphi^\beta_{t,p,s\cdot(\overline{n}+1),z}$ $\land\varphi^\beta_{t,p,s\cdot(\overline{n}+1)+1,y_1}\land \cdots \land \varphi^\beta_{t,p,s\cdot(\overline{n}+1)+\overline{n},y_n}\land \forall i((i<s)\to \forall u\forall u_1 \cdots \forall u_n\forall u'\forall u_1'\cdot \forall u'_n($ $\varphi^\beta_{t,p,i\cdot(\overline{n}+1),u}\land \varphi^\beta_{t,p,i\cdot(\overline{n}+1)+1,u_1}\land \cdots \land \varphi^\beta_{t,p,i\cdot(\overline{n}+1)+\overline{n},u_n}\land \varphi^\beta_{t,p,(i+1)\cdot(\overline{n}+1),u'}\land \varphi^\beta_{t,p,(i+1)\cdot(\overline{n}+1)+1,u'_1}$ $\land \cdots \land \varphi^\beta_{t,p,(i+1)\cdot(\overline{n}+1)+\overline{n},u'_n})\to\lambda_{u,u_1,\cdots,u_n,u',u'_1,\cdots,u'_n}))$

这样我们就证明了$\text{Th}(\mathfrak{N})$是不可判定的。

公理化与完全性

以自然数算术理论为例。人脑会如何判定一个一阶逻辑命题$\varphi$是否属于自然数算术理论$\text{Th}(\mathfrak{N})$？在现代，人类用公理化的方法来完成判定。指定一组一阶逻辑公式$\Phi \subseteq \text{Th}(\mathfrak{N})$，称这组公式就是自然数算术的“公理”。对于每个$\varphi$，只需利用形式推导规则，找到一个证明$\Phi \vdash \varphi$，那么就能说明$\varphi$是正确的自然数算术定理。公理化把数学变得机械化了：计算机也可以完成上面的过程。我们已经看到，全体正确的形式证明是寄存器机可枚举的。于是在已知公理$\Phi$时，只需启动证明的枚举程序$P$，对于每个证明检查最下方的sequence的后件是否为$\varphi$，且是否所有前件都落在$\Phi$中。假设$\Phi$是有限集，那么程序$P$已经能正确判定由一组公理$\Phi$的所有结论。而如果$\Phi$是无穷集，那么我们还必须保证“检查前件是否落在$\Phi$中”这一步能在有限步内完成，这恰好等价于要求公理$\Phi$本身要是一个可判定的集合。总结来看，只要我们能找到一组能够包含一切自然数算术真理的公理集合，且这个公理集合是可判定的，那么我们就可以让机器来帮我寻找$\varphi$的证明。如果确实存在一个$\Phi\vdash \varphi$的证明，那么程序$P$一定会在有限步内停机并输出这个证明。但是否有可能，我们所找到的$\Phi$既没有$\Phi \vdash \varphi$也没有$\Phi\vdash \neg \varphi$？如果$\Phi$满足对于所有的sentence $\varphi$，要么$\Phi \vdash \varphi$要么$\Phi\vdash \neg\varphi$，并且满足以上所有要求，那么我们确实找到了一个程序来判定$\text{Th}(\mathfrak{N})$。但我们已经证明了，$\text{Th}(\mathfrak{N})$是不可判定的，因此我们永远不可能找到满足所有这些要求的公理集合。

为了讨论方便，我们把上述讨论中提到的几个概念明确定义出来。

给定一个符号集$S$，我们对于一个一阶逻辑$S$-structure $\mathfrak{A}$定义过由该structure给出的理论(theory)，它是sentence集合$\text{Th}(\mathfrak{A}):=\{\varphi \in L_0^S\mid \mathfrak{A}(\varphi)=true\}$。现在扩展这一定义，使得“理论”不再依赖于某个给定的structure。对于任意一阶逻辑sentence集合$T$，称$T$是一个理论(theory)如果$T$是可满足的，且对于任何$\varphi\in L_0^S$，若$T\vdash \varphi$则$\varphi\in T$。也即，一个理论是一个可满足的sentence集合，它关于形式推理“$\vdash$”是封闭的。（$\text{Th}(\mathfrak{A})$满足新的定义，因为它可以被$\mathfrak{A}$满足，同时如果$\text{Th}(\mathfrak{A})\vdash \varphi$，那么$\mathfrak{A}(\varphi)=true$，因此$\varphi \in \text{Th}(\mathfrak{A})$。）

对于任意一个一阶逻辑sentence集合$T$，我们定义$T$关于形式推理“$\vdash$”的闭包$T^\vdash := \{\varphi \in L_0^S\mid T \vdash \varphi\}$。显然，如果$T$是可满足的，那么$T^\vdash$也是可满足的，此时$T^\vdash$一定是一个理论；反之，如果$T^\vdash$是一个理论，那么它是可满足的，因此$T\subseteq T^\vdash$也是可满足的。由此可见，$T^\vdash$是理论$\iff\text{Sat }T$。而根据完备性，$\text{Sat }T\iff \text{Con }T$。而$\text{Con }T$意味着存在$\varphi \in L_0^S$使得$T\vdash \varphi$不成立，那么$T^\vdash \subsetneq L_0^S$。反之，如果$T^\vdash \subsetneq L_0^S$，那么存在$\varphi \in L_0^S$使得$T\vdash \varphi$不成立，就意味着$\text{Con }T$（如果$\text{Inc }T$，那么$T$一定能推出$\varphi$）。综上，$T^\vdash$是理论$\iff\text{Sat }T$ $\iff$ $\text {Con }T\iff T^\vdash \subsetneq L_0^S$。

对于任意一个理论$T\subseteq L_0^S$，如果存在一个可判定的一阶逻辑sentence集合$\Phi$使得$\Phi^\vdash =T$，就称$T$是可公理化的(axiomatizable)，集合$\Phi$称为$T$的公理(axioms)。特别地，如果可以找到这样的$\Phi$使得$\Phi$是有限集，那么称$T$是可有限公理化的(finite axiomatizable)。

对于任意一个理论$T\subseteq L_0^S$，如果对于任意$\varphi\in L_0^S$都有“$\varphi\in T$成立”或“$\neg\varphi\in T$成立”，就称$T$是完全的(complete)。

定义了这些概念以后，先前的讨论就可以总结为：

• 可公理化的理论是可枚举的；
• 可公理化的完全的理论是可判定的；

我们进一步补充说明两点：

• 一，可公理化的理论不一定是可判定的。考虑反例$\{\varphi \in L^S_0\mid \ \vdash \varphi\}$，它可以看作空集推出的理论$\varnothing^\vdash$，因此是可公理化的，但我们证明过它是不可判定的；

• 二，可枚举的完全的理论是可判定的。对任意待判定的命题$\varphi$，启动枚举程序，因为完全性，有限步内一定会枚举到$\varphi$或$\neg\varphi$，因此是可判定的；

以自然数算术为例。我们已经证明理论$\text{Th}(\mathfrak{N})$是不可判定的，因此$\text{Th}(\mathfrak{N})$不可能既是可公理化的又是完全的。但是$\text{Th}(\mathfrak{N})$是自然数算术标准模型$\mathfrak{N}$下所有满足的命题，因此$\text{Th}(\mathfrak{N})$一定是完全的。这就推出了：$\text{Th}(\mathfrak{N})$是不可公理化的。也即，我们不可能找到一组可判定的一阶逻辑sentence $\Phi$，使得$\Phi^\vdash = \text{Th}(\mathfrak{N})$。

同理，由“可枚举的完全的理论是可判定的”也可推出$\text{Th}(\mathfrak{N})$是不可枚举的。甚至不存在一个程序能列出自然数算术上所有的真理。

哥德尔不完全性定理

我们证明了，即便是对于“自然数算术”这样简单的数学模型，它也是不可公理化的。这意味着我们不可能从$\text{Th}(\mathfrak{N})$中提取出一套“一致的”且“可判定的”一阶逻辑公式组$\Phi$，使得$\Phi^\vdash= \text{Th}(\mathfrak{N})$。无论怎样提取$\Phi$，只要$\Phi$是“一致的”且“可判定的”，就一定有$\Phi^\vdash \subsetneq \text{Th}(\mathfrak{N})$。这说明对于任意这样的$\Phi$，始终存在一个$\varphi\in \text{Th}(\mathfrak{N})$，使得$\Phi\not\vdash \varphi$。也即，公理$\Phi$不能由形式系统推出$\varphi$。那么，公理$\Phi$是否能形式地推出$\neg\varphi$呢？假如可以，也即假如$\Phi \vdash \neg\varphi$，那么由完备性$\Phi \models \neg\varphi$。既然$\Phi \subseteq \text{Th}(\mathfrak{N})$，因此$\mathfrak{N}(\Phi)=true$，于是$\mathfrak{N}(\varphi)=false$。但这就与$\varphi\in\text{Th}(\mathfrak{N})$矛盾了！说明，同时也有$\Phi\not\vdash \neg\varphi$。所以：无论怎样选取公理$\Phi$，只要$\Phi$是一致的且可判定的，那么始终存在一个$\varphi\in \text{Th}(\mathfrak{N})$，使得$\Phi\not\vdash \varphi$和$\Phi\not\vdash\neg\varphi$同时成立。这就是哥德尔第一不完全性定理(Gödel's First Incompleteness Theorem)。这意味着（至少对一阶逻辑语言来说）公理化方法在根本上是有局限性的。

然而，现代数学就是公理化的数学。人们“常识”中的任何一个自然数算术上的真理都可以从下面这组皮亚诺公理$\Phi_{\text{PA}}$中推出：（符号集为$S_{\text{ar}}={+,\cdot,0,1}$）

• $\forall x \ \neg x+1\equiv 0$
• $\forall x \ 0+x \equiv x$
• $\forall x \ x \cdot 0\equiv 0$
• $\forall x\forall y \ (x+1\equiv y+1\to x\equiv y)$
• $\forall x\forall y(x+(y+1)\equiv (x+y)+1)$
• $\forall x\forall y(x \cdot (y+1)\equiv (x\cdot y)+x)$
• $\{\forall x_1\cdots \forall x_n((\varphi\dfrac{0}{y}\land \forall y(\varphi\to \varphi\dfrac{y+1}{y}))\to \forall y\varphi)\mid n\in \mathbb{N},\varphi\in L^{S_{\text{ar}}},\text{free}(\varphi)\subseteq \{y,x_1,\cdots,x_n\}\}$

和用二阶逻辑表示的皮亚诺公理不同，我们现在用一个一阶逻辑的无穷集合来表示归纳公理。当然，根据我们在“一阶逻辑的表达能力”一文中证明的，现在这组一阶逻辑的皮亚诺公理$\Phi_{\text{PA}}$肯定无法把$\mathfrak{N}$刻画到同构。然而，我们可以认为现代数学中所有被人们所熟知的自然数算术真理都包含在$\Phi_{\text{PA}}^\vdash$内。显然，$\Phi_{\text{PA}}$是可满足的所以是一致的，并且它是可判定的（只需用程序检查公式是否符合上面那七种形式）。于是，我们知道$\Phi_{\text{PA}}^\vdash\subsetneq \text{Th}(\mathfrak{N})$。因此，存在一个“常识”之外的自然数算术真理$\varphi$，它不能由皮亚诺公理推出。问题是，这样的$\varphi$究竟是什么？哥德尔利用公式的“自指(self-reference)”构造出了这样一个$\varphi$。

我们首先定义“允许表示(allow representation)”的概念。给定一个$S_{\text{ar}}$上的公式集$\Phi$：

• 对于任意一个$\mathbb{N}$上的$k$元关系$R\in \mathbb{N}^k$，如果存在一个一阶逻辑$S_\text{ar}$-公式$\varphi_{v_1,\cdots,v_k}$满足“对于任意$n_1,\cdots,n_k\in \mathbb{N}$，若$R(n_1,\cdots,n_k)$成立则有$\Phi \vdash \varphi_{\overline{n_1},\cdots,\overline{n_k}}$，若$R(n_1,\cdots,n_k)$不成立则有$\Phi \vdash \neg\varphi_{\overline{n_1},\cdots,\overline{n_k}}$”，就称$k$元关系$R$是可用$\Phi$表示的(representable in $\Phi$)。
• 对于任意一个$\mathbb{N}$上的$k$元函数$f\in \mathbb{N}^k\to \mathbb{N}$，如果存在一个一阶逻辑$S_\text{ar}$-公式$\varphi_{v_1,\cdots,v_k,v_{k+1}}$满足“对于任意$n_1,\cdots,n_k,n\in \mathbb{N}$，若$f(n_1,\cdots,n_k)=n$则有$\Phi \vdash \varphi_{\overline{n_1},\cdots,\overline{n_k},\overline{n}}$，若$f(n_1,\cdots,n_k)\neq n$则有$\Phi \vdash \neg\varphi_{\overline{n_1},\cdots,\overline{n_k},\overline{n}}$，同时$\Phi\vdash \exists v( \varphi_{\overline{n_1},\cdots,\overline{n_k},v}\land \forall v'(\varphi_{\overline{n_1},\cdots,\overline{n_k},v'}\to v\equiv v'))$”，就称$k$元函数$f$是可用$\Phi$表示的(representable in $\Phi$)。

下面证明，如果$\Phi$是一致的并且是可判定的，那么每个“可用$\Phi$表示的”$k$元关系$R\in \mathbb{N}^k$都是可判定的。也即，存在一个程序$P$，对于每个输入的$k$元组$(n_1,\cdots,n_k)$，可以在有限步内正确判断这个$k$元组是否落在$R$中。设用来表示$R$的一阶逻辑公式是$\varphi_{v_1,\cdots,v_k}$。让计算机枚举$S_\text{ar}$下的所有证明（相继式演算），对于每个证明调用$\Phi$的判定程序检查其最下方的sequence的每个前件是否都落在$\Phi$中。如果满足，检查该sequence的结论是否为$\varphi_{\overline{n_1},\cdots,\overline{n_k}}$或$\neg \varphi_{\overline{n_1},\cdots,\overline{n_k}}$。如果是，则对于$\varphi_{\overline{n_1},\cdots,\overline{n_k}}$返回真，对于$\neg \varphi_{\overline{n_1},\cdots,\overline{n_k}}$返回假。这个程序一定在有限时间内停机，因为$\varphi_{\overline{n_1},\cdots,\overline{n_k}}$与$\neg\varphi_{\overline{n_1},\cdots,\overline{n_k}}$总有一个为真。并且因为$\Phi$是一致的，该程序的输出结果一定是正确的。证毕。

可以证明如果$\Phi$是一致的并且是可判定的，那么每个“可用$\Phi$表示的”$k$元函数$f\in \mathbb{N}^k\to \mathbb{N}$都是可计算的(computable)。其中，“可计算的”含义就是存在一个程序$P$，对于输入的$k$元组$(n_1,\cdots,n_k)$，可以在有限步内输出$f(n_1,\cdots,n_k)$。证明方法是完全类似的，唯一的改动是在检查sequence的结论时需要枚举函数值（由于函数值存在，这一枚举一定会在有限时间内结束，不需要特殊的枚举技巧），在此不再赘述。

对于一个$S_{\text{ar}}$上的公式集$\Phi$，如果对于任意$n\in\mathbb{N}$，$\mathbb{N}$上的所有可判定的$n$元关系都是可用$\Phi$表示的，所有可计算的$n$元函数都是可用$\Phi$表示的，就称公式集$\Phi$是允许表示的(allow representation)。

公式集$\text{Th}(\mathfrak{N})$是允许表示的。对于$\mathbb{N}$上任意一个可判定的$n$元关系$R$，设这个判定它的程序为$P_R$，它从格局$(1,l_1,\cdots,l_n)$执行到$(L,m_1,\cdots,m_n)$。我们证明过，可以用$S_\text{ar}$构造一个公式$\chi$使得这个公式被$\mathfrak{N}$满足当且仅当$P_R$完成对应的格局转移。而$\mathfrak{N}(\chi)=true$当且仅当$\text{Th}(\mathfrak{N})\vdash \chi$（这时简略的写法，严谨的写法应当把$\chi$中的自由变量替换为对应的自然数符号）。所以这就等价于：$n$元关系$R$是可用$\Phi$表示的。同理，所有$n$元函数$f$都是可用$\Phi$表示的。因此$\text{Th}(\mathfrak{N})$是允许表示的。

可见，“$\Phi$允许表示”这一定义是为了表达“可以用$\Phi$推出所有刻画$\mathbb{N}$上的‘可计算的’关系和函数的一阶逻辑公式”。而在我们证明$\text{Th}(\mathfrak{N})$允许表示时，实际上绕开了“$\mathbb{N}$”而直接复用了原先“可以用$S_\text{ar}$下的一阶逻辑公式刻画程序”的结论，这些一阶逻辑公式都是自然数算术上的公式，因此当然能由$\text{Th}(\mathfrak{N})$推出。而如果我们仔细考察我们用算术公式刻画程序的方法，就会发现我们没有用到任何超出“常识”的自然数算术公式。换言之，用以刻画程序的自然数算术公式可以仅由皮亚诺公理$\Phi_{PA}$推出（这是直观上自然的，并且已经被证明）。这样我们就得到：$\Phi_{\text{PA}}$也是允许表示的。

事实上，哥德尔最初证明自然数算术系统的不可判定性的时候，并不是向停机问题归约来完成的。因为“图灵机”及其等价的计算模型当时还没有被提出。所以，在哥德尔第一不完全性定理的原始表述中，有“允许表示”这一附加的条件。现在我们知道，“允许表示”这一条件就是为了使得逻辑系统具有编码寄存器机程序的能力。这本质上是一阶逻辑符号集对表达能力的影响的一个问题。我们在上一节中强调了，要能编码寄存器机程序的停机行为，对一阶逻辑的符号集是有要求的。能使用的符号越多，就越容易刻画程序的行为。如果符号不足，就无法完成向停机问题的归约。恰恰，如果符号不足，系统又恢复了可判定性。可见，正是当系统的“表达能力”跨越某一临界条件时，就会出现不可判定性。“可以刻画计算机”和“允许表示”都是这样的临界条件。这两个条件都有一种“自指”性质：逻辑系统表达自身的能力。一旦逻辑系统能够刻画计算程序的运行，这个系统就可以刻画把自身输入自身的程序，从而产生停机问题的悖论。同样的，（我们将要看到）如果一个逻辑系统允许表示自己，也将导致悖论。这样的由“自指”产生的矛盾就是计算理论中常用的证明技巧：对角线方法(diagonal argument)。它很像“说谎者悖论(the liar paradox)”：小明说“我说的这句话是假话”，那么他的这句话究竟是真话还是假话呢？在这里，小明的语言“指向”了他自己，于是他的“系统”就出现了矛盾。

为了让自然数算术的一阶逻辑公式能够指向自己，首先要能把每个$S_{\text{ar}}$-formula编码为一个自然数。和停机问题中一样，我们再次使用哥德尔编码的技巧：因为$S_\text{ar}$-formula是可枚举的，那么存在程序$P$能把全体$S_\text{ar}$-formula依字典序从小到大无重复的打印出来。这样，我们就可以在每个$S_\text{ar}$-formula $\varphi$和其在此程序下的字典序$n$之间建立双射，把$n$称作$\varphi$的哥德尔编码。$\varphi$的哥德尔编码记为$[\varphi]$。

设$\Phi$是允许表示的。下面证明，对于任意含有恰好一个自由变元的公式$\psi\in L_1^{S_\text{ar}}$，存在一个$\varphi\in L_0^{S_\text{ar}}$使得$\Phi \vdash (\varphi \leftrightarrow \psi_{\overline{[\varphi]}})$。这称为不动点定理(Fixed Point Theorem)。下面我们要基于$\psi$构造这个$\varphi$，使得$\varphi$具有“$\psi$代入$[\varphi]$”时的性质。证明：构造自然数上的二元函数$F(n,m)$，当且仅当哥德尔编码为$n$的算术公式$\varphi_n$恰好只有一个自由变元时，函数返回公式“$\varphi_n$将自由变元代入$\overline{m}$”的编码，否则返回0。由于$\Phi$允许表示，$F(n,m)=l$可以被表示为$\Phi \vdash \varphi^{F}_{n,m,l}$。对于给定的$\psi$，我们令$\chi_{v_0}=\forall x(\varphi^F_{v_0,v_0,x}\to \psi_{x})$，可见它表示“第$v_0$个算术公式代入$v_0$后编码为$x$”成立时能推出“$\psi_x$成立”（自指！）。而$\chi_{v_0}$本身也是一个算术公式，假设它的编码为$n$。令$\varphi=\chi_{\overline{n}}$。也即$\varphi=\forall x(\varphi^F_{\overline{n},\overline{n},x}\to \psi_x)$。我们验证$\Phi \vdash (\varphi \leftrightarrow \psi_{\overline{[\varphi]}})$成立：左推右，假设$\Phi\vdash \varphi$，要证$\Phi\vdash \psi_{\overline{[\varphi]}}$。根据$\Phi \vdash \varphi$，也即$\Phi\vdash\forall x(\varphi^F_{\overline{n},\overline{n},x}\to \psi_x)$，取$x$为$[\varphi]$代入有$\Phi \vdash \varphi^F_{\overline{n},\overline{n},[\varphi]}$能推出$\Phi \vdash \psi_{\overline{[\varphi]}}$。那么只需证$\Phi \vdash \varphi^F_{\overline{n},\overline{n},[\varphi]}$。$F(n,n)=F([\chi_{v_0}],n)$ $=[\chi_{\overline{n}}]$ $=[\varphi]$，根据可表示的定义就有$\Phi \vdash \varphi^F_{\overline{n},\overline{n},[\varphi]}$，得证。右推左，假设$\Phi\vdash \psi_{\overline{[\varphi]}}$，要证$\Phi\vdash \forall x(\varphi^F_{\overline{n},\overline{n},x}\to \psi_x)$。假设对于已知$F(n,n)=[\varphi]$成立，那么根据函数映射的唯一性写出$\Phi \vdash \forall x(\varphi^F_{\overline{n},\overline{n},x}\rightarrow x\equiv [\varphi])$。假设对于任意$z\in \mathbb{N}$有$\Phi\vdash \varphi^F_{\overline{n},\overline{n},\overline{z}}$，那么$[\varphi]=z$。现在$\Phi\vdash \psi_{\overline{[\varphi]}}$，所以$\Phi\vdash \psi_{\overline{z}}$。因此$\Phi\vdash \forall z(\varphi^f_{\overline{n},\overline{n},z}\to \psi_z)$，这就是要证的。证毕。

根据不动点定理，我们可以证明：对于任意$S_\text{ar}$下的公式集$\Phi$，如果$\Phi$是一致的并且是允许表示的，那么自然数集合$\{[\varphi]\mid \varphi \in \Phi^\vdash\}$是不可用$\Phi$表示的（我们对$\mathbb{N}$上的一元关系定义过“可用$\Phi$表示”，而一个自然数集合可以看作一个$\mathbb{N}$上的一元关系）。证明：如果这个一元关系是可表示的，设表示它的公式为$\chi_{v_0}$。取$\psi:=\neg\chi_{v_0}$，由不动点定理，存在一个$\alpha\in L_0^{S_\text{ar}}$使得$\Phi\vdash \alpha\leftrightarrow \neg\chi_{\overline{[\alpha]}}$。但是，如果$\Phi\vdash \alpha$，那么$[\alpha]\in \{[\varphi]\mid \varphi \in \Phi^\vdash\}$，因此$\Phi\vdash \chi_{\overline{[\alpha]}}$；如果$\Phi\not\vdash \alpha$，那么$[\alpha]\not\in \{[\varphi]\mid \varphi \in \Phi^\vdash\}$，因此$\Phi\vdash \neg\chi_{\overline{[\alpha]}}$。所以，$\Phi\vdash \alpha\leftrightarrow\chi_{\overline{\alpha}}$。由此可见，$\Phi\vdash \alpha$当且仅当$\Phi \vdash \chi_{\overline{[\alpha]}}$当且仅当$\Phi \vdash \neg\chi_{\overline{[\alpha]}}$。但是$\Phi$是一致的，因此这是不可能的。所以自然数集合$\{[\varphi]\mid \varphi \in \Phi^\vdash\}$是不可用$\Phi$表示的。

$\text{Th}(\mathfrak{N})$就是一致的并且允许表示的，并且它本身就对“$\vdash$”封闭。所以，集合$[\text{Th}(\mathfrak{N})]:=\{[\varphi]\mid \varphi \in \text{Th}(\mathfrak{N})\}$是不可用$\text{Th}(\mathfrak{N})$表示的。也即，“算术真理是不可在算术系统内部定义的”。

于是，对于任意$\Phi\subseteq L^{S_\text{ar}}$，如果$\Phi$是一致的、可判定的、允许表示的，那么$\Phi^\vdash$是不完全的，也即存在$\varphi\in L_0^{S_\text{ar}}$满足$\Phi\not\vdash \varphi$且$\Phi\not\vdash\neg\varphi$。这就是哥德尔第一不完全性定理的原始陈述。现在可以利用不动点定理给出证明：如果$\Phi^\vdash$是完全的，并且显然它可由$\Phi$公理化，那么由“可公理化的完全的理论是可判定的”可知$\Phi^\vdash$是可判定的。进而，$\{[\varphi]\mid \varphi\in \Phi^{\vdash}\}$是$\mathbb{N}$上可判定的一元关系。根据$\Phi$是允许表示的，我们有$\{[\varphi]\mid \varphi\in \Phi^{\vdash}\}$是可由$\Phi$表示的。但我们已经证明了$\{[\varphi]\mid \varphi \in \Phi^\vdash\}$是不可用$\Phi$表示的，矛盾。所以$\Phi^\vdash$是不完全的。证毕。

假设$\Phi$是一致的、可判定的、允许表示的。现在我们可以构造那个不存在于$\Phi$中的自然数算术命题了。由于证明（相继式演算）是可枚举的，我们可以为每一个证明也按字典序赋予一个哥德尔编码。我们构造一个二元关系$H$，满足$H(n,m)$成立当且仅当编码为$m$的证明以“$\varphi_1\cdots \varphi_k \ \varphi$”结尾，其中$[\varphi]=n$，且$\varphi_i\in \Phi$。因为$\Phi$是可判定的，所以$H$也是可判定的。因此$H$是可由$\Phi$表示的，它刻画“编码为$n$的公式是否可证（是否能由编码为$m$的证明给出）”。设表示$H$的公式为$\varphi^H_{v_0,v_1}$。令公式$\text{DER}^{\Phi}_{x}:=\exists y\varphi^H_{x,y}$，它刻画“编码为$x$的公式是否可证”，其中DER是derivable的缩写。应用不动点定理，令$\psi_x=\neg\text{DER}^\Phi_x$，可知：存在$\varphi\in L_0^{S_\text{ar}}$满足$\Phi \vdash \varphi \leftrightarrow \neg \text{DER}^{\Phi}_{[\varphi]}$。因为$\Phi$是一致的，所以$\Phi\not\vdash \varphi$：假如$\Phi \vdash \varphi$，由$\Phi \vdash \varphi \leftrightarrow \neg \text{DER}^{\Phi}_{[\varphi]}$可知$\Phi\vdash \neg\text{DER}^\Phi_{[\varphi]}$。但是$\Phi\vdash \varphi$存在一个$m\in \mathbb{N}$使得意味着编码为$m$的证明证出了$\Phi \vdash \varphi$，因此$H([\varphi],m)$成立，根据$H$可表示，推出$\Phi\vdash \text{DER}^\Phi_{[\varphi]}$。这与$\Phi$一致矛盾。因此$\Phi\not\vdash \varphi$。我们任取一个不可证的命题，例如$\neg 0\equiv 0$，有$\Phi\not\vdash \neg 0\equiv 0$。我们看到，$\Phi\not\vdash \neg 0\equiv 0$当且仅当$\Phi$是一致的。所以我们刚刚得出的结论“如果$\Phi$一致，那么$\Phi\not\vdash \varphi$”可以被写成一个公式$\neg\text{DER}^\Phi_{[\neg 0\equiv 0]}\to \neg \text{DER}^{\Phi}_{[\varphi]}$。这个公式所表达的内容从根本上看只是对寄存器机的一种可能的运行过程的刻画，而我们强调过寄存器机的行为是能用皮亚诺公理以内的算术来刻画的。因此，$\Phi_{\text{PA}}\vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}\to \neg \text{DER}^{\Phi}_{[\varphi]}$。进而，对于任意$\Phi\supseteq \Phi_{\text{PA}}$，$\Phi\vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}\to \neg \text{DER}^{\Phi}_{[\varphi]}$。

现在，对于任意$\Phi\supseteq \Phi_{\text{PA}}$，现在我们就写出那个不能由$\Phi$推出的真命题：

$$\neg\text{DER}^\Phi_{[\neg 0\equiv 0]}$$

我们来验证确实有$\Phi \not\vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}$：假如$\Phi \vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}$，那么由$\Phi\vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}\to \neg \text{DER}^{\Phi}_{[\varphi]}$可知$\Phi \vdash \neg \text{DER}^{\Phi}_{[\varphi]}$。由$\Phi \vdash \varphi \leftrightarrow \neg \text{DER}^{\Phi}_{[\varphi]}$可知$\Phi\vdash \varphi$。但是$\Phi$是一致的，我们已经证得$\Phi\not\vdash \varphi$。矛盾。因此$\Phi \not\vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}$。

这就是哥德尔第二不完全性定理(Gödel's Second Incompleteness Theorem)：对于任意$\Phi\subseteq L_0^{S_\text{ar}}$，若$\Phi$是一致的，可判定的，且满足$\Phi_{\text{PA}}\subseteq\Phi$（这蕴含了$\Phi$是允许表示的），那么$\Phi \not\vdash \neg\text{DER}^\Phi_{[\neg 0\equiv 0]}$。

哥德尔第二不完全性定理告诉我们，只要一个自然数算术的公理系统达到皮亚诺系统的表达能力，它就无法证明一个自然数算术的真命题，这个命题描述的是这个系统自身的一致性。简单来说，一个系统只要复杂到能够表达算术，就一定无法在这个系统内部证明其自身的一致性。

尽管哥德尔第一不完全性定理和第二不完全性定理都是在“一阶逻辑语言”和“自然数算术”这两个特殊的系统下得到证明的，但它们却很容易迁移到其它逻辑语言和数学模型上。因为其证明的核心是构造自指，而这一构造唯一的要求就是逻辑语言的表达能力要能足够刻画“（图灵机的）计算”。于是，“不完全性”的结论自然也在表达能力更强的逻辑语言以及更复杂的数学模型上成立。例如，利用第一不完全性定理的结论，集合论的ZFC公理就有不可证真也不可证伪的命题，而利用第二不完全性定理的结论，这一命题就是那个刻画“ZFC系统的一致性”的命题。而既然整个现代数学都可以看作是建立在ZFC公理系统之上的形式系统，这就意味着整个现代数学在根基上是有缺陷的。至少我们已经知道，存在许多永远无法在现代数学系统内部得到证明的命题，要想判断这些命题的真伪必须引入“系统以外”的方法。假如真的存在一套“完美”的数学系统，那么这套系统一定不是现代意义上的“形式系统”。

参考文献

[1] H.-D. Ebbinghaus, J.Flum, W. Thomas: Mathematical Logic