Peano 公理 ——自然数最早的公理化定义

(Peano, 1889) 设 `NN` 是一个非空集合, `0 in NN` 是其中某一特定的元. `+` 是 `NN` 上一变换 (即 `NN` 到自身的映射), `(NN, 0, +)` 满足:
1. `0 !in "ran"(+)`, 即不存在 `x in NN`, 使得 `0 = x^+`;
2. `+` 是一单射, 即 `x^+ = y^+ rArr x = y`;
3. 归纳原理: `AA E sube NN`, 如果 (1) `0 in E`; (2) `n in E rArr n^+ in E`, 那么 `E = NN`.

零的惟一性 设 `n in NN`, 则 `n != 0` `iff EE x in NN`, `n = x^+`. 即, `NN` 中仅有 0 满足 Peano 公理的性质 1.

`lArr` 由公理可知, 下证 `rArr`. 反设 `n in NN`, `n != 0`, 且 `AA x in NN`, `n != x^+`. 用 `E` 表示与 `n` 不相等的所有自然数, 因此 `0 in E`. 若 `x in E`, 即 `x != n`, 由假设 `n != x^+` 成立, 故 `x^+ in E`. 由归纳原理知 `E = NN`, 即 `n` 不与任何自然数相等, 矛盾; 因此 `n = 0`.

自然数的惟一性 满足 Peano 公理的系统都彼此同构; 因此在同构意义下, 自然数系统是惟一的. 所谓 `(NN, 0, +)` 与 `(NN', 0', +')` 同构, 是指存在一个双射 `f: NN to NN'`, 使得 `f(0) = 0'`, `quad f(n^+) = f(n)^(+')`, `quad AA n in NN`.

1. 由于 `0'` 是惟一的, 可以令 `f(0) = 0'`. 我们把 `f` 的定义域记为 `E`, 因此 `0 in E`. 对任意 `n in E`, 定义 `f(n^+) = f(n)^(+')`, 因此 `n^+` 也有定义, `n^+ in E`. 由归纳原理, `E = NN`, `f` 在 `NN` 上有定义.
2. 下证 `f` 是满射, 即证 `AA n' in NN'`, `EE n in NN` 使 `n' = f(n)`. 若 `n' = 0'`, 结论成立; 现在设结论在 `E sube NN'` 上成立, 由已知 `0' in E`. 若 `n' = f(n)` 成立, 则 `{:n':}^(+') = f(n)^(+') = f(n^+)`, 结论也成立. 在 `NN'` 上应用归纳原理知结论成立.
3. 下证 `f` 是单射, 即证 `AA m, n in NN`, `f(m) = f(n) rArr m = n`. 若 `m, n` 之中有一个为 `0`, 不妨设 `m = 0`, 则 `f(n) = f(0) = 0'`, 若 `n != 0`, 则存在 `x in NN` 使 `x^+ = n`. 于是 `f(n) = f(x^+) = f(x)^(+') != 0`, 矛盾; 因此 `n = 0`. 现在设 `f(m) = f(n) rArr m = n`, 则 `f(m^+) = f(n^+)` `iff f(m)^(+') = f(n)^(+')` `rArr f(m) = f(n)` `rArr m = n`. 在 `NN` 上应用归纳原理知结论成立.

自然数集 `NN` 的惟一性已经得到保证. 下面我们将在集合论中保证它的存在性.

在公理集合论体系内定义自然数

归纳集与归纳原理

对任意集合 `x`, 定义 `x^+ := x uu {x}`, 称为 `x` 的后继元 (successor). 由配对公理, 并公理和外延公理, 后继元是存在惟一的. 后继元就是把集合 `x` "放入自身" 所得到的集合, 如 `{1, 2}^+ = {1, 2, {1, 2}}`. 显然有 `x in x^+`, `x sube x^+`.

称 `A` 是一个归纳集 (inductive set), 如果
1. `O/ in A`;
2. `x in A rArr x^+ in A`.

在集合论体系内引入下面的公理:

无限公理 归纳集是存在的.

归纳集的全体不构成集, 而是一个真类. (??)

自然数的定义 由无限公理, 归纳集存在. 将最小的归纳集记为 `omega`, 称为自然数集, 它的元素称为自然数. 由归纳集定义,`O/ in omega`, 我们记 `0 := O/`, `1 := 0^+`, `2 := 1^+`, 等等: `0 = O/`, `quad 1 = {O/}`, `quad 2 = {O/, {O/}} cdots`. 但什么是 "最小" 的归纳集呢? 我们不能取 `omega` 为所有归纳集的交, 因为归纳集的全体不构成集. 相对地, 取归纳集 `A`, 然后定义 `omega` 为 `A` 的子集: `omega := {x in A:` 对任意归纳集 `E` 有 `x in E}` 该集合的存在惟一性由子集公理和外延公理保证. 下面证明, `omega` 确是一个归纳集, 并且是最小的归纳集.

首先 `O/ in A`, 且对任意归纳集 `E` 有 `O/ in E`, 从而由 `omega` 的定义, `O/ in omega`.
其次, 若 `x in omega`, 则 `x in A`, 且对任意归纳集 `E` 有 `x in E`. 于是分别由 `A, E` 是归纳集知, `x^+ in A`, 且对任意归纳集 `E` 有 `x^+ in E`. 再由 `omega` 的定义知 `x^+ in omega`.
由归纳集的定义, `omega` 是归纳集. 由 `omega` 的定义知对任意归纳集 `E`, `omega sube E`, 因此是最小的归纳集.

由自然数集的作法知道, "交" 的概念可以从集合的交推广到更一般情形: 真类的交.

可以验证, 我们定义的自然数集 `omega` 适合 Peano 公理. 先证最有用的归纳原理:

自然数归纳原理 (数学归纳法原理) 设 `T sube omega`, `0 in T` 且 `n in T rArr n^+ in T`, 则 `T = omega`. 于是 `omega` 满足 Peano 公理的 3.

显然 `T` 是归纳集, 因此 `omega` 作为最小的归纳集, 有 `omega sube T`. 但 `T sube omega`, 于是 `T = omega`.

自然数归纳原理告诉我们, 要得到所有的自然数, 只需从 `0` 开始, 每次按最近得到的数 `n`, 将 `n^+` 也加入到集合中来, 这一过程无限地 (合法性由无限公理保证) 进行下去, 就得到全体自然数.

`bm omega` 上的强归纳原理 设 `T sube omega`, 且 `n sube T rArr n in T`, 则 `T = omega`.

令 `S = {n in omega: n sube T}`, 由定义 `S sube T sube omega`.
首先 `0 in omega`, 且 `0 = O/ sube T`, 因此 `0 in S`. 其次若 `n in S`, 则 `n sube T`, 于是 `n in T`, 从而 `n^+ = n uu {n} sube T`. 又由定义 `omega` 是归纳集, 所以由 `n in omega` 得到 `n^+ in omega`. 这推出 `n^+ in S`. 于是由自然数归纳原理, `S = omega`, 从而只能 `T = omega`.

传递集与单调性

本小节证明 `n mapsto n^+` 是单射. 为此引入传递集的概念.

称 `A` 为一传递集 (transitive set), 如果 `EE x (t in x ^^ x in A) rArr t in A`. 由于 `x in O/` 是伪命题, 上式的前件为假, 因此对 `A = O/` 上式为真, 即 `O/` 是传递集.

以下集合均为传递集: `O/`, `{O/}`, `{O/, {O/}}`...

`AA A`, 下列命题等价:
1. `A` 是传递集;
2. `uuu A sube A`;
3. `a in A rArr a sube A`;
4. `A sube 2^A`.

1. `rArr` 2. 设 `t in uuu A`, 则 `EE x in A`, `t in x`. 由传递集的定义得 `t in A`.
2. `rArr` 3. 设 `a in A`, 则 `a sube uuu A`. 由 2, `uuu A sube A`, 所以 `a sube A`.
3. `iff` 4. 显然.
4. `rArr` 1. 设 `t in x`, `x in A`. 由 4, `x in 2^A`, 即 `x sube A`. 再由 `t in x` 得 `t in A`.

正则公理 对任意非空集合 `A`, 存在 `a in A` 满足 `a nn A = O/`: `AA A(A != O/ rarr EE a(a in A ^^ a nn A = O/))`. 正则公理确保属于关系不会循环, 比如, 不会有 `x in x`, `x in y in x` 或 `x_0 ∋ x_1 ∋ x_2 ∋ cdots` 的情况. (??) 因为正则公理排除了 `x in x` 的情况, 所以 Russel 悖论不会出现.

若 `x` 是传递集, 则 `uuu x^+ = x`.

`x^+ = x uu {x}`, 显然 `x in x^+`, 故 `x sube uuu x^+`.
设 `a in x^+ = x uu {x}`, 则 `a in x` 或 `a = x`. 由 `x` 是传递集知 `a sube x` 或 `a = x`. 从而 `x^+` 的每一元素都是 `x` 的子集, 有 `uuu x^+ sube x`.

若 `x` 是传递集, 则 `uuu x^+ = x sube x^+`, 所以 `x^+` 也是传递集. 从而由 `0 = O/` 是传递集知, 每个自然数都是传递集.

平行于强归纳原理, 有:

`omega` 本身也为一传递集.

令 `T = {x in omega: x sube omega}`,
首先 `0 in omega`, 且 `0 = O/ sube omega`, 所以 `0 in T`. 其次若 `n in T`, 即 `n in omega`, `n sube omega`, 于是 `n^+ = n uu {n} sube omega`. 又由 `omega` 是归纳集和 `n in omega` 推出 `n^+ in omega`. 这推出 `n^+ in T`. 于是由自然数归纳原理 `T = omega`. 但 `T` 是一传递集: `AA t in T`, `t sube omega = T`. 所以 `omega` 也是传递集.

现在证明 Peano 公理的 2, 即变换 `n mapsto n^+` 是单射.

1. `(AA m, n in omega)` `m = n iff m^+ = n^+`;
2. `(AA n in omega)` `n != n^+`.

1. 只需证 `m^+ = n^+ rArr m = n`. 设 `m^+ = n^+`, 则 `uuu m^+ = uuu n^+`, 但 `m, n` 为传递集, 所以 `uuu m^+ = m`, `uuu n^+ = n`, 从而 `m = n`.
2. 令 `T = {n in omega: n != n^+}`. 首先因为 `0^+ = O/ uu {O/} = {O/} != O/ = 0`, 所以 `0 in T`.
   其次若 `n in T`, 则 `n != n^+`, 由 1 有 `n^+ != n^(+ +)`, 从而 `n^+ in T`, 由归纳原理, `T = omega`.

最后, `AA n in omega`, `n^+ = n uu {n} != O/ = 0`. 即 `omega` 满足 Peano 公理的 1, 从而 `omega` 是一个 Peano 系统.