哥德尔的证明如何运作 (2020)

1931 年，奥地利逻辑学家库尔特·哥德尔取得了可以说是历史上最令人惊叹的智力成就之一。那个时代的数学家寻求数学的坚实基础：一组基本的数学事实或公理，既一致（永远不会导致矛盾）又完整，作为所有数学真理的基石。但哥德尔在 25 岁时发表了令人震惊的不完备性定理，粉碎了这个梦想。他证明，任何可以作为数学基础的公理都不可避免地是不完整的。总有一些关于数字的真实事实无法用这些公理来证明。他还表明，没有一组候选公理可以证明其自身的一致性。他的不完备性定理意味着不可能有一切事物的数学理论，无法统一可证明的和真实的。数学家能够证明什么取决于他们的起始假设，而不是所有答案所源自的任何基本事实。自哥德尔发现以来的 89 年里，数学家们偶然发现了他的定理所预言的那些无法回答的问题。例如，哥德尔本人帮助建立了涉及无穷大大小的连续统假设是不可判定的，停机问题也是不可判定的，该问题询问接受随机输入的计算机程序是否会永远运行或最终停止。物理学中甚至出现了无法判定的问题，这表明哥德尔的不完备性不仅影响数学，而且以某种难以理解的方式影响现实。这是哥德尔如何证明他的定理的简化、非正式的概述。哥德尔编号 哥德尔的主要策略是将公理系统的陈述映射到系统内的陈述上，即映射到有关数字的陈述上。这种映射使得公理系统能够令人信服地谈论自身。此过程的第一步是将任何可能的数学陈述或一系列陈述映射到称为哥德尔数的唯一数字。欧内斯特·内格尔 (Ernest Nagel) 和詹姆斯·纽曼 (James Newman) 在他们 1958 年出版的《哥德尔证明》一书中提出了哥德尔方案的稍微修改版本，以 12 个基本符号作为表达一组基本公理的词汇。例如，某物存在的陈述可用符号∃表示，而加法则用+表示。重要的是，符号 s 表示“的后继”，给出了一种指定数字的方法；例如，ss 0 表示 2。然后这 12 个符号被分配哥德尔数 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 等等。然后，他将每个素数提升到序列中同一位置处的公式的哥德尔数（例如，2 243,000,000 × …，如果 0 = 0 排在第一位），并将所有内容相乘。算术元数学真正的好处是，即使是关于算术公式的陈述（称为元数学陈述）本身也可以转换为具有自己的哥德尔数的公式。首先考虑公式 ~(0 = 0)，意思是“零不等于零”。这个公式显然是错误的。然而，它有一个哥德尔数：2 的 1 次方（符号 ~ 的哥德尔数），乘以 3 的 8 次方（“开括号”符号的哥德尔数），依此类推，得到 21 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 。因为我们可以为所有公式（甚至是错误的公式）生成哥德尔数，所以我们可以通过谈论它们的哥德尔数来明智地讨论这些公式