从数理逻辑本身到哥德尔不完备定理的一种证明方法

音乐能激发或抚慰情怀，绘画使人赏心悦目，诗歌能动人心弦，哲学使人获得智慧，科学可以改善物质生活，但数学能给予以上的一切。

​ -- 克莱因

# 对于数学和数理逻辑的思考

谈到数学，我不禁想到一个经典的问题：数学是被人发现的，还是被人发明的？这好像已经迈入了哲学的范畴， 我有一个苹果，然后再有了一个苹果，于是共有 1+1=2 个苹果，这好像是想当然的，因为像苹果这类区限分明的自然事物是可以数的，人们发现自然物可以被计数，于是就有了数学中的加法。人们定义了 1 和 2，同时定义了加法的规则，于是有了 1+1=2，这样做是合理的，符合人类直觉的，并且与许多人们公认的规则结合在在一起建立了数学大厦，并且在几千年的人类文明进化史中没有出什么差错。我们今天坐在高楼大厦里，用着精密的手机，电脑，坐着高铁，飞机穿梭于世界各地。我们靠它们生存，但是我们如何保证高楼不会坍塌，坐的飞机不会坠落呢，因为我们有强大的 “武器” 依靠，即数学的证明。这些东西无一不是在图纸上被确定性的定义了材料和尺寸等规则，并经过了数学的验证，设计师拍着胸脯保证，在数学上已经验证过了，才最终被制造出来。高效运转的人类社会离不开数学，而数学大厦又建造在这些所谓的 “公理” 之上，而这些公理的正确性，如果靠的仅仅是我们人类的直觉，这不免让我有些发怵。** 直觉是靠的住的吗？** 在几何上，两个点可以唯一确定一条直线，二维平面内的两条直线不是平行就必定相交，所有的直角都相等。。。 这些都是不证自明的定理，很少有人会怀疑。但是我们知道，有些时候直觉是靠不住的，比如哥伦布环绕了地球一圈并返回到了起点，我们就理所应当的认为地球是圆的，因为排除了地球边缘是深不见底的深渊或者天圆地方等盛行的理论，但是我们很少想过，地球会不会是一个甜甜圈，会不会是一个莫比乌斯环？

但对于这些貌似是不证自明的定理，如果他们是不对的，那人类社会不可能高度发达，所以我倾向于认为数学是被人发现的，但我们常用的自然数，符号等属于我们发明的 “符号体系”，这些符号体系体现了自然界中某些本质，某些永远正确，客观存在的东西，这些东西就是数学。 有一点我们必须确定，不能对每一个数学结论都凭借直觉来确认，我们可以根据直觉判断自行车的轮子应当是圆的，但对于更复杂的东西好像就不行了，否则很可能会踩雷，导致某天某样东西突然崩塌，造成不可预计的后果，我们需要一些从正确的结论推导出新结论的东西，并且保证这个 “过程” 和这个 “过程” 的出发点是正确的，我觉得这就是数理逻辑研究的领域，数理逻辑研究的是数学本身，即 “数学的数学”。当然数理逻辑也有出发点，一些不需要证明就能被认为正确的东西，否则就会出现 “数学的数学的数学”，无限递归下去，这是很可笑的，但我们需要保障这些出发点尽可能少（减少出错的机会），并且不容置疑的正确。

# 哥德尔不完备定理的出现

在数理逻辑这个领域发展之初，数学家们为数学寻求坚实的基础：一系列基本的数学事实，或者说公理。它们既是一致的，即不会导致矛盾，同时也是完备的，以作为所有数学真理的基础。但是哥德尔发表的不完备定理彻底粉碎了这一梦想，这一定理简短又振聋发聩，大概意思是

—— 每个无矛盾的数学系统都存在一些语句无法被证明（不完备的）。

这意味着不存在一个对万事万物皆适用的数学理论，可证明性和正确性也无法统一。数学家可以证明的内容取决于他们的初始假设，而非所有结论所依据的基本事实（这个自然界本身）。这个定理引起了轩然大波，也产生了许多有趣的问题，对于这些问题的讨论，许多又进入到了哲学的领域，比如不完备定理依赖算术又说算术是不完备的，这不是循环论证吗？物理学需要数学，哥德尔不完备定理是不是意味着我们永远无法理解宇宙等。

# 一个有趣的证明

这个证明是在 (如何简单清晰地解释哥德尔不完备定理？ - 知乎 (zhihu.com) 看到的

哥德尔的主要策略是把关于某个公理系统的语句映射到一个特定的系统内的语句，即映射到一个关于数字的语句。这个映射使公理系统能够有效地谈论自身。

这个过程的第一步是将任何可能的数学语句或一系列语句映射到一个被称为哥德尔数的唯一数字。

这个对哥德尔的方案略微修改后的版本是由欧内斯特・内格尔（Ernest Nagel）和詹姆士・纽曼（James Newman）在他们 1958 年出版的《哥德尔的证明》（《Gödel's Proof》）的书中提出的，始于用 12 个基本符号作为词汇来表达一系列基本公理。例如，用符号 ∃表示存在，用符号 + 表示加法。重要的是，符号 s 表示 “后继”，给出了表示特定数字的方法。例如， ss0 指的是 2 。

这 12 个符号被分配到了从 1 至 12 的哥德尔数。

下一步，用字母表示变量，从 xyz 开始，映射到大于 12 的素数（即 13,17,19 ）。

接下来，这些符号和变量的任意组合，即任何可以被构造的算术公式或公式序列，都将有自己的哥德尔数。

比如，考虑 0=0 。这个公式的三个符号对应的哥德尔数是 6,5,6 。哥德尔需要将这三个数字的序列改为一个唯一的数字，也就是其他符号序列不会生成的数字。 为此，他采用前三个质数（2,3,5 ），将每个符号的哥德尔数作为这个序列相同位置的指数，并将它们相乘。因此 0=0 变为 $2^{6} \times 3^{5} \times 5^{6}$，即 243000000 。

该映射之所以有效，是因为没有两个公式会有相同的哥德尔数。 哥德尔数是整数，而整数仅以一种方式分解为质数。因此，243000000 的唯一质数分解是$2^{6} \times 3^{5} \times 5^{6}$ ，这意味着只有一种可能的方法可以解码这个哥德尔数：公式 0=0。

哥德尔之后更进一步。数学证明是由一系列的公式组成的。因此，哥德尔也为每个公式序列赋予了唯一的哥德尔编号。在这种情况下，正如前面一样，他从质数列表开始，即 2,3,5 依此类推。 然后，他将公式的哥德尔数作为对应位置素数序列的指数（例如，若先出现 0=0 ，则为$2^{243000000} \times ...$），然后将所有数相乘。

算数元数学

这么做真正的好处是，即使是关于算术公式的语句，也被称为元数学语句，也可以转换为以它们自身的哥德尔数所产生的公式。

首先考虑公式 $\sim (0=0)$，意思是 “零不等于零”。这个公式显然的错误的。不过它依然有哥德尔数：2 的 1 次幂（符号 $\sim$ 的哥德尔数是 1），乘以 3 的 8 次幂（“左括号” 的哥德尔数是 8），依次类推，得到 $2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9$ 。

因为我们可以为所有公式甚至错误的公式生成哥德尔数，所以我们可以通过谈论它们的哥德尔数来明智地谈论这些公式。

考虑以下语句：“公式$\sim(0=0)$ 的第一个符号是波浪号”。这个关于 $\sim(0=0)$) 的正确的元数学语句转化为关于公式的哥德尔数的语句，即其第一个指数为 1，即波浪号的哥德尔数。 换句话说，我们的语句为$2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9$ 只有一个 2 因子。如果$\sim(0=0)$ 以除波浪号以外的任何符号开头，那么其哥德尔数至少应该有两个 2 因子。因此，更准确地说， 2 是$2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9$ 的因子，但 $2^2$ 不是因子。

我们可以将最后一个语句转换为精确的算术公式，即我们可以使用基本符号写下。这个公式当然有一个哥德尔数，我们可以通过将其符号映射到素数的幂上来进行计算。

对于好奇的读者，这个语句可以读作 “存在一个整数 x 使得 x 乘以 2 等于$2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9$，且不存在一个整数 x 使得 xx 乘以 4 等于$2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9$。对应的公式为

$(\exists x)(x \times s s 0=s s s \ldots s s s 0) \cdot \sim(\exists x)(x \times s s s s 0=s s s \ldots s s s 0)$

其中$s s s \ldots s s s 0$ 表示有 $2^1\times 3^8\times5^6\times7^5\times11^6\times 13^9$ 个后继符号 s 。符号$\cdot$ 意思是 “且”，是基本词汇中较长表达的简写： $p\cdot q$ 可以用 $\sim(\sim p\vee \sim q)$ 代替。

对于这个例子，内格尔和纽曼写道 “这说明了一个非常普遍且深刻的见解，它位于哥德尔发现的核心：长链符号的印刷性质可以间接但完全准确地 被对大整数因式分解性质的讨论替代。

对于元数学语句，转换为符号依然是可能的：“存在某个哥德尔数为 x 的公式序列，可以证明哥德尔数为 k 的公式”，或者简言之，“哥德尔数为 k 的公式可以被证明”。将此类语句 “算术化” 的能力为解决这个难题奠定了基础。

G 自身

哥德尔的独到见解是，他可以用公式本身的哥德尔数代入到公式中，从而导致无穷无尽的麻烦。

为了看出这个代入是如何起效的，考虑公式 (∃x)(x=sy) （它读作 “存在一个变量 x 使得它是 y 的后继”，或者简言之，“ y 有一个后继”）。像所有公式一样，它有哥德尔数，即某个大整数，我们就叫它 m 。

现在让我们在公式中用 m 代替符号 y 。 这形成一个新公式 (∃x)(x=sm) ，表示 “ m 有一个后继”。 我们怎么记这个公式的哥德尔数呢？我们需要传达三点信息：我们从哥德尔数为 m 的公式开始。 在其中，我们用 m 代替了符号 y 。根据前面介绍的映射方案，符号 y 的哥德尔数为 17。因此，让我们指定新公式的哥德尔数为 sub (m,m,17) 。

译者注：这段是理解的难点，我们更仔细的再叙述一遍。在这段中，我们定义了一个函数 sub ，这个函数一共有 3 个输入，他们都是正整数，我们记为 sub (a,b,c)) 。其中，第一个参数 a 是一个公式的哥德尔数，我们接收到 a 之后要把它解码成此哥德尔数所对应的公式。最后一个参数 c 指的是一个符号的哥德尔数，我们要找到 a 对应公式的所有哥德尔数为 c 的符号所对应的位置。最后，我们把刚才找到的位置全部替换成数字 b 。现在，我们计算这个修改后的公式的哥德尔数，这个数字就是 sub (a,b,c)。

替换构成了哥德尔证明的关键。

他考虑下面一个元数学语句 “无法证明哥德尔数为 sub (y,y,17) 的公式”。回想一下我们刚刚学到的符号，哥德尔数为 sub (y,y,17) 的公式是通过取哥德尔数为 y （某个未知量）的公式并将该变量 y 替换掉哥德尔数为 17 的符号（也是任何一个 y 的位置）。

事情变得令人迷惑，但是不管怎么说，我们的元数学语句 “无法证明哥德尔数为 sub (y,y,17) 的公式” 肯定能转化为某个特定哥德尔数所对应的公式。 我们把这个数称为 n 。

现在进行最后一轮替换：哥德尔通过将数字 n 替换先前公式中 y 的位置来创建一个新公式。他的新公式声称：“无法证明哥德尔数为 sub (n,n,17) 的公式”。我们将此新公式称为 G 。

自然， G 也有一个哥德尔数。那么它的值是什么呢？哇哦，它肯定是 sub (n,n,17) ！根据定义， sub (n,n,17) 是下面公式的哥德尔数，它是通过将哥德尔数为 n 的公式中对应哥德尔数为 17 的符号用 n 替代所得到的。而 G 正是这个公式！ 由于素数分解的唯一性，我们现在看到 G 所讨论的公式就是 G 本身。

译者注：这又是一个难点。我们更仔细的叙述如何计算 sub (n,n,17)。回忆我们前面的注，我们的第一步就是要解码 n 所对应的公式。根据前文，我们知道这对应了语句 “无法证明哥德尔数为 sub (y,y,17) 的公式”。第二步，我们要找到 17 所对应的符号，也就是 y 的所有位置，我们将找到的位置加个框：“无法证明哥德尔数为 \mathrm{sub}(\bbox[#EEF, 5px, border: 2px solid red]{y},\bbox[#EEF, 5px, border: 2px solid red]{y},17) 的公式 “。第三步，我们要把框的位置替换成 n ，也就是 “无法证明哥德尔数为 sub (n,n,17) 的公式 “，而这正是公式 G 。

G 断言自己无法被证明。

但是 G 能被证明吗？如果是的话，则意味着存在某个公式序列，可以证明哥德尔数为 sub (n,n,17) 的公式。但这恰好与 G 相反，即 G 断言不存在这样的证明。相反的语句 G 和 ∼G 在一致的公理体系中不可能同时为真。因此， G 的正确与否必然无法被判定。

然而，尽管 G 是无法被判定，它显然是对的。 G 意思是 “无法证明哥德尔数为 sub (n,n,17) 的公式”，而这正是我们所发现的事实。既然 G 是正确的，还是在此公理体系内构造的一个无法被判定的语句，说明了这个系统是不完备的。

你可能认为你可以提出一些额外的公理，使用它们证明 G 并解决悖论。但是你不能。哥德尔说明了对于增强的公理系统将允许构建新的正确的公式 G （根据与之前的方法类似），而该公式无法在新的增强系统中得到证明。在努力建立完备的数学系统时，你永远无法摆脱困境。

没有一致性的证明

我们学到了如果公理集是一致的，则它是不完备的。这是哥德尔第一不完备定理。第二定理，即没有一套公理可以证明其自身的一致性，由此易得。

如果公理集可以证明它永远不会产生矛盾，那意味着什么？这意味着存在根据这些公理构建的一系列公式，证明了这个含义为 “这组公理是一致的” 的元数学公式。由第一定理，这个公理集必然是不完备的。

但是，“公理集是不完备的” 与 “有一个无法被证明的正确的公式” 含义相同。这个语句等价于我们的公式 G 。我们知道公理不能证明 G 。

因此，哥德尔创造了一个矛盾的证明：如果公理集可以证明其自身的一致性，那么我们将能够证明 G 。但是我们不能。因此，没有一组公理可以证明其自身的一致性。

哥德尔的证明扼杀了对一个一致和完备的数学系统的追求。内格尔和纽曼在 1958 年写道，不完备性的含义 “还没有被完全理解”。直到今天仍然如此。