一阶皮亚诺算术

自然数——0, 1, 2 等等——是数学的基石，然而其直观上的简单性却掩盖了深刻的哲学和逻辑挑战。我们如何在一个有限、严谨的形式系统中捕捉无限的数世界及其性质？这一追求并非纯粹的学术探讨，它探究了可被形式化、可计算和可证明之物的极限。本文通过探索为此目的而设计的基石性公理系统——一阶皮亚诺算术 (PA)——来解决这个根本问题。在接下来的章节中，我们将首先从头开始构建这个系统，详细介绍其语言、公理和强大的归纳原理。然后，我们将揭示这种形式化带来的惊人后果，从它作为通用计算模型的角色，到由 Gödel、Tarski 和奇异的“非标准”世界的存在所揭示的深刻局限。我们的旅程从定义构成皮亚诺算术的精确原理和机制开始。

好了，我们已经搭好了舞台。我们想在一个形式系统中捕捉数的本质。但要怎么做呢？你不能只在数学专著中写下“数是用来计数的东西”。我们需要更精确，就像钟表匠组装一块精致的钟表。我们需要从头开始，用明确定义的组件和规则来构建我们的算术理论。这段旅程将带领我们从简单的计数行为走向理性本身的深刻极限。

首先，如果我们要讨论数，我们需要一种语言。不是英语或中文，而是一种纯逻辑的语言，剥离了所有歧义。我们称之为 $L_{PA}$，即皮亚诺算术的语言。这种语言中的词汇是什么？它出奇地简单。我们只需要几个特殊符号就可以开始。

首先，我们需要一个起点。我们将有一个表示特定数字的符号：$0$。这是我们的锚点，是通往无限数字阶梯的第一步。

接下来，我们需要一种从一个数到下一个数的方法。为此，我们有一个“后继”机器，一个我们称之为 $S$ 的函数。如果你给 $S$ 一个数，它会吐出紧接着的下一个数。所以，$S(0)$ 是我们语言中表示“一”的方式。$S(S(0))$ 是表示“二”的方式，依此类推。对于任何自然数 $n$，我们可以用一个我们称之为​​数符​​的项 $\overline{n}$ 来表示它，这只是将符号 $S$ 应用于 $0$ 恰好 $n$ 次。

最后，我们想做算术！我们引入另外两个函数符号：$+$ 表示加法，$\cdot$ 表示乘法。它们就像小工厂。$+$ 工厂接收两个数并给出它们的和。$\cdot$ 工厂接收两个数并给出它们的积。

就是这样！我们整个算术语言由这四个非逻辑符号——$0, S, +, \cdot$——以及变量（如 $x, y, z$）、等号 $=$、标准的逻辑联结词（“与”、“或”、“非”、“如果……那么”）和量词（“对于所有” $\forall$，“存在” $\exists$）构成。有了这些简单的工具，我们可以构造像 $(S(S(0)) \cdot S(0)) + S(S(S(0)))$ 这样的项，这是书写 $(2 \cdot 1) + 3$ 的形式化方式。

在赋予语法之前，语言只是一堆符号——语法是告诉我们哪些陈述为真的规则。这些规则就是我们的​​公理​​。对于皮亚诺算术 (PA)，我们需要几条我们相信对于日常使用的数字来说是不证自明的公理。

我们从后继机器 $S$ 的一些基本性质开始：

1. ​​零是起点：​​ 没有数在零之前。在我们的形式语言中，这意味着 $0$ 不是任何数的后继：$\forall x (S(x) \neq 0)$。
2. ​​没有两个不同的数会得到相同的后继：​​ 如果 $x$ 的后继与 $y$ 的后继相同，那么 $x$ 和 $y$ 本身必须是同一个数。形式化地，$\forall x \forall y (S(x) = S(y) \rightarrow x=y)$。

这两条简单的规则确保了我们的数构成一个从 $0$ 开始、没有循环或分支的清晰的无限序列。

接下来，我们必须教会我们的系统加法和乘法实际上做什么。我们不能假设它知道。我们必须定义它们。我们使用一种称为递归的非常优雅的方法来做到这一点。我们为 $0$ 定义这些运算，然后展示如何使用后继函数 $S$ 将定义扩展到下一个数。

对于加法：

1. 任何数加零都保持不变：$\forall x (x + 0 = x)$。
2. 将 $y$ 的后继加到 $x$ 上，与取 $(x+y)$ 的后继是相同的：$\forall x \forall y (x + S(y) = S(x+y))$。例如，$7 + (5+1)$ 与 $(7+5)+1$ 相同。

对于乘法：

1. 任何数乘以零都得零：$\forall x (x \cdot 0 = 0)$。
2. 将 $x$ 乘以 $y$ 的后继，与计算 $(x \cdot y)$ 然后将 $x$ 加到结果上是相同的：$\forall x \forall y (x \cdot S(y) = (x \cdot y) + x)$。例如，$7 \cdot (5+1)$ 与 $(7 \cdot 5) + 7$ 相同。

有了这些公理，我们为我们的形式系统定义了算术的基本运算。我们给了它游戏的基本规则。但要做任何真正有趣的事情，我们还需要最后一块，也是我们武器库中最强大的工具。

我们如何证明一个性质对所有自然数都成立？我们不能一个一个地检查，因为它们有无限多个。我们需要一个更聪明的原理。你可能以前见过它：就像一排多米诺骨牌。如果你能证明……

1. 第一块多米诺骨牌倒下（性质对 $0$ 成立），并且
2. 如果任何一块多米诺骨牌倒下，它将推倒下一块（如果性质对一个数 $x$ 成立，它也必须对其后继 $S(x)$ 成立）， ……那么你就可以确定所有的多米诺骨牌都会倒下。

这就是数学归纳法原理。我们如何将这个强大的思想放入我们的一阶语言中？这里我们遇到了一个微妙而深刻的问题。在理想世界中，我们会有一条单一的公理说：“对于任何性质 $P$，如果 $P(0)$ 为真且 $\forall x (P(x) \rightarrow P(S(x)))$ 为真，那么 $\forall x P(x)$ 为真。”

但在我们的一阶语言中，我们没有办法说“对于任何性质”。像 $x$ 和 $y$ 这样的变量代表数，而不是抽象的性质。这是“一阶”的关键限制。所以，我们必须稍微变通一下。我们引入一个​​公理模式​​。它不是一条公理，而是一个用于生成公理的无限配方。该模式说：对于任何你可以在我们的语言 $L_{PA}$ 中写出的公式 $\varphi(x)$，以下都是一条公理： $(\varphi(0) \land \forall x(\varphi(x) \rightarrow \varphi(S(x)))) \rightarrow \forall x \varphi(x)$ 这意味着我们的多米诺骨牌原理适用于任何我们可以用公式表达的性质。这个模式是 PA 的引擎，允许我们从有限的基本公理集合中证明无限多的事实。

你可能会想，这个多米诺骨牌原理只是我们决定添加的一条任意规则吗？或者它对于我们所熟知的数来说是真实的，有更深层的原因吗？原因很美妙。在集合论的语言中，自然数 $\mathbb{N}$ 可以被构造为包含 $0$ 并且在后继运算下“闭合”的最小集合。现在，考虑一个满足归纳条件的性质 $\varphi(x)$。$\varphi(x)$ 为真的数的集合必须包含 $0$ 并且在后继运算下是闭合的。但由于 $\mathbb{N}$ 是最小的这样的集合，这个数的集合必须是整个 $\mathbb{N}$！。所以，归纳模式不仅仅是一个方便的规则；它反映了自然数是什么的本质。

有了我们的语言和公理，我们就创建了皮亚诺算术。我们试图描述的结构是我们在学校里都学过的那个：自然数集合 $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ 以及我们熟悉的后继、加法和乘法运算。我们称之为算术的​​标准模型​​。

现在是价值百万美元的问题：我们成功了吗？我们的公理是否完美地确定了标准模型，而没有其他可能？看起来应该是这样。它们显然都是关于 $\mathbb{N}$ 的真命题。但在这里，逻辑为我们准备了一个惊人的意外。答案是否定的。

PA 的公理，尽管强大，却容许其他奇异的模型，这些模型与我们所知的自然数完全不同。这些被称为​​非标准模型​​。它们存在性的证明是一个叫做​​紧致性定理​​的工具最优雅的应用之一。想象一下，我们在语言中添加一个新的常量符号，称之为 $c$。然后我们添加一个新的、无限的公理列表：

• $c \neq \overline{0}$
• $c \neq \overline{1}$
• $c \neq \overline{2}$
• ……依此类推，对于每一个数符 $\overline{n}$。

我们要求 $c$ 是一个不等于任何标准自然数的数。这会产生矛盾吗？紧致性定理告诉我们，只要一个理论的每个有限部分都有模型，那么整个理论就有模型。所以，让我们取这些新公理的任何一个有限列表，比如说直到 $c \neq \overline{N}$。我们能为 PA 加上这个有限列表找到一个模型吗？当然可以！我们只需使用标准模型 $\mathbb{N}$，并决定我们的新符号 $c$ 就表示数 $N+1$。在这个解释中，所有 PA 的公理都是真的，我们所有有限的要求，如“$c$ 不是 5”或“$c$ 不是 100”也都是真的。

既然我们新理论的每一个有限部分都是一致的，紧致性定理保证了整个无限理论也必须有一个模型！这个模型是 PA 的一个模型，但它包含一个元素 $c$，根据定义，它不等于任何标准自然数。这个 $c$ 是一个“非标准”数。这个模型包含一个标准自然数的副本，但它也包含其他“超越无穷”的元素。这些奇异世界的存在是我们的归纳原理是一个一阶模式，而不是一个单一、全能的二阶公理的直接后果。该模式留下了漏洞，而这些非标准数就是从裂缝中溜进去的。PA 不是​​范畴的​​；它不能唯一地描述一个结构。

起初，这些非标准模型可能看起来像一个奇异的缺陷，是我们逻辑系统的失败。但在科学中，失败往往是最有趣的部分——它们教会我们新的东西。这些奇异数学宇宙的存在对于我们能知道什么和能证明什么具有深远的启示。

请记住，一个陈述能从 PA 的公理中被证明，当且仅当它在 PA 的每一个模型中都为真。这是由一阶逻辑的可靠性定理和完备性定理保证的。现在，想象一个陈述，它对于我们的标准数 $\mathbb{N}$ 碰巧是真的，但在某个奇异的非标准模型中是假的。我们能对它说些什么呢？因为它并非在 PA 的所有模型中都为真，所以它不可能从 PA 的公理中被证明！。这些非标准模型为我们提供了一个强大的工具，来证明某些真理实际上是不可证明的。

这直接将我们引向了 Kurt Gödel 和他著名的​​不完备性定理​​。Gödel 所展示的是，对于任何像 PA 这样一致且强大到足以进行基本算术的形式系统，总会存在一些在标准模型中为真但在该系统内部不可证明的陈述。PA 是不完备的。它无法捕捉所有关于自然数的真理。

最后的、令人谦卑的结论也许是最著名的。考虑陈述“皮亚诺算术是一致的”（我们可以将其写成一个复杂的公式，$\operatorname{Con}(PA)$）。我们当然相信这是真的。实际上，在一个更强大的理论，如策梅洛-弗兰克尔集合论 (ZFC) 中，我们可以构造标准模型 $\mathbb{N}$ 并验证它满足所有 PA 的公理。既然 PA 有模型，它必然是一致的，并且 ZFC 可以形式化地证明这一点：$\mathrm{ZFC} \vdash \operatorname{Con}(PA)$。但 Gödel 的第二不完备性定理表明，PA 本身，如果它是一致的，就无法证明自身的一致性。一个系统不能用它自己的规则来为其自身的可靠性提供绝对的保证。

我们试图为算术建立一个完美、完备且能自我验证的系统的努力，最终引导我们发现了一个关于形式推理本身局限性的根本性发现。我们出发去捕捉简单的数字真理，最终却凝视着不可证明的深渊。简而言之，这就是数理逻辑经久不衰的美丽与力量。

我们花了一些时间来铺设皮亚诺算术的公理，就像一个孩子小心翼翼地摆放一排多米诺骨牌。我们定义了语言、游戏规则和归纳原理。乍一看，这似乎是一项相当枯燥的工作——对我们在小学学到的东西：计数、加法和乘法进行形式化描述。但现在，我们准备推倒第一块骨牌并观察。我们将看到的不是一个简单的线性级联，而是一个爆炸性的、分支的连锁反应，它撕裂了数学、计算机科学和哲学的基础。事实证明，研究这些简单的公理，就是研究思想本身的极限。

最早的惊人发现之一是，皮亚诺算术（PA）不仅仅是关于数，它还关乎计算。任何你可以描述为清晰、逐步的机械过程——我们称之为算法——都可以在 PA 的语言中被反映和模拟。

想一个简单的计算机程序。它接收输入，遵循一系列操作，然后产生输出。我们可以在 PA 中做同样的事情。对于一大类被称为“原始递归函数”的可计算函数（这涵盖了你可能想到的绝大多数算法），我们可以在算术语言中构造一个公式，完美地表示该函数的图形。这个公式，我们称之为 $\varphi_f(\vec{x}, y)$，充当了陈述“$y$ 是在输入 $\vec{x}$ 上计算函数 $f$ 的结果”的逻辑替身。这不仅仅是一个松散的类比。PA 足够强大，可以证明对于任何输入 $\vec{x}$，都存在一个唯一的输出 $y$ 满足该公式。

这从函数扩展到了性质，或关系。考虑关系“$x$ 整除 $y$”。我们可以定义它的特征函数，如果关系成立则输出 $1$，不成立则输出 $0$。这个函数是原始递归的，因此，整除性这个性质可以被 PA 中的一个公式完美地捕捉。实现这一点的公式 $\exists z \le y (x \cdot z = y)$ 非常简单。它陈述了“$x$ 整除 $y$”为真，如果你能找到一个数 $z$（不大于 $y$），使得 $x$ 乘以 $z$ 等于 $y$。我们只需要搜索到 $y$（一个有界量词）这一事实是这个性质对于 PA 来说如此直观易处理的关键原因。

是什么赋予了 PA 这种非凡的力量？秘密成分是它成熟的归纳公理模式。存在较弱的算术系统，但 PA 的归纳适用于其语言中任何可定义的性质，无论多么复杂。这使得 PA 能够证明那些其定义本身就涉及搜索事物，或断言“存在”某个对象（如计算的代码）的函数是全函数。

这一力量的最终证明是著名的阿克曼函数。它是一个全可计算函数，但它增长得如此惊人地快，以至于它不是原始递归的——它超过了任何可通过简单嵌套循环定义的函数。你无法在不使用可增长堆栈的情况下编写一个“for”循环来计算它。然而，通过使用巧妙的嵌套归纳——归纳中的归纳——PA 可以证明阿克曼函数是全函数，即它对于任何一对自然数总是会停机并给出一个值。在某种意义上，PA 是一个用逻辑的朴素语言表达的强大的“通用计算机”。

在惊叹于 PA 容纳计算世界的力量之后，我们自然会问：它的极限是什么？它能捕捉一切吗？在这里，故事发生了戏剧性的转折。对 PA 边界的探索引出了现代逻辑中一些最深刻的结果。

​​真理问题​​

让我们从一个听起来简单的问题开始：PA 能定义自己的真理概念吗？也就是说，我们能否写出一个公式，称之为 $T(x)$，当且仅当 $x$ 是一个真算术句子的哥德尔数（编码）时，该公式为真？

一瞬间，这似乎是可能的。如果我们将自己限制在语言的一个非常简单的部分——所谓的 $\Delta_0$ 公式，其中所有量词都是有界的（例如，“对于所有 $x \lt 100$……”）——那么答案是肯定的！我们可以写出一个公式 $T_{\Delta_0}(x)$，它能完美地检验任何 $\Delta_0$ 句子的真伪。它之所以能工作，是因为检验这样一个句子从不需要无限的搜索；我们只需检查有限数量的情况。

但这是一个虚假的曙光。一旦我们允许在语言中使用无界量词（“对于所有 $x$……”），整个项目就崩溃了。Alfred Tarski 证明，对于任何足够丰富以至于可以谈论其自身语法的语言（如 PA 的语言），该语言的真理谓词在该语言内部是不可定义的。证明是对古老的说谎者悖论的精彩形式化。通过一个称为对角线引理的优美工具，人们可以构造一个句子 $\lambda$，它实际上在说：“这个句子不是真的”，或者更形式化地，$\lambda \leftrightarrow \neg T(\ulcorner \lambda \urcorner)$。如果存在这样一个真理谓词 $T(x)$，那么这个句子将当且仅当它为假时为真——这是一个逻辑上的不可能。结论是不可避免的：算术中真理的语义概念是一个更丰富、更高层次的概念，无法在算术内部被完全捕捉。我们必须始终走出系统才能谈论它的真理。

​​证明问题​​

所以我们无法定义真理。但也许我们仍然可以证明所有真命题？这是希尔伯特纲领的核心支柱之一：为所有数学找到一套完备且一致的公理。哥德尔第一不完备性定理粉碎了这个梦想。

在这里，区分两种“完备性”至关重要。我们使用的底层逻辑系统，即一阶逻辑，确实以其自己的方式是完备的：哥德尔的*完备性定理说，任何逻辑上有效（在所有可能的世界中都为真）的句子都是可证明的。但是，任何用该逻辑写出的特定的、足够强大的公理理论*，如 PA，都注定是不完备的。Gödel 表明，只要 PA 是一致的，就会存在一些在自然数的标准模型中为真，但 PA 永远无法证明的句子。

很长一段时间里，这些“不可判定”的句子似乎是人为的、自我指涉的悖论。但在 1977 年，Jeff Paris 和 Leo Harrington 发现了一个“自然的”不可判定陈述。Paris–Harrington 原理是组合学中一个著名结果——有限拉姆齐定理的一个小变体。这是一个关于给数集着色的陈述，并且可以被证明是真的。然而，PA 无法证明它。为什么？原因更为深刻。事实证明，Paris–Harrington 原理本身足够强大，可以蕴含 PA 的一致性。而根据哥德尔第二不完备性定理，任何足够强大且一致的理论都无法证明自身的一致性。系统无法从其自身资源内部为自己的健全性作担保。

PA 的不完备性还有另一个奇异而美妙的后果。如果公理没有确定所有关于自然数的真理，它们至少确定了自然数的世界吗？这些公理是否强制了一个唯一的结构？答案是响亮的“不”。

因为 PA 是一个一阶理论，它受到模型论中强大的 Löwenheim–Skolem 定理和紧致性定理的约束。这些定理意味着，如果 PA 有其预期的模型（$\mathbb{N}$），它也必须有其他与其不同构的“非标准”模型。存在一些奇异的宇宙，它们满足 PA 的每一条公理，但却包含“无限”数——比任何标准整数 $0, 1, 2, \dots$ 都大的数。

在这些非标准模型中，我们熟知的标准数构成了一个完美的 $\mathbb{N}$ 的初始副本。但这个副本并没有穷尽整个模型。还存在其他“超越无穷”的数。这怎么可能呢，既然我们有归纳公理？归纳法告诉我们，任何对 $0$ 成立且从任何数传递到其后继的性质，都必须对所有数成立。但这里的关键是：一阶 PA 的归纳模式只适用于可由 PA 语言中的公式定义的性质。标准数的集合，虽然从我们外部的视角来看是一个完全合法的集合，但在模型内部是不可定义的。它是一个“外部”性质。因此，归纳法 просто从它上面飞过，无法“看到”它并得出结论说它就是整个模型。

这种现象代表了一阶逻辑的深刻局限，也是 Hilbert 追求一个范畴的形式化——一个描述唯一一个数学结构的系统——梦想的失败。实际上，我们可以通过转向一个更强大的框架，即二阶逻辑，来为算术实现范畴性。但这一举动付出了可怕的代价。在二阶逻辑中，我们失去了演绎系统本身的完备性。我们牺牲了一个通用的、机械化的证明检查程序，而这正是 Hilbert 最珍视的另一个目标。我们面临一个根本性的权衡：我们可以拥有一个唯一的预期模型，或者我们可以拥有一个完备的证明系统，但我们不能两者兼得。

穿越皮亚诺算术的旅程是科学事业的一个完美寓言。我们从一个熟悉世界的简单、不证自明的规则开始。我们发现它们具有意想不到的力量，使我们能够模拟广阔的计算领域。但当我们推向边界时，我们发现我们的系统并非我们所希望的万能钥匙。它是不完备的，无法捕捉所有真理，甚至无法证明自身的一致性。它甚至无法描述一个单一、明确的现实。

但这些不是失败。它们是最深刻的发现。它们教会我们，真理是一个比证明更难以捉摸的概念，语义将永远超越语法，而我们的形式系统，无论多么强大，都是它们试图描述的数学现实的不完美镜像。一个旨在形式化简单计数行为的系统，竟能引导我们触及这些深刻哲学问题的核心，这一事实本身就是数学那令人难以置信的、相互关联的美的明证。