皮亚诺公理（综述）

                     

贡献者： 待更新

　　 本文根据 CC-BY-SA 协议转载翻译自维基百科 相关文章。

　　 在数学逻辑中，皮亚诺公理（Peano axioms，/piˈɑːnoʊ/，[peˈaːno]），也称为德德金–皮亚诺公理或皮亚诺假设，是一组用于描述自然数的公理体系，由 19 世纪意大利数学家朱塞佩·皮亚诺提出。这些公理在多项元数学研究中几乎未加改动地被广泛采用，其中包括关于数论是否一致与完备等基本问题的研究。

　　 由皮亚诺公理所提供的算术公理化体系，通常被称为皮亚诺算术。

　　 将算术进行形式化的重要性，在赫尔曼·格拉斯曼的工作之前并未被广泛重视。格拉斯曼在 19 世纪 60 年代指出，算术中的许多事实可以从关于后继运算和数学归纳的更基本事实中推导出来。1881 年，查尔斯·桑德斯·皮尔士提出了一种自然数算术的公理化体系。1888 年，理查德·德德金又提出了另一种自然数的公理体系，而皮亚诺则在 1889 年出版的著作《以新方法阐述的算术原理》（拉丁文：Arithmetices principia, nova methodo exposita）中，将其加以简化并作为一组公理发表。

　　 皮亚诺公理共包括三类陈述：1. 第一条公理断言自然数集合中至少存在一个元素；2. 接下来的四条是关于等号的一般性陈述，在现代的处理方式中，这些往往被看作是 “基础逻辑” 的一部分，而非皮亚诺公理本身；3. 再接下来的三条公理是关于自然数及其后继运算的基本性质的一阶逻辑陈述；4. 第九条、也是最后一条公理则是一个二阶逻辑陈述，它表达了对自然数进行数学归纳法的原理，正是这一点使得原始皮亚诺公理体系接近二阶算术。如果显式引入加法和乘法两个运算符号，并将第九条二阶归纳公理替换为一阶公理模式，就可以得到一个较弱的一阶系统。术语 “皮亚诺算术” 有时特指这一限制后的系统。

1. 历史上的二阶表述

　　 当皮亚诺提出他的公理时，数理逻辑的语言还处于起步阶段。他为了表达这些公理而创造的逻辑符号体系并未广泛流行，尽管它成为现代集合成员关系符号（∈，源自皮亚诺的 ε）的起点。皮亚诺明确区分数学符号和逻辑符号，这在当时的数学中还不常见；这种区分最早由哥特洛布·弗雷格在其 1879 年出版的《概念文字》中引入。\(^\text{[7]}\) 然而，皮亚诺并不知道弗雷格的工作，而是独立地基于布尔和施罗德的研究重建了自己的逻辑体系。\(^\text{[8]}\)

　　 皮亚诺公理定义了自然数的算术性质，通常表示为集合 $N$ 或 $\mathbb{N}$。这些公理中的非逻辑符号包括一个常数符号 0 和一个一元函数符号 S（表示 “后继”）。

　　 第一条公理声明常数 0 是一个自然数：

　　 1.0 是一个自然数。

　　 皮亚诺最初在其公理表述中使用 1 而非 0 作为 “第一个” 自然数，\(^\text{[9]}\) 而他在《数学公式集》中的公理则包括了零。\(^\text{[10]}\)

　　 接下来的四条公理描述了等同性关系。由于这些内容在带有等号的一阶逻辑中是逻辑有效的，因此在现代的数学处理中，它们通常不被视为 “皮亚诺公理” 的一部分。\(^\text{[8]}\)

1.对于每一个自然数 $x$，有 $x = x$。即：等同性是自反的。
2.对于所有自然数 $x$ 和 $y$，如果 $x = y$，那么 $y = x$。即：等同性是对称的。
3.对于所有自然数 $x$、$y$ 和 $z$，如果 $x = y$ 且 $y = z$，那么 $x = z$。即：等同性是传递的。
4.对于所有 $a$ 和 $b$，如果 $b$ 是自然数并且 $a = b$，那么 $a$ 也是自然数。即：自然数在等同性下是封闭的。

　　 其余的公理定义了自然数的算术性质。假设自然数在一个单值 “后继” 函数 $S$ 下是封闭的：

5.对于每一个自然数 $n$，$S(n)$ 也是自然数。即：自然数在后继函数 $S$ 下是封闭的。
6.对于所有自然数 $m$ 和 $n$，如果 $S(m) = S(n)$，那么 $m = n$。即：$S$ 是一个单射（注入函数）。
7.对于每一个自然数 $n$，命题 $S(n) = 0$ 是假的。即：不存在一个自然数，其后继是 0。

图
图 1：右图中从最近的一块开始的一连串浅色多米诺骨牌，可以用来表示自然数集合 $\mathbb{N}$。\(^\text{[1][11][12]}\) 然而，公理 1–8 同样也被“所有多米诺骨牌的集合”（无论是浅色还是深色）所满足。\(^\text{[2]}\) 第九条公理（归纳公理）将 $\mathbb{N}$ 限定为那一串浅色骨牌（即“无赘物”原则），因为只有浅色骨牌会在最前一块被推倒时依次倒下。\(^\text{[13]}\) 指用继承关系（S）一块一块地排列这些骨牌。指如果不加第九公理，也可能包含不属于自然数的“赘余元素”。

　　 公理 1、6、7 和 8 定义了自然数直观概念的一种一元表示方式：数字 1 可以被定义为 $S(0)$，2 为 $S(S(0))$，以此类推。然而，如果将自然数的概念完全建立在这些公理之上，则公理 1、6、7、8 并不蕴含后继函数能够生成所有非零的自然数。

　　 我们直观上认为每一个自然数都可以通过对 0 反复应用后继函数而得到，这一想法需要额外添加一条公理来保证，这条额外的公理通常被称为归纳公理。

　　 9.如果 $K$ 是一个集合，满足以下条件：

　　 那么 $K$ 包含所有的自然数。

　　 归纳公理有时也以如下形式表述：

　　 9.如果 $\varphi$ 是一个一元谓词，满足：

　　 那么对于每一个自然数 $n$，$\varphi(n)$ 都为真。

　　 在皮亚诺的最初表述中，归纳公理是一个二阶公理。而现在通常用一个较弱的一阶归纳公理模式来替代这个二阶原理。二阶与一阶的表述之间存在重要区别，这些区别将在下文《皮亚诺算术作为一阶理论》部分中进一步讨论。

定义算术运算与关系

　　 如果使用二阶归纳公理，那么可以直接利用皮亚诺公理在自然数集合 $\mathbb{N}$ 上定义加法、乘法以及全序（线性序）关系。然而，在使用一阶归纳的情况下，这种定义是不可行的，因此加法和乘法通常被作为额外的公理加入。这些运算和关系的对应函数通常在集合论或二阶逻辑中构造，并且可以借助皮亚诺公理证明它们的唯一性。

　　 加法

　　 加法是一个函数，它将两个自然数（即 $\mathbb{N}$ 中的两个元素）映射为另一个自然数。它的定义是递归式的： $$ \begin{aligned} a + 0 &= a, \quad \text{(1)} \\ a + S(b) &= S(a + b). \quad \text{(2)} \end{aligned}~ $$

图
图 2

　　 为了证明加法的交换律，首先通过对 $b$ 的数学归纳法证明：$0 + b = b \quad \text{和} \quad S(a) + b = S(a + b)$ 接着使用这两个结果，再通过对 $b$ 的归纳法证明：$a + b = b + a$ 因此，结构 $(\mathbb{N}, +)$ 构成一个以 0 为单位元的交换幺半群（commutative monoid）。$(\mathbb{N}, +)$ 同时也是一个可消去 magma，因此它可以嵌入一个群中。嵌入 $\mathbb{N}$ 的最小群是整数集 $\mathbb{Z}$。

　　 乘法

　　 类似地，乘法是一个将两个自然数映射为另一个自然数的函数。在加法已定义的前提下，乘法被递归地定义为：

　　 $a \cdot 0 = 0$

　　 $a \cdot S(b) = a + (a \cdot b)$

　　 显然，$S(0)$（即 1）是乘法的右单位元： $$ a \cdot S(0) = a + (a \cdot 0) = a + 0 = a~ $$ 要证明 $S(0)$ 也是**乘法的左单位元**，则需要使用数学归纳公理，因为乘法是以这种方式定义的：

　　 因此，根据归纳公理，$S(0)$ 是所有自然数的乘法左单位元。此外，可以进一步证明，乘法满足交换律和对加法的分配律： $$ a \cdot (b + c) = (a \cdot b) + (a \cdot c)~ $$ 因此，$(\mathbb{N}, +, 0, \cdot, S(0))$ 构成一个交换半环。

　　 不等式

　　 在自然数集合中，通常的全序关系 ≤ 可以如下定义（假设 0 是自然数）：

　　 对所有 $a, b \in \mathbb{N}$，当且仅当存在某个 $c \in \mathbb{N}$ 使得 $a + c = b$，我们称 $a \leq b$。

　　 该关系在加法和乘法下是稳定的：对所有 $a, b, c \in \mathbb{N}$，如果 $a \leq b$，则有：

　　 因此，结构 $(\mathbb{N}, +, \cdot, 1, 0, \leq)$ 构成一个有序半环；并且由于在 0 和 1 之间不存在其他自然数，它是一个离散有序半环。

　　 归纳公理有时也可以用如下形式表述，这种形式使用了更强的假设，并借助了 “≤” 这个序关系：

　　 对于任意谓词 $\varphi$，如果满足：

　　 这种归纳公理的形式被称为强归纳法，它是标准归纳形式的一个推论，但在涉及 “≤” 这个序关系的推理中通常更为合适。例如，若要证明自然数集合是良序的（即：自然数的任意非空子集都有最小元素），可以如下推理：

　　 设 $X \subseteq \mathbb{N}$ 是一个非空集合，且假设 $X$ 没有最小元素。

　　 因此，根据强归纳原理，对所有 $n \in \mathbb{N}$ 都有 $n \notin X$，也即 $X \cap \mathbb{N} = \varnothing$，这与 $X$ 是自然数的非空子集矛盾。所以，$X$ 必然有最小元素。

模型

　　 皮亚诺公理的一个模型是一个三元组 $(N, 0, S)$，其中：$N$ 是一个（必然是无限的）集合，$0 \in N$，$S: N \to N$ 是一个函数，满足上述公理。德德金（Dedekind）在他 1888 年的著作《数的本质与意义》（德文原名 Was sind und was sollen die Zahlen?，意即 “数是什么，它们有何用？”）中证明：任何两个满足皮亚诺公理（包括二阶归纳公理）的模型都是同构的。具体来说，设有两个皮亚诺模型 $(N_A, 0_A, S_A)$ 和 $(N_B, 0_B, S_B)$，则存在一个唯一的同态映射 $f: N_A \to N_B$，满足： $$ \begin{aligned} f(0_A) &= 0_B \\ f(S_A(n)) &= S_B(f(n)) \end{aligned}~ $$ 并且这个映射是双射（即一一对应）。这意味着：二阶皮亚诺公理是范畴性的，即它的模型在结构上是唯一的（同构的）。（而下面将提到的任何一阶形式的皮亚诺公理，则不具备这一特性。）

　　 集合论模型

　　 皮亚诺公理可以从集合论对自然数的构造以及集合论公理（如 ZF 公理）中导出。\(^\text{[15]}\) 标准的自然数构造方式由约翰·冯·诺依曼提出，其出发点是将 0 定义为空集** $\emptyset$，并引入一个集合上的运算符 $s$，定义如下： $$ s(a) = a \cup \{a\}~ $$ 自然数集 $\mathbf{N}$ 被定义为：所有包含空集且在 $s$ 运算下封闭的集合的交集。在这个定义下，每一个自然数（作为集合）等于所有比它小的自然数的集合： $$ \begin{aligned} 0 &= \emptyset \\ 1 &= s(0) = s(\emptyset) = \emptyset \cup \{\emptyset\} = \{\emptyset\} = \{0\} \\ 2 &= s(1) = s(\{0\}) = \{0\} \cup \{\{0\}\} = \{0, \{0\}\} = \{0, 1\} \\ 3 &= s(2) = s(\{0,1\}) = \{0,1\} \cup \{\{0,1\}\} = \{0,1,\{0,1\}\} = \{0,1,2\} \end{aligned}~ $$ 以此类推。由集合 $\mathbf{N}$、元素 $0$、以及后继函数 $s: \mathbf{N} \to \mathbf{N}$ 构成的结构满足皮亚诺公理。

　　 皮亚诺算术与几个较弱的集合论系统是相同一致性强度的。\(^\text{[16]}\) 其中一种系统是在 ZFC 公理体系中将 “无穷公理” 替换为其否定。另一种系统由 “通用集合论”（包括外延性、公设空集的存在、以及附加公理）构成，并增加了一个公理模式：如果某性质对空集成立，且对所有 “附加” 结构都成立，那么它就对所有集合成立。

　　 范畴论中的解释

　　 皮亚诺公理也可以通过范畴论来理解。设 $\mathcal{C}$ 是一个具有终对象 $1_\mathcal{C}$ 的范畴，定义带基点的一元系统范畴 $\mathsf{US}_1(\mathcal{C})$ 如下：

　　 若 $\mathsf{US}_1(\mathcal{C})$ 存在一个初始对象，则称范畴 $\mathcal{C}$ 满足 Dedekind–Peano 公理。这个初始对象称为 $\mathcal{C}$ 中的一个自然数对象。如果 $(N, 0, S)$ 是该初始对象，而 $(X, 0_X, S_X)$ 是任意一个其他对象，则存在唯一的态射 $u : (N, 0, S) \to (X, 0_X, S_X)$，使得： $$ \begin{aligned} u(0) &= 0_X \\ u(Sx) &= S_X(u(x)) \end{aligned}~ $$ 这正是对 $0_X$ 和 $S_X$ 的递归定义。

一致性

　　 当皮亚诺公理最初被提出时，伯特兰·罗素等人认为这些公理隐含地定义了 “自然数” 这一概念。\(^\text{[17]}\) 但亨利·庞加莱则更加谨慎，他指出：只有当这些公理是一致的时，它们才能定义自然数；如果能够从这些公理出发推导出诸如 $0 = 1$ 这样的矛盾，那么这些公理就是不一致的，也就什么都无法定义。\(^\text{[18]}\)1900 年，大卫·希尔伯特将 “使用仅限有限方法证明皮亚诺公理的一致性” 列为他著名的 23 个问题中的第二个问题。\(^\text{[19]}\)1931 年，库尔特·哥德尔证明了他著名的第二不完备性定理，该定理指出：如果皮亚诺算术是一致的，那么它自身无法形式化地证明自身的一致性。\(^\text{[20]}\)

　　 虽然人们普遍认为哥德尔定理否定了使用有限方法证明皮亚诺算术一致性的可能性，但这其实依赖于人们对 “有限证明” 一词具体含义的理解。哥德尔本人曾指出，可以使用一些不能在皮亚诺算术内部形式化的有限方法，对皮亚诺算术或更强系统给出一致性证明。1958 年，哥德尔发表了一种基于类型论的一致性证明方法。\(^\text{[21]}\)1936 年，格哈德·根岑给出了一种皮亚诺公理系统一致性的证明，使用了一个称为 $\varepsilon_0$ 的序数的超限归纳法。。\(^\text{[22]}\) 根岑解释道：“本文的目的是证明初等数论的一致性，或者说，将一致性问题归约为某些基本原理。” 根岑的证明常被认为是有限性的，因为 $\varepsilon_0$ 可以用有限对象来编码（例如，作为一个图灵机描述某种整数的序结构，或者更抽象地，表示为某种有限树的线性有序结构）。然而，根岑的证明是否符合希尔伯特设想的 “有限性” 要求仍不明确：目前并没有一个被广泛接受的、精确定义的 “有限证明” 的概念，而希尔伯特本人也从未给出这个概念的明确定义。

　　 当代绝大多数数学家都相信皮亚诺公理是一致的，这种相信或基于直觉，或基于对某种一致性证明（如根岑的证明）的接受。

　　 但也有少数哲学家和数学家（其中一些人还主张超有限主义）拒绝接受皮亚诺公理，因为接受这些公理就意味着接受自然数的无限集合。尤其是，加法（包括后继函数）和乘法被假设为全定义的运算（即对所有自然数都适用）。

　　 有趣的是，存在一些自我验证理论，它们与皮亚诺算术类似，但使用减法和除法代替加法和乘法，并通过特定方式加以公理化，从而避免证明那些等价于加法和乘法 “全定义性” 的命题。尽管如此，这些理论仍能证明皮亚诺算术中所有真实的 $\Pi_1$ 命题，而且还能扩展为一个一致的理论，该理论能证明自身的一致性（即以 “0 ≠ 1” 不可由希尔伯特风格证明为形式表述的一致性命题）。\(^\text{[23]}\)

2. 一阶理论中的皮亚诺算术

　　 除第九条公理（归纳公理）外，皮亚诺公理的其余部分都是一阶逻辑中的命题。\(^\text{[24]}\) 加法、乘法和序关系这些算术运算，也可以通过一阶公理来定义。上面所述的归纳公理是一个二阶公理，因为它是对谓词进行量化的（也可以理解为对自然数的集合进行量化，而不仅仅是对自然数本身）。作为替代，可以采用一种一阶归纳公理模式。该模式包含对每一个可以在皮亚诺算术的一阶语言中定义的谓词所对应的一个归纳公理。因此，这种模式比原始的二阶归纳公理更弱。\(^\text{[25]}\) 它之所以更弱，是因为在一阶语言中可定义的谓词数量是可数的，而自然数集合的总数是不可数的。因此，存在许多集合是无法在一阶语言中描述的（实际上，大多数集合都具备这一性质）。

　　 此外，皮亚诺算术在一阶公理化中还有一个技术限制：在二阶逻辑中，可以从 “后继函数” 出发推导出加法和乘法运算，但在更受限的一阶逻辑中无法做到这一点。因此，在皮亚诺算术的语言符号中，加法和乘法必须被直接包含进来，并且要明确给出一组连接三种运算之间关系的公理。

　　 以下这组公理（再加上通常的等式公理），包含了罗宾逊算术七条公理中的六条，对于皮亚诺算术的一阶公理化是足够的：\(^\text{[26]}\)

　　 除了上述关于数的基本公理之外，皮亚诺算术还包含归纳公理模式，该模式由一组递归可枚举、甚至是可判定的公理组成。对于皮亚诺算术语言中的任意公式 $\varphi(x, y_1, \ldots, y_k)$，其对应的一阶归纳公理为： $$ \forall \bar{y} \left( \left( \varphi(0, \bar{y}) \land \forall x\left( \varphi(x, \bar{y}) \Rightarrow \varphi(S(x), \bar{y}) \right) \right) \Rightarrow \forall x \varphi(x, \bar{y}) \right)~ $$ 其中 $\bar{y}$ 是 $y_1, \ldots, y_k$ 的缩写。一阶归纳公理模式包括了所有这种形式的实例，也就是说，它包含了对每一个一阶公式 $\varphi$ 所对应的归纳公理。

等价的公理化形式

　　 上述的皮亚诺算术公理化采用的是一种语言符号系统，其中只包含 “零”、以及 “后继函数”、“加法” 和 “乘法” 运算符号。然而，除了这种形式，还有许多不同但等价的公理化方式。

　　 其中一种替代表述形式 \(^\text{[27]}\)，使用的是序关系符号代替后继函数，并基于离散有序半环的语言进行公理化。该系统的公理划分如下：第 1–7 条：关于半环结构的公理；第 8–10 条：关于序关系的公理；第 11–13 条：关于运算与序关系的兼容性；第 14–15 条：关于离散性的规定。

  1. 对所有 $x, y, z$： $(x + y) + z = x + (y + z)$  即：加法满足结合律。
  2. 对所有 $x, y$： $x + y = y + x$  即：加法满足交换律。
  3. 对所有 $x, y, z$： $(x \cdot y) \cdot z = x \cdot (y \cdot z)$  即：乘法满足结合律。
  4. 对所有 $x, y$： $x \cdot y = y \cdot x$  即：乘法满足交换律。
  5. 对所有 $x, y, z$： $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$  即：乘法对加法满足分配律。
  6. 对所有 $x$： $x + 0 = x \land x \cdot 0 = 0$  即：0 是加法的单位元，是乘法的吸收元（实际上是多余的 \(^\text{[note 3]}\)）。
  7. 对所有 $x$： $x \cdot 1 = x$  即：1 是乘法的单位元。
  8. 对所有 $x, y, z$：   若 $x < y \land y < z$，则 $x < z$  即：小于关系满足传递性。
  9. 对所有 $x$： $\lnot(x < x)$  即：小于关系具备反自反性。
  10. 对所有 $x, y$： $x < y \lor x = y \lor y < x$  即：任意两个元素之间满足三歧性。
  11. 对所有 $x, y, z$：   若 $x < y$，则 $x + z < y + z$  即：加上相同的元素保持大小关系。
  12. 对所有 $x, y, z$：   若 $0 < z \land x < y$，则 $x \cdot z < y \cdot z$  即：与同一个正数相乘保持大小关系**。
  13. 对所有 $x, y$：   若 $x < y$，则存在某个 $z$，使得 $x + z = y$  即：任意两个不等的元素之间存在差值。
  14. $0 < 1 \land \forall x\ (x > 0 \Rightarrow x \geq 1)$  即：0 和 1 是不同的元素，且它们之间没有中间值。换言之，1 是 0 的后继，表示数是离散的。
  15. 对所有 $x$： $x \geq 0$  即：0 是最小的自然数元素。

　　 由上述这些公理所定义的理论被称为 PA⁻（皮亚诺算术减归纳）。该理论同样是不完备的，它的一个重要性质是：任何满足该理论的结构 $M$，在按 $\leq$ 排序下，都包含一个与 $\mathbb{N}$ 同构的初始段。这个初始段中的元素被称为标准元素，而结构中其他不属于该段的元素则被称为非标准元素。

　　 最终，完整的皮亚诺算术 PA 是通过在 PA⁻ 的基础上加入一阶归纳公理模式来获得的。

不可判定性与不完备性

　　 根据哥德尔的不完备性定理，皮亚诺算术（PA）的理论（若是一致的）是不完备的。因此，存在某些在 PA 的标准模型中为真的一阶逻辑（FOL）句子，但它们并不是该一阶公理体系的逻辑后果。

　　 事实上，即使是更弱的公理系统，比如罗宾逊算术，也已经体现出这种本质上的不完备性。这一不完备性结果与哥德尔的一阶逻辑完备性定理密切相关，由此可以推出一个结论：不存在算法能够判定某个一阶句子是否是皮亚诺算术一阶公理化的逻辑后果。因此，PA 是一个不可判定的理论。实际上，即使是 PA 中的存在性命题也已经不可判定。这是因为希尔伯特第十问题的负解表明：所有可枚举集合都是丢番图集合，因此都可以通过 PA 中带有自由变量的存在量词公式来定义。相较于存在性公式，具有更高量词等级（即更多量词交替）的 PA 公式表达能力更强，它们可以定义属于算术层级更高层次的集合。

非标准模型

　　 虽然通常所说的自然数满足皮亚诺算术（PA）的公理，但实际上还存在其他满足这些公理的模型，称为非标准模型。根据紧致性定理，在一阶逻辑中无法排除非标准元素的存在。\(^\text{[28]}\) 此外，上向 Löwenheim–Skolem 定理表明，PA 存在任意无限势（基数）下的非标准模型。而在原始的（二阶）皮亚诺公理体系中，模型是唯一的（在同构意义下）。\(^\text{[29]}\) 这也说明了一阶系统 PA 相较于二阶皮亚诺公理更弱的一个方面。

　　 当我们将 PA 理解为某个一阶集合论（如 ZFC）中的一个可证明理论时，德德金对 PA 的范畴性证明意味着：每一个集合论模型中，都存在唯一一个（在同构意义下）满足皮亚诺公理的模型，它作为一个初始段嵌入该集合论模型中所包含的所有其他 PA 模型中。在集合论的标准模型中，这个最小的 PA 模型就是标准的自然数模型；但如果集合论模型本身是非标准的，那么这个 “最小” 的 PA 模型也可能是非标准的。而这一现象在任何一阶形式化的集合论中都是无法避免的。

　　 那么，自然会有人问：是否可以显式构造出一个可数的非标准模型？答案是肯定的。1933 年，斯科勒姆就给出了一个这样的非标准模型的显式构造。但另一方面，1959 年，坦能鲍姆定理指出：不存在一个可数的非标准 PA 模型，其加法或乘法是可计算的。\(^\text{[30]}\) 这一结果表明：在可数非标准模型中，很难以完全显式的方式刻画加法和乘法运算。此外，所有可数的非标准 PA 模型具有唯一的一种序类型。设：$\omega$ 表示自然数的序类型，$\zeta$ 表示整数的序类型，$\eta$ 表示有理数的序类型，那么，任何可数非标准 PA 模型的序类型是：$\omega + \zeta \cdot \eta$ 也就是说：它的结构可以被想象为：先是一段标准的自然数序列（ω），随后是一个稠密排列的、由整数序列组成的线性序列。

　　 溢出原理

　　 在一个非标准模型 $M$ 中，割集是 $M$ 的一个非空子集 $C$，满足以下两个条件：向下封闭：若 $x < y$ 且 $y \in C$，则 $x \in C$；对后继封闭：若 $x \in C$，则 $S(x) \in C$。若 $C$ 是 $M$ 的一个真子集（即不是整个 $M$），则称其为一个真割集。每一个非标准模型都有许多真割集，其中包括一个与标准自然数对应的割集。然而，在皮亚诺算术中，由于包含归纳公理模式，任何真割集都不可能是可定义的。溢出引理首次由亚伯拉罕·罗宾逊提出，正式地刻画了这一事实。

　　 溢出引理\(^\text{[31]}\) 设 $M$ 是皮亚诺算术的一个非标准模型，$C \subsetneq M$ 是一个真割集。设 $\bar{a}$ 是 $M$ 中若干个元素组成的元组，$\varphi(x, \bar{a})$ 是算术语言中的一个公式，并且满足： $$ M \models \varphi(b, \bar{a}) \quad \text{对所有 } b \in C~ $$ 那么，存在某个 $c \in M$，它大于 $C$ 中的所有元素，并且仍满足： $$ M \models \varphi(c, \bar{a})~ $$ 换句话说，如果某个公式 $\varphi(x, \bar{a})$ 对割集中的所有元素都为真，那么它也会在某个超出该割集的非标准元素处成立——这就是所谓的 “溢出” 现象。

3. 另见

4. 注释

  1. 表示 0 的最近的浅色棋子，以及表示后继的相邻棋子
  2. 非连续集合满足公理 1（因为它包含一个 0 元素），满足公理 2–5（因为这不影响等式关系），满足公理 6（因为所有棋子都有一个后继），满足公理 7（因为没有两个多米诺骨牌被同一个棋子推动或推动同一个棋子），也满足公理 8（因为除了第一个浅色棋子之外，其他每个多米诺骨牌都被另一个推倒）。
  3. 命题 “$\forall x \ (x \cdot 0 = 0)$” 可以从其他公理（在一阶逻辑中）推导出来，推导如下：首先，根据分配律与加法单位元性质，有：$x \cdot 0 + x \cdot 0 = x \cdot (0 + 0) = x \cdot 0 = x \cdot 0 + 0$ 其次，根据**公理 15**（关于 0 和 1 的序关系），我们知道：$x \cdot 0 = 0 \quad \lor \quad x \cdot 0 > 0$ 假设 $x \cdot 0 > 0$，那么根据加法的保序性与交换律，有：$x \cdot 0 + x \cdot 0 > x \cdot 0 + 0$ 进而得到：$x \cdot 0 + 0 > x \cdot 0 + 0$ 这与小于关系的反自反性矛盾，因此假设不成立。所以，必须有：$x \cdot 0 = 0$ 这一推理说明，在定义中虽然 $x \cdot 0 = 0$ 被列为一个公理，但在特定公理系统中，它是可以从其他公理推导而得的。

5. 参考文献

引文

  1. “Peano”，《兰登书屋韦氏完整版词典》
  2. 格拉斯曼，1861 年（*Grassmann 1861*）
  3. 王浩，1957 年，第 145、147 页：“众所周知，正如皮亚诺自己承认的那样，他在发展其公理体系的过程中大量借鉴了格拉斯曼的工作。不那么为人所知的是，格拉斯曼实际上已经给出了一个整数集合的刻画，这种刻画现在在现代代数教材中已相当常见——即整数构成一个有序整环，其中每个正数集合都具有最小元。[……] [格拉斯曼的著作] 很可能是首次严肃而较为成功地尝试以公理化的方式建立数的体系。”
  4. 皮尔士，1881 年
  5. 希尔兹，1997 年
  6. 范·海耶诺特，1967 年，第 94 页
  7. 范·海耶诺特，1967 年，第 2 页
  8. 范·海耶诺特，1967 年，第 83 页
  9. 皮亚诺，1889 年，第 1 页
  10. 皮亚诺，1908 年，第 27 页
  11. Matt DeVos，《数学归纳法》，西蒙弗雷泽大学
  12. Gerardo Con Diaz，《数学归纳法》，哈佛大学，2013 年 5 月 2 日存档于 Wayback Machine
  13. Meseguer 与 Goguen（1986），第 2.3 节（第 464 页）与第 4.1 节（第 471 页）
  14. 关于形式证明，可参见例如：《从递归定义出发对加法和乘法性质的归纳证明》（文件名：Inductive proofs of properties of add, mult from recursive definitions.pdf）
  15. Suppes（1960），Hatcher（2014）
  16. Tarski 与 Givant（1987），第 7.6 节
  17. Fritz（1952），第 137 页 关于 “解释” 的一个例子是罗素本人对 “基数” 的定义。在这个例子中，未解释系统是皮亚诺对数系的公理体系——皮亚诺认为，其三个基本概念和五条公理足以推导出自然数体系的全部性质。然而，罗素指出，皮亚诺的公理实际上是对任何类似如下形式的数列的定义：$x_0, x_1, x_2, \ldots, x_n, \ldots$ 其中自然数列只是其中的一个特例。
  18. Gray 2013，第 133 页：   “于是庞加莱开始探讨逻辑主义是否能够导出算术，更准确地说，是**序数的算术**。庞加莱指出，Couturat 接受了皮亚诺公理作为数的定义，但这是站不住脚的。因为我们无法通过列举实例来证明这些公理无矛盾；而如果试图通过检验其所有推论来证明无矛盾，则这恰恰需要用到 Couturat 所认为这些公理能够导出的数学归纳原理。   （在《科学与方法》中被删去的一段）进一步指出：要么我们假设归纳原理来证明它，这样做只能说明‘若它是真的，则它不矛盾’，这并无实质内容；要么我们使用了归纳原理的另一个形式，但这又需要我们证明我们的推理步骤的数量在新的定义下是一个整数，而这是做不到的。”（1905c，第 834 页）
  19. Hilbert，1902
  20. Gödel，1931
  21. Gödel，1958
  22. Gentzen，1936
  23. Willard，2001
  24. Partee、Ter Meulen 与 Wall，2012，第 215 页
  25. Harsanyi（1983）
  26. Mendelson，1997，第 155 页
  27. Kaye，1991，第 16–18 页
  28. Hermes，1973，VI.4.3，介绍 Thoralf Skolem 的一个定理
  29. Hermes，1973，VI.3.1
  30. Kaye，1991，第 11.3 节
  31. Kaye，1991，第 70 页及以后

资料来源

6. 延伸阅读

7. 外部链接

　　 本文部分内容引自 PlanetMath 上的 PA 条目，依据 Creative Commons Attribution/Share-Alike License 发布


致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。

                     

友情链接： 超理论坛　|　©小时科技 保留一切权利