哥德尔的证明如何运作（2020）

# 哥德尔证明是如何运作的 来源：https://www.quantamagazine.org/how-godels-proof-works-20200714/ 1931年，奥地利逻辑学家库尔特·哥德尔完成了可以说是历史上最令人惊叹的智力成就之一。 那个时代的数学家们寻求数学的坚实基础：一组基本的数学事实（即公理），既要相容——永不导致矛盾——又要完备，作为所有数学真理的基石。 但哥德尔在年仅25岁时发表的令人震惊的不完备定理粉碎了这一梦想。他证明，任何可以假设为数学潜在基础的公理集合都必然是不完备的；总有关于数字的真实事实无法由这些公理证明。他还表明，任何候选公理集合都无法证明自身的一致性。 他的不完备定理意味着不可能有数学上的万有理论，不可能将可证明之物与真实之物统一起来。数学家能证明什么取决于他们的起始假设，而非从中涌出所有答案的根本基础真理。 在哥德尔发现之后的89年里，数学家们恰恰遇到了他的定理所预言的那类无法回答的问题。例如，哥德尔本人帮助确立了连续统假说（https://www.quantamagazine.org/to-settle-infinity-question-a-new-law-of-mathematics-20131126/）是不可判定的，该假说涉及无穷的大小；停机问题也是如此，它询问一个接受随机输入的计算机程序是会永远运行还是最终停止。不可判定问题甚至出现在物理学中（https://www.nature.com/news/paradox-at-the-heart-of-mathematics-makes-physics-problem-unanswerable-1.18983），这表明哥德尔式的不完备性不仅困扰着数学，而且——以某种尚未被充分理解的方式——也困扰着现实。 以下是哥德尔如何证明其定理的简化、非正式概述。 ## 哥德尔编号 哥德尔的主要策略是将关于一个公理系统的陈述映射到该系统内的陈述——即映射到关于数字的陈述。这种映射使公理系统能够清晰地谈论自身。 这个过程的第一步是将任何可能的数学陈述或一系列陈述映射到一个唯一的数字，称为哥德尔数。 欧内斯特·内格尔和詹姆斯·纽曼在他们1958年的著作《哥德尔证明》中提出的哥德尔方案略作修改的版本，始于12个基本符号，这些符号充当表达一组基本公理的词汇。例如，某物存在的陈述可以用符号∃表示，而加法用+表示。重要的是，表示“后继”的符号*s*提供了一种指定数字的方式；例如，*ss*0指2。 然后这十二个符号被赋予哥德尔数1到12。 | **常项符号** | **哥德尔数** | **通常含义** | |---|---|---| | ~ | 1 | 并非 | | ∨ | 2 | 或 | | ⊃ | 3 | 如果...那么... | | ∃ | 4 | 存在一个... | | = | 5 | 等于 | | 0 | 6 | 零 | | s | 7 | 的后继 | | ( | 8 | 标点符号 | | ) | 9 | 标点符号 | | , | 10 | 标点符号 | | + | 11 | 加 | | × | 12 | 乘 | 接下来，表示变量的字母，从*x*、*y*和*z*开始，映射到大于12的素数（即13、17、19、...）。 然后，这些符号和变量的任何组合——即任何可以构造的算术公式或公式序列——都有其自己的哥德尔数。 例如，考虑0 = 0。这个公式的三个符号对应哥德尔数6、5和6。哥德尔需要将这个三数序列变成一个唯一的数字——一个由任何其他符号序列都无法产生的数字。为此，他取前三个素数（2、3和5），将每个素数提升为序列中相同位置符号的哥德尔数次方，然后将它们相乘。因此0 = 0变成2^6 × 3^5 × 5^6，即243,000,000。 这种映射之所以有效，是因为永远不会有任何两个公式最终得到相同的哥德尔数。哥德尔数是整数，而整数只能以唯一方式分解为素数。因此243,000,000的唯一素因数分解是2^6 × 3^5 × 5^6，这意味着只有一种可能的方式解码该哥德尔数：即公式0 = 0。 哥德尔随后更进一步。一个数学证明由一系列公式组成。因此哥德尔也给每个公式序列赋予一个唯一的哥德尔数。在这种情况下，他像之前一样从素数列表开始——2、3、5等等。然后，他将每个素数提升为序列中相同位置公式的哥德尔数次方（例如，如果0 = 0排在第一位，则为2^243,000,000 × ...），并将所有结果相乘。 ## 元数学的算术化 真正的好处在于，甚至关于算术公式的陈述（称为元数学陈述）本身也可以被翻译成具有自己哥德尔数的公式。 首先考虑公式~(0 = 0)，意思是“零不等于零”。这个公式显然为假。尽管如此，它有一个哥德尔数：2的1次方（符号~的哥德尔数），乘以3的8次方（“左括号”符号的哥德尔数），以此类推，得到2^1 × 3^8 × 5^6 × 7^5 × 11^6 × 13^9。 因为我们可以为所有公式生成哥德尔数，即使是假的公式