哥德尔不完备性定理
前言
“总有办法知道每句话是真是假”，和“所有的真理都能被证明”，是非常自然的想法。但是，至少在基础算术中，不是所有的命题都能判断真假，且不是所有的真命题都能被证明出来。说明这一现象的就是哥德尔不完备性定理。
哥德尔不完备性定理是数学领域内最反直觉的定理之一：即使是（几乎）最简单的数学系统——仅包括自然数的加减乘运算（小学2年级数学内容），也复杂到 存在无法被证明的真命题。
不完备性定理的表述
哥德尔不完备性定理一共有两条：
哥德尔第一不完备性定理：如果算术公理没有⽭盾，那么存在⼀个算术命题，它是真的，但不能通过算术公理证明出来。
哥德尔第二不完备性定理：如果算术公理没有⽭盾，那么“算术公理没有⽭盾”这个命题本⾝不能通过算术公理证明出来。
这其中，算术公理（更具体地说，皮亚诺算术公理）是定义基础算术的公理系统，一共有5条，分别是：
- 0是自然数；
- 每个自然数n都有一个后继数（通常记作S(n)或n+1，表示n的下一个自然数）；
- 0不是任何自然数的后继数；
- 对于每个自然数m和n，m+1=n+1 当且仅当 m=n；
- 如果一个性质对0成立；且，如果假设其对n成立，就可以证明其对S(n)也成立，那么这个性质对所有自然数都成立。（即 可以使用数学归纳法）
用更严谨的数学语言来描述哥德尔不完备性定理，就是：
只要一个公理系统强大到足够表达基础算术，且这个系统是一致的，那么这个系统就一定是不完备的。此外，无法在上述系统内部证明本系统是一致的。
公理系统：用规定好的符号，和一些起始公理和推理规则定义的数学系统。欧氏几何，皮亚诺算术公理等都是公理化系统。
一致：不存在一个命题，既可以被证明为真，又可以被证明为假。
完备：不存在某个命题，既不能被证明为真，也不能被证明为假。或者说，所有的真命题都能被证明。
第一不完备性定理的证明
设 公理体系T能够描述自然数的加、减、乘运算（即至少包含皮亚诺算术作为其子系统）。除非另有说明，下文的所有证明都在公理系统T中进行。
1. 命题的可编码性
存在一种编码方法，可以将任何一个命题转换为一个自然数。
证明：
首先，总可以将每个构成命题的符号（如数字，运算符，括号等）映射到一个唯一的自然数。
（可递推的）系统中，构成命题的符号的数量总是有限的，比如公理体系T一共只会用到12个运算符号：
- ~（非）
- ∨（或）
- ⊃（如果...那么...）
- ∃（存在）
- =（等于）
- 0（零）
- S（后继）
- (（左括号）
- )（右括号）
- ,（逗号）
- +（加）
- ×（乘）
和一些变量符号（如 x，y，z 等）。
想要表达任何一个命题，都只需要这些符号。
然后，总可以将一个命题的符号序列转换为一个自然数序列。
比如说，这12个运算符号可以被编码为自然数1到12。x，y，z等变量符号通常用12之后的素数编码：13，17，19...。
注：使用素数是为了简化描述，用13，14，15...等自然数来编码变量符号也是合法的。
比如，命题 ~(Sx=0)（“x 的后继数不等于 0”，即 “0 不是任何自然数的后继数”）
就可以被编码为一个自然数序列：{1, 8, 13, 5, 9}。
最后，总可以将这个自然数序列编码为一个单一的自然数，比如通过将每个数字作为一个质因数的指数。
对于自然数序列{1, 8, 13, 5, 9}，其对应的编码自然数为 2^1 * 3^8 * 5^13 * 7^5 * 11^9，即634796401646829484863281250。此数字被称为此命题的“哥德尔数”。
任何一个命题都可以被编码为一个自然数，而自然数的集合是可枚举的（即可以按顺序，不重不漏地一一列举出来），所以命题的集合也是可枚举的。
2. 证明过程的可编码性
存在一种编码方法，可以将任何一个证明过程转换为一个自然数。
其思路与上文类似，证明如下：
任何一个命题的证明过程本质上就是一系列有限且有序的命题，第一个命题是公理，最后一个命题是要证明的结论，而总可以将任何一个命题转换为一个自然数。所以，一个证明的命题序列可以被编码为一个自然数序列，并最终编码为一个自然数。
比如，命题 (∃x)(x=S0) （“存在0的后继（即存在1）”）的证明过程为：
- (∃x)(x=Sy)
- (∃x)(x=S0)
设这两个命题的哥德尔数分别为y和z（它们都是非常大的数，见附录），那么这个证明过程可以被编码为一个自然数序列 {y, z}，并最终编码为一个自然数 2^y * 3^z。
自然数的集合是可枚举的，所以证明过程的集合也是可枚举的。
3. 程序的可编码性
存在一种编码方法，可以将任何一个程序转换为一个自然数。
证明：
因为任何一个程序都是有限种类的字符的有限长序列，而字符序列可以被编码为自然数（证明见上）。因此，任何一个程序都可以被编码为一个自然数。
这样做的妙处在于，由于程序本身也可以被编码为自然数，所以程序可以“谈论”/处理其他的程序，甚至包括它自己。
由于程序/算法/图灵机均为 能以有限步骤、以机械的方式计算出结果的有效过程，所以在计算理论中，程序/算法/图灵机这三个概念等价，即，总可以写出一个执行某算法的图灵机，也总可以构建一个执行某算法的程序（Church-Turing 定理）。
鉴于非数学/计算机科学的读者可能不太熟悉图灵机的概念，本文将用“程序”或“算法”代替“图灵机”一词，来稍微增加一点直观性。除非另有说明，下文中，所有“程序”和“算法” 均是指 有限长，输入为自然数，且内部具有有限个状态的程序（其实就是图灵机）。
4. 枚举式证明算法
存在通用的 可以证明所有存在证明的命题的算法。
注：“通用” 指，此算法本身是固定的，不会随具体输入而改变。
证明：
在数学证明中，推理规则一共只有2条：肯定前件（由ϕ与ϕ→ψ推出ψ）和全称化（由ϕ推出∀xϕ）。
所以，想要判断一个证明过程是否正确，只需要判断每一步得到的推论是否符合语法，且是否可以由推理规则 从公理和之前的推论中推出。这些工作只是简单的枚举工作，故可以在有限步骤内机械地完成。
剩下的工作就简单了：因为每一个证明过程都可以被编码为一个自然数（证明见上），所以可以从2开始，依次暴力枚举所有自然数，检查其对应的证明过程是否是对此命题的有效证明。只要这个命题是可以被证明的，那么总有一个自然数对应的证明过程会被找到。
注：对于为假或不可证明的命题，此方法会永远运行下去，永远不会停止。
这说明，存在一个通用的算法（暴力枚举+逐步验证），可以在有限步骤内证明任何可以证明的命题。只要一个命题可以被证明，就可以使用此算法找到其证明方法。
5. 停机问题
不存在通用算法，能够在有限步内正确判断任意一个算术命题。
使用反证法：假设存在一个通用算法U(M, x)，能够正确判断任意程序M在输入为x时（下文记作M(x)）是否会停机（即，会在有限步内停止运行）。
让我们依据算法U构造另一个程序N(Y)：如果U判断Y(Y)会停机，那么我们就让N(Y)就会进入一个死循环；如果U判断Y(Y)进入死循环，那么我们就让N(Y)立刻停机。N的代码化表述见附录。
注：Y(Y)是合法的，因为Y是一个程序，可以被编码为一个自然数（证明见上），所以Y本身也可以作为程序的合法输入。
现在，尝试用通用算法U判断N(N)是否会停机。
如果通用算法U判断N(N)会停机，在N(N)内部就会进入死循环。反之，如果U判断N(N)不会停机，N(N)就会立刻停机。无论如何，通用算法U都会给出错误的判断。
因此，通用算法U不可能存在，即不存在任何通用方法，能够在有限步内正确判断任意一个程序会不会停机。
继续使用反证法：假设存在一个通用算法V(y)，能够在有限步内正确判断任意一个算术命题y是否为真。
考虑此命题：“M(x)会停机”。
如果V能够在有限步内正确判断这个命题，那么V就可以充当判断程序是否停机的通用算法U。但是，上文中已经证明不存在通用算法U，所以V不可能存在。即，不存在通用算法，能够在有限步内正确判断任意一个算术命题。
6. 第一不完备性定理的一种证明
只要公理体系T是一致的，那么T一定是不完备的。
使用反证法：假设公理体系T一致且完备，那么就可以使用 暴力枚举+逐步验证 的方法，同时开始证明任意算术命题A和非A。
因为T是一致的，A命题和非A命题总有一个为真。不妨设A命题为真。
因为T是完备的，所有的真命题都能被证明，所以A命题一定能被证明。那么，总可以使用 暴力枚举+逐步验证 的方法，在有限步内找到A命题的正确证明。A命题被证明为真，说明非A命题为假，说明这两个命题均在有限步内得到了正确的判断。
由于算术命题A是任取的，这说明，对任意算术命题，甚至包括上文的N(N)停机问题，总有通用的方法能给出正确判断。这与上文中证明的“不存在通用算法，能够在有限步内正确判断任意一个算术命题。”矛盾。
因此，原假设不成立，公理体系T要么不一致，要么不完备。如果承认T是一致的，那么就必须承认T中存在不能被证明的真命题A，T是不完备的。
证毕。
注：T是否一致是另外一个独立的问题。一般来说，我们不愿意承认一个公理体系是不一致的，否则我们会在其内部证明出各种天马行空的结果，如 1=0 等等。
7. 第一不完备性定理的另一种证明
只要公理体系T是一致的，那么T一定是不完备的。
首先，定义一个函数 sub(a,b,c)。此函数的作用是：取哥德尔数为a的命题，找到命题中哥德尔数为c的符号的位置，把它替换成数字b，计算并返回新命题的哥德尔数。
考虑此命题：“无法证明哥德尔数是 sub(y,y,17) 的命题”，设此命题的哥德尔数为n。
让我们先分析sub(y,y,17)：
依据流程，首先，取哥德尔数为y的命题。假设此命题为 (∃x)(x=Sy)，则y的值为1722255...0000000（见附录）。
然后，在此命题中，找到哥德尔数为17的符号（即“y”符号），并将其替换为1722255...0000000，得到新的命题：(∃x)(x=s1722255...0000000)
那么，以 sub(y,y,17) 为哥德尔数的命题就是 (∃x)(x=s1722255...0000000)
现在，考虑此命题：“无法证明哥德尔数是 sub(n,n,17) 的命题”，记此命题为G。
同样，让我们先分析sub(y,y,17)：首先，取哥德尔数为n的命题，即 “无法证明哥德尔数是 sub(y,y,17) 的命题”。
然后，找到哥德尔数为17的符号，并将其替换为n，得到新的命题：“无法证明哥德尔数是 sub(n,n,17) 的命题”。此命题即G命题本身。
如此，我们通过复杂且抽象的方式，构造了一个自指命题G。
现在，让我们判断G命题是否为真。
如果G命题是一个假命题，则说明 可以证明哥德尔数是 sub(n,n,17) 的命题，所以哥德尔数是sub(n,n,17)的命题是一个真命题，即，G命题是一个真命题。这与原假设矛盾。
所以，如果承认T是一致的，那么G命题就只能是一个真命题。
但由于它说“G命题无法证明的”，所以G命题就是一个无法被证明出来的真命题。
总结以上逻辑：如果承认公理体系T是一致的，那么在T中就存在无法被证明出来的真命题，T是不完备的。
证毕。
第二不完备性定理的证明
只要公理体系 T 是一致的，就不可能在 T 内部证明 T 的一致性。
证明：
第一不完备性定理说明：假如公理体系T是一致的，那么G命题就无法被证明出来。此时，由于G命题说自己是无法证明的，所以G命题为真。
即，“T是一致的”证明了G命题。
假设 在T内部能证明T是一致的，那么在T内部就能证明G命题，这就与第一不完备性定理矛盾。这说明 在T内部不能证明T是一致的。
即，如果承认公理体系T是一致的，就不可能在T内部证明T的一致性。
证毕。
后记
目前，已经发现了一些在皮亚诺算术中无法证明的真命题，比如 加强有限拉姆齐定理（Strengthened finite Ramsey theorem）等。
附录1：程序N(Y)的代码化表述
1 | def N(Y): |
附录2：y的值
假设以 y 为哥德尔数的命题为 (∃x)(x=Sy)
则 y = 2^8 * 3^4 * 5^13 * 7^9 * 11^8 * 13^13 * 17^5 * 19^7 * 23^17 * 29^9
y 的值为：
172225505803959398742621651659678877886965404082311908389214945877004912002249920215937500000000。
附录3：参考资料
《哥德尔、埃舍尔、巴赫：集异璧之大成》
毕导的视频 吐个槽，这个视频被选进了b站每周必看，b站现在这么硬核了吗？
ChatGPT o3