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` 的惟一性已经得到保证. 下面我们将在 ZFC 集合论中保证它的存在性.

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

归纳集与归纳原理

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

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

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

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

设非空集合 `S` 的元素均为归纳集, 则 `uuu S` 是归纳集.

`O/ in uuu S`; 若 `x in uuu S`, 则存在 `A in S` 使得 `x in A`. 于是 `x^+ in A sube uuu S`. 因此 `uuu S` 是归纳集.

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

[来自群友 幂零群] 考虑全体归纳集 `S`. 若 `S` 是集合, 则定义 `S_0 := S`, `S_(n+1) := S_n^+`. 应用替换公理模式, 将下文的自然数集 `omega` 替换为 `T := {S_n: n in omega}`, 则 `omega uu T` 也是归纳集. 有 `S in omega uu T in S`, 与正则公理矛盾.

自然数的定义 由无限公理, 归纳集存在. 将最小的归纳集记为 `omega`, 称为自然数集, 它的元素称为自然数. 由归纳集定义,`O/ in omega`, 我们记 `0 := O/`, `1 := 0^+`, `2 := 1^+`, 等等: `0 = O/`,
`1 = {0} = {O/}`,
`2 = {0, 1} = {O/, {O/}}`,
`3 = {0, 1, 2} = {O/, {O/}, {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` 而不是 `NN` 的理由是, 自然数有多种定义方式, `omega` 用来特指它的这一种定义.

由自然数集的作法知道, "交" 的概念可以从集合的交推广到更一般情形: 真类的交. 设 `cc C` 是一个真类 (其元素为集合, 而且非空, 毕竟空集不是真类), 先取 `A in cc C`, 然后令 `I := { x in A: AA E in cc C, x in E}`. 称 `I` 为真类 `cc C` 的交, 记为 `uuu cc C`.

可以验证, 我们定义的自然数集 `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), 如果 "`in`" 的传递性在 `A` 上成立: `EE x (t in x ^^ x in A) rArr t in A`. 由于 `x in O/` 是伪命题, 上式的前件为假, 因此对 `A = O/` 上式为真, 即 `O/` 是传递集.

自然数 0, 1, 2... 均为传递集: `O/`, `{O/}`, `{O/, {O/}}`...

传递集的全体也是一个真类. 我们将在序数一节中说明.

    `AA A`, 下列命题等价:
  1. `A` 是传递集;
  2. `uuu A sube A`;
  3. `a in A rArr a sube A`; 即 `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`.

后继的逆运算 若 `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`.

    传递集的性质
  1. 传递集的后继也是传递集.
  2. 若非空集合 `S` 的元素皆是传递集, 则 `nnn S`, `uuu S` 是传递集.
  1. 设 `x` 是传递集, 则 `uuu x^+ = x sube x^+`, 所以 `x^+` 也是传递集.
  2. 取 `x in nnn S`, 则 `AA y in S`, `x in y`. 由 `y` 是传递集知 `x sube y`. 再由 `y` 的任意性知 `x sube nnn S`. 故 `nnn S` 是传递集.
    `uuu S` 的证明类似.

由于 `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/} != 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 系统.

序数

[来自 李文威《代数学方法》]

序数类

    (von Neumann) 称集合 `alpha` 是一个序数, 如果
  1. `alpha` 是传递集. 即 `alpha` 的每个元素都是 `alpha` 的子集, 换言之 `alpha sube cc P(alpha)`.
  2. `alpha` 的元素按从属关系 "`in`" 构成良序, 即 `(alpha, in)` 是良序集.
    3. 每个自然数都是序数; `omega` 也是序数.

由正则公理知道, 不存在从属关系的无穷降链, 因此 `alpha` 的每个非空子集总是有极小元, 从而条件 2 可以减弱为全序.

序数中的极小元 [来自群友 幂零群] 若 `alpha != O/` 是序数, 则 `alpha` 存在唯一极小元, 这个极小元就是 `O/`.

由 `(alpha, in)` 是良序集知道 `alpha` 存在一个极小元 `m`. 假设 `m != O/`, 取 `x in m`, 则由 `alpha` 的传递性和 `m in alpha` 知道 `x in alpha`. 这与 `m` 的极小性矛盾, 因此 `m = O/`. 再由空集的唯一性知 `alpha` 的极小元唯一.

    序数的性质
  1. 若 `alpha` 是序数, 则其后继 `alpha^+` 也是序数.
  2. 若 `alpha` 是序数, 则它的元素 (如果存在) 也是序数.
  3. 若 `alpha, beta` 是序数, 则 `alpha nn beta` 也是序数.
  1. 这是因为传递集的后继也是传递集. 下证 `alpha^+ = alpha uu {alpha}` 是良序集. 事实上和集合 `alpha` 相比, 集合 `alpha^+` 只多了一个元素 `alpha`, 因此 `alpha^+` 中的其它元素皆是 `alpha` 的元素, 这指出 `alpha^+` 是全序, 且 `alpha` 是其中的最大元. 添加一个最大元并不影响每个非空子集有极小元, 因此 `alpha^+` 是良序集.
  2. 设 `beta in alpha`. 由 `alpha` 是传递集知 `beta sube alpha`. 因此 `beta` 作为 `alpha` 的子集也是良序集.
    又设 `x in tau in beta`, 由 `alpha` 是传递集和 `tau in beta in alpha` 知道 `tau in alpha`. 同理由 `x in tau in alpha` 知道 `x in alpha`. 现在 `x, tau, beta` 皆是 `alpha` 的元素, 由 `alpha` 上序关系的传递性知道 `x in beta`, 因此 `beta` 是传递集.
  3. 首先由传递集的性质知道 `alpha nn beta` 是传递集, 又良序集的子集也是良序集, 所以 `alpha nn beta` 是序数.
    序数之间的关系
  1. 若 `alpha, beta` 是序数, `alpha subne beta`, 则 `alpha in beta`.
  2. 若 `alpha, beta` 是序数, 必有 `alpha sube beta` 或 `beta sube alpha`.
    3. 总之, 对任意两个序数 `alpha, beta`, 必有 `alpha in beta`, `beta in alpha`, `alpha = beta` 之一成立.
  1. 因为 `alpha` 真包含于 `beta`, 可令 `gamma` 为 `beta - alpha` 的极小元. 用 `lt` 表示 `in`, 令 `X = {x in beta: x lt gamma}`, 下证 `X = alpha`.
    事实上任取 `x in X`, 由 `x lt gamma` 知道 `x !in beta - alpha`, 即 `x in alpha`, 这证明了 `X sube alpha`.
    另一方面任取 `y in alpha`, 由 `alpha` 的传递性有 `y sube alpha`, 因此 `gamma !in y`, 即 `gamma` 不小于 `y`. `gamma` 也不等于 `y`, 这是因为 `gamma in beta - alpha` 而 `y in alpha`. 综上由于 `alpha` 是全序集, 只能 `y lt gamma`, 即 `y in X`. 这证明了 `alpha sube X`.
    把 `X` 定义中的 `lt` 换成 `in` 可知 `X = gamma`, 因此事实上我们证明了 `alpha` 是 `beta - alpha` 的极小元.
  2. 令 `gamma := alpha nn beta`, 则 `gamma` 也是序数, 我们证明必有 `gamma = alpha` 或 `gamma = beta`. 否则, `gamma` 是 `alpha` 和 `beta` 的真子集. 由 1. 知道 `gamma in alpha`, `gamma in beta`, 从而 `gamma in gamma`, 与偏序的反称性矛盾 (或者说, 与正则公理矛盾).

序数类 我们把全体序数记为 `bb(On)`. 定义序数 `alpha lt beta` 当且仅当 `alpha in beta`, 则 `(bb(On), lt)` 构成全序, 进而由正则公理知道它构成良序, 但不是良序集, 因为 `bb(On)` 不是一个集合!

若非空集合 `S` 的元素皆为序数, 则 `nnn S`, `uuu S` 是序数. 分别记作 `"inf"S` 和 `"sup"S`. 特别有 `"inf"S in S`.

我们已经知道 `"inf" S`, `"sup" S` 是传递集. 又 `(bb(On), lt)` 构成良序, 所以 `"inf" S`, `"sup" S` 都是良序集.
下证 `"inf"S in S`. 因为 `"inf"S = nnn S`, 所以对任意序数 `alpha in S` 都有 `"inf"S sube alpha`. 但 `"inf"S`, `alpha` 皆为序数, 所以必有 `"inf"S = alpha` 或 `"inf"S in alpha`. 我们断言必存在 `alpha in S` 使得 `"inf"S = alpha`, 假如不然, 则对任意 `alpha in S` 都有 `"inf"S in alpha`, 于是 `"inf" S in nnn S = "inf"S`, 矛盾.
注: 因为 `"inf"S in S`, 所以它实际是 `S` 中的最小序数. 我们还可以说明 `"sup"S` 是 `S` 的上确界. 这是因为对任意 `alpha in S`, `alpha sube uuu S`, 从而 `alpha le S`, 说明它是上界. 又任取 `beta lt "sup"S`, 则 `beta in uuu S`, 即存在 `S_0 in S` 使 `beta in S_0`, 即 `beta lt S_0`, 说明它是最小上界, 即上确界.
  1. 我们已经学习过真类的交, 因此 `"inf" S` 定义中的 `S` 可以推广到真类. 引理告诉我们, 任意一族序数都可以取其中的最小元.
  2. 约定 `"sup" O/ = O/`.
  3. `"sup"S in S` 不一定成立, 比如 `"sup" omega = omega`.

Burali-Forti 悖论 (1897) 全体序数 `bb(On)` 是一个真类. 由于序数是特殊的传递集, 传递集的全体也是真类.

假如 `bb(On)` 是一个集合, 则 `S := uuu bb(On)` 有定义, 且 `S` 也是一个序数. 考虑 `S` 的后继 `S^+`, 它也是一个序数, 且严格大于全体序数. 这是因为任取 `alpha in bb(On)`, 有 `alpha sube S`. 若 `alpha = S`, 则 `alpha = S in S^+`; 若 `alpha != S`, 则 `alpha in S sube S^+`. 但 `S^+` 自身也是一个序数, 这意味着 `S^+` 大于自身, 一个矛盾.

`bb(On)` 不能被嵌入到集合中. 换言之, 对任意集合 `P`, 不存在单射 `bb(On) to P`.

若存在这样的单射 `f`, 分离公理模式确保 `f(bb(On)) sube P` 是集合, 而替换公理模式指出 `bb(On) = f^-1(f(bb(On)))` 亦是集合, 矛盾.

极限序数

极限序数 若序数 `alpha` 不是任何序数的后继, 则称 `alpha` 是极限序数. `O/`, `omega` 都是极限序数. 我们把小于 `omega` 的序数称为有限序数, 而其它序数称为无穷序数. `omega` 是最小的无穷序数, 也是除了 `O/` 之外最小的极限序数.

利用公式 `x = uuu x^+` 快速判断: 如果 `alpha = uuu alpha`, 则它是极限序数; 否则不是.

理解序数构造的钥匙 设 `alpha` 是序数, 则 `alpha` `= {beta: beta in alpha}` `= {beta: beta lt alpha}`. 由此可知每个序数都是一个集合, 它恰好包含了小于它的所有序数. 例如, `1 = {0}`, `2 = {0, 1}`, `omega = {0, 1, 2, ...}`

  1. `alpha^+ = "inf"{beta: beta gt alpha}`, 因此 `alpha^+` 是大于 `alpha` 的最小序数.
  2. `beta lt alpha^+ iff beta le alpha`. 换言之不存在 `beta` 使得 `alpha lt beta lt alpha^+`.
  3. 若 `alpha` 是极限序数, `beta lt alpha`, 则 `beta^+ lt alpha`.
  4. 若 `alpha` 是极限序数, 则 `alpha = "sup" alpha` `= "sup"{beta: beta lt alpha}`. 总之, `"sup" alpha = { beta, if alpha = beta^+; alpha, otherwise :}`.
  1. 一方面, 显然 `alpha^+ gt alpha`, 所以 `alpha^+ supe nnn { beta: beta gt alpha }`, 因为 `alpha^+` 是右边的交集的一员.
    另一方面, 任取 `beta gt alpha`, 则有 `alpha in beta`, `alpha sube beta`, 因此 `alpha^+ = alpha uu {alpha} sube beta`. 所以 `alpha^+ sube nnn {beta: beta gt alpha}`.
  2. 这是上一条的推论.
  3. 因为 `alpha` 是极限序数, 不可能有 `beta^+ = alpha`; 另一方面, 因为 `beta^+` 是大于 `beta` 的最小序数, 也不可能有 `beta^+ gt alpha`. 所以 `beta^+ lt alpha`.
  4. 一方面, 对任意 `beta lt alpha`, 有 `beta sube alpha`, 因此 `alpha supe uuu {beta: beta lt alpha}`. 另一方面, 由于 `alpha` 是极限序数, 对任意 `xi in alpha`, 取 `beta = xi^+`, 由 3. 知 `xi in beta lt alpha`, 这证明了 `alpha sube uuu {beta: beta lt alpha}`.
    构造非零极限序数的一种方法 设 `x` 是归纳集, 令 `alpha := { y in x: y sube x, y in bb(On) }`. 按定义验证以下性质:
  1. `alpha` 非空.
  2. `alpha` 是序数.
  3. `y in alpha rArr y^+ in alpha`.
    4. 因此 `alpha` 是非零极限序数.
  1. `O/ in alpha`.
  2. 先证 `alpha` 是传递集. 设 `y in alpha`, 则 `y` 是序数; 又设 `z in y`, 则 `z` 作为 `y` 的元素也是序数. 于是 `z in y sube x`, `z sube y sube x`, 因此 `z in alpha`. 又 `alpha` 的元素均为序数, 显然为一良序, 所以 `alpha` 是序数.
  3. 设 `y in alpha`, 则 `y in x`. 但 `x` 是传递集, 所以 `y^+ in x`. 又 `y in x`, `y sube x`, 所以 `y^+ = y uu {y} sube x`. 因此 `y^+ in alpha`.

超穷递归 (超限归纳法)

    超限归纳法 令 `C` 为一个由序数构成的类. 如果
  1. `O/ in C`;
  2. `alpha in C rArr alpha^+ in C`;
  3. 对于每个极限序数 `alpha`, 满足 `((AA beta lt alpha) beta in C) rArr alpha in C`.
    4. 那么 `C = bb(On)`. 如果仅考虑小于某 `theta` 的序数而非 `bb(On)` 整体, 断言依然成立.

反设 `C != bb(On)`. 取不在 `C` 中的最小序数 `alpha != O/`, 则无论它是后继或极限序数都导致矛盾.

序数的运算

设 `alpha, beta` 是序数, `gamma` 是极限序数, 借助超穷递归原理定义序数的运算如下:
加法 `alpha + 0 := alpha` `alpha + beta^+ := (alpha + beta)^+` `alpha + gamma := "sup"{alpha + xi: xi lt gamma}`
乘法 `alpha * 0 := 0` `alpha * beta^+ := alpha * beta + alpha` `alpha * gamma := "sup"{alpha * xi: xi lt gamma}`
指数 `alpha^0 := 1` `alpha^(beta^+) := alpha^beta * alpha` `alpha^gamma := "sup"{alpha^xi: xi lt gamma}`
在 `alpha, beta` 有限的情况下, 它们的运算与自然数相同.
    序数 `omega` 的一些性质
  1. 设 `alpha lt omega`, 则 `alpha + omega = omega`, `quad alpha gt 0 rArr alpha * omega = omega`, `quad alpha gt 1 rArr alpha^omega = omega`.
  2. 序数的加法和乘法满足结合律, 但交换律一般不成立, 例如 `1 + omega = omega` 是一个极限序数, 但 `omega + 1` 是一个后继序数. 乘法同理: `2 * omega = omega`, 但 `omega * 2 = omega + omega`.
    序数加法的性质 对任意序数 `alpha`:
  1. 零元: `0 + alpha = alpha`.
  2. 右不等式: `beta ge gamma rArr beta + alpha ge gamma + alpha`.
  3. 左不等式: `beta gt gamma iff alpha + beta gt alpha + gamma`.
  4. 左消去律: `beta = gamma iff alpha + beta = alpha + gamma`.
    1. 使用超穷递归证明:
    1. `alpha = 0` 时, 结论成立;
    2. 若 `0 + alpha = alpha`, 则 `0 + alpha^+` `= (0 + alpha)^+` `= alpha^+`;
    3. 若 `alpha` 为极限序数, 且对一切 `xi lt alpha` 有 `0 + xi = xi`, 则 `0 + alpha` `= "sup"{0 + xi: xi lt alpha}` `= "sup"{xi: xi lt alpha}` `= alpha`.
    2. `beta = gamma` 时结论显然. 下设 `beta gt gamma`, 对 `alpha` 归纳:
    1. `alpha = 0` 时显然成立;
    2. 设结论对 `alpha` 成立, 即 `beta + alpha ge gamma + alpha`, 下证 `beta + alpha^+ ge gamma + alpha^+`. 若 `beta + alpha = gamma + alpha`, 则结论已经成立. 若 `beta + alpha gt gamma + alpha`, 则不可能有 `beta + alpha^+ lt gamma + alpha^+`, 否则两边取上确界得到 `beta + alpha le gamma + alpha`, 矛盾.
    3. 设 `alpha` 是极限序数, 且结论对一切 `xi lt alpha` 成立: `beta + xi ge gamma + xi`. 两边取上确界就得到 `beta + alpha ge gamma + alpha`.
    3. 先证 `rArr`. 对 `beta` 归纳:
    1. `beta = 1` 时, 必有 `gamma = 0`, 结论成立;
    2. 假设 `beta gt gamma rArr alpha + beta gt alpha + gamma`, 考虑 `beta^+ gt gamma`, 若 `gamma = beta`, 显然成立 `alpha + beta^+ gt alpha + gamma`; 若 `gamma lt beta`, 由归纳假设 `alpha + beta^+ gt alpha + beta gt alpha + gamma`.
    3. 假设 `beta` 为极限序数, 且结论对一切 `xi lt beta` 成立. 任取 `gamma lt beta`, 则由上确界性质 `alpha + beta` `= "sup"{alpha + xi: xi lt beta}` `ge alpha + gamma`. 为了将上式加强为严格的不等式, 注意到 `beta` 为极限序数, 所以 `gamma^+ lt beta`, 因此 `alpha + beta ge alpha + gamma^+ gt alpha + gamma`.
    再证 `lArr`. 假设 `alpha + beta gt alpha + gamma`, 那么不能有 `beta = gamma`, 否则 `alpha + beta = alpha + gamma`; 也不能有 `beta lt gamma`, 否则 `alpha + beta lt alpha + gamma`. 所以 `beta gt gamma`.
  4. `rArr` 显然; 下证 `lArr`. 假设 `alpha + beta = alpha + gamma`, 那么不能有 `beta lt gamma`, 否则 `alpha + beta lt alpha + gamma`; 同理不能有 `beta gt gamma`, 所以 `beta = gamma`.

序数加法一般不满足右消去律, 比如 `1 + omega = 2 + omega = omega`.

    序数加法和 sup 的性质 设 `alpha` 是任意序数,
  1. 设集合 `S` 的元素都是序数, `"sup"S` 是后继序数, 则 `"sup"S in S`.
  2. 若 `beta gt 0`, 则 `beta` 是极限序数当且仅当 `alpha + beta` 是极限序数.
  3. 若 `beta gt 0`, 则 `alpha + "sup"beta = "sup"(alpha + beta)`.
  4. 设非空集合 `S` 的元素都是序数, 则 `alpha + "sup"S = "sup"(alpha + S)`, 这里 `alpha + S := {alpha + beta: beta in S}`.
  1. 设 `"sup"S = alpha^+`, 由上确界性质知存在 `beta in S` 使得 `alpha lt beta le alpha^+`, 于是 `beta = alpha^+`.
    逆命题不成立. 如 `S = {omega}`, `"sup"S = omega in S`, 但 `omega` 是极限序数.
  2. 设 `beta = gamma^+` 是后继, 于是 `alpha + beta = (alpha + gamma)^+` 也是后继. 现在设 `beta` 是极限序数, 下证 `alpha + beta` 是极限序数. 反设 `alpha + beta = "sup"{alpha + xi: xi lt beta}` 是后继序数, 则由 1. 知 `alpha + beta in {alpha + xi: xi lt beta}`, 即存在 `xi lt beta` 使得 `alpha + beta = alpha + xi`. 由左消去律知道 `beta = xi`, 矛盾.
    1. 若 `beta = gamma^+`, 则 `"sup" beta = gamma`. 于是 `alpha + beta` `= alpha + gamma^+` `= (alpha + gamma)^+` `= (alpha + "sup"beta)^+`. 两边同时取上确界得到 `alpha + "sup"beta` `= "sup"(alpha + beta)`.
    2. 若 `beta` 是极限序数, 则 `"sup"beta = beta`, 由定义 `alpha + "sup" beta = alpha + beta`, 又由 2. 知 `alpha + beta` 是极限序数, 故 `alpha + beta = "sup"(alpha + beta)`.
    4. 记 `gamma := "sup"S`.
    1. 若 `gamma in S`, 则对任意 `beta in S` 有 `beta le gamma`, 从而 `alpha + beta le alpha + gamma`, 即 `alpha + gamma = "sup"(alpha + S)`.
    2. 若 `gamma !in S`, 由 1. 知道 `gamma` 是极限序数, 由定义 `alpha + gamma = "sup"{alpha + beta: beta lt gamma}`. 下证它等于 `"sup"(alpha + S)`.
    3. 记 `左 := {alpha + beta: beta lt gamma}`, `右 := alpha + S`. 对任意 `beta in S` 有 `beta lt gamma`, 所以右 `sube` 左, `"sup" 右 le "sup" 左`.
    4. 对任意 `beta lt gamma`, 由上确界性质, 存在 `xi in S` 使得 `beta lt xi`, 于是 `alpha + beta lt alpha + xi`, `"sup" 左 le "sup" 右`.

加法结合律 `(alpha + beta) + gamma = alpha + (beta + gamma)`.

    对 `gamma` 归纳:
  1. `gamma = 0` 时结论成立;
  2. 设结论对 `gamma` 成立, 则对 `gamma^+` 有 `(alpha + beta) + gamma^+`
    `= ((alpha + beta) + gamma)^+`
    `= (alpha + (beta + gamma))^+`
    `= alpha + (beta + gamma)^+`
    `= alpha + (beta + gamma^+)`.
  3. 若 `gamma` 是极限序数, 且对一切 `xi lt gamma` 结论成立, 则 `(alpha + beta) + gamma`
    `= "sup"{(alpha+beta) + xi: xi lt gamma}`
    `= "sup"{alpha + (beta+xi): xi lt gamma}`
    `= alpha + "sup"{beta + xi: xi lt gamma}`
    `= alpha + (beta + gamma)`.

序数的减法 设序数 `beta le alpha`, 则存在唯一序数 `gamma` 使得 `beta + gamma = alpha`. 于是可记 `alpha - beta := gamma`.

  1. 存在性. `beta = alpha` 时取 `gamma = 0` 即可. 下设 `alpha gt beta ge 0`, 对 `alpha` 使用超穷递归:
    1. 若对序数 `alpha` 结论成立, 则对序数 `alpha^+` 和任意 `beta lt alpha^+` (即 `beta le alpha`) 有 `beta + gamma^+` `= (beta + gamma)^+` `= alpha^+`.
    2. 若 `alpha` 是极限序数, 且对一切 `xi lt alpha` 结论成立, 则对任意 `beta lt alpha`, `beta + "sup"{gamma: beta + gamma = xi, xi lt alpha}` `= "sup"{beta + gamma: beta + gamma = xi, xi lt alpha}` `= "sup"{xi: xi lt alpha}` `= alpha`.
  2. 唯一性. 这等价于序数加法的左消去律.

大序数初探*

[来自：core.exe@知乎]

    序数 `epsi_alpha` 和 `zeta_alpha`
  1. 我们知道, `omega^2 = omega * omega = "sup"{omega * n: n lt omega}`.
    `omega^n = omega^(n-1) * omega = "sup"{omega^(n-1) * k: k lt omega}`.
     如果对映射 `alpha mapsto omega^alpha` 进行迭代: `omega^omega = "sup"{omega^n: n lt omega}.
    `omega^(omega^omega) = "sup"{omega^(omega^n): n lt omega}`.     最终 `epsi_0 := "sup"{1, omega, omega^omega, omega^(omega^omega), cdots}`. 它是满足等式 `omega^alpha = alpha` 的第一个序数.
  2. `epsi_0+1` 并不是 `alpha mapsto omega^alpha` 的不动点, 依然可以取指数使它增大: `epsi_1 := "sup"{epsi_0+1, omega^(epsi_0+1), omega^(omega^(epsi_0+1)), cdots}`. `epsi_1` 是继 `epsi_0` 后满足等式 `omega^alpha = alpha` 的下一个序数. 现在对一切序数 `alpha`, 定义 `epsi_alpha := { "sup"{epsi_beta+1, omega^(epsi_beta+1), omega^(omega^(epsi_beta+1)), cdots}, if alpha = beta+1; "sup"{epsi_beta: beta lt alpha}, if alpha 是极限序数; :} 一些例子: `epsi_omega = "sup"{epsi_0, epsi_1, epsi_2, cdots}`,
    `epsi_(omega^omega) = "sup"{epsi_omega, epsi_(omega^2), epsi_(omega^3), cdots}`,
    `epsi_(epsi_0) = "sup"{epsi_omega, epsi_(omega^omega), epsi_(omega^(omega^omega)), cdots }`.
  3. 我们知 `epsi_alpha` 是比指数 `omega^alpha` 增长更快的一种运算. 对下标 `alpha` 进行迭代就得到 `zeta_0 := "sup"{epsi_0, epsi_(epsi_0), epsi_(epsi_(epsi_0)), cdots }`. 这不仅是 `alpha mapsto omega^alpha` 的不动点, 也是 `alpha mapsto epsi_alpha` 的不动点.
  4. 还存在比 `zeta_alpha` 更高的层级, 其思路是使用后继跳出不动点, 然后不断迭代达到下一个不动点. `zeta` 层级之后分别是 `eta`, `xi`... 等等, 但希腊字母是有限个的, 这促使我们寻找一个统一的定义. 注意到 `epsi_alpha` 是迭代 `alpha mapsto omega^alpha` 的第 `alpha` 个不动点, `zeta_alpha` 是迭代 `alpha mapsto epsi_alpha` 的第 `alpha` 个不动点. 因此我们寻求一列函数 `f_n(alpha)`, 其中 `f_(n+1)(alpha)` 是 `f_n` 的第 `alpha` 个不动点:
    Veblen 函数 定义为二元函数 `varphi(x, y)`, `x, y` 为序数. 它满足:
  1. `varphi(0, alpha) := omega^alpha`, `varphi(1, alpha) := epsi_alpha`, `varphi(2, alpha) := zeta_alpha`.
  2. 考虑第 `alpha` 层的迭代 `varphi_alpha := beta mapsto varphi(alpha, beta)`. `varphi(alpha+1, 0)` 定义为 `varphi_alpha` 的第 0 个不动点. `varphi(alpha+1, beta+1)` 定义为 `varphi(alpha+1, beta)` 之后, `varphi_alpha` 的下一个不动点. 写为公式就是 `varphi(alpha+1, 0) := "sup"{varphi(alpha, 0)+1, varphi(alpha, varphi(alpha, 0)+1), cdots}`,
    `varphi(alpha+1, beta+1) := "sup"{varphi(alpha+1, beta)+1, varphi(alpha, varphi(alpha+1, beta)+1), cdots}`,
    `varphi(alpha, beta) := "sup"{varphi(alpha, gamma): gamma lt beta}`, 如果 `beta` 为极限序数.
  3. 对于第一个变元 `alpha` 是极限序数的情形, 定义 `varphi(alpha, 0) := "sup"{varphi(gamma, 0): gamma lt alpha}`,
    `varphi(alpha, beta+1) := "sup"{varphi(gamma, varphi(alpha, beta)+1), gamma lt alpha}`.
  4. 最后, 还可以考虑第一个变元的迭代 `alpha mapsto varphi(alpha, 0)`, 它的第 0 个不动点是 `Gamma_0 := "sup"{0, varphi(0, 0), varphi(varphi(0, 0), 0), cdots}`. 这也是 Veblen 函数的极限.

选择公理

[来自李文威《代数学方法》] [参考 芷雨Chira@知乎]

在定义自然数集时, 我们用公理规定 "存在归纳集", 然后从中取出了一个归纳集 `A`. 一般地, 给定有限个非空集合, 我们可以分别从中取出一个元素, 作为它所在集合的代表. 然而, 当这样的非空集合有无限个时, 以上做法失效: 因为公理和推理规则只能应用有限次. 一个自然的想法是, 对于无限个非空集合, 也应能取出它们的代表元, 这就是选择公理.

选择公理 设集合 `X` 的每个元素皆非空, 则存在函数 `g: X to uuu X` 使得 `AA x in X`, `g(x) in x`. 这个函数称为选择函数.

对任意良序集 `P`, 存在唯一的序数 `alpha` 与它同构.

不妨设 `P != O/`, 因为 `P` 是集合, 然而不存在无所不包的集合, 故可选取 `u !in P`. 下面利用超穷递归定义一族元素 `A_alpha`, 其中 `alpha in bb(On)`:
首先由于 `P` 是良序集, 可以令 `A_0 := min(P)`, 这里 `min` 表示取出一个极小元. 对任意序数 `alpha`, 记 `P_alpha := { A_beta: beta lt alpha }`, 对应于 `alpha` 的前段. 递归定义 `A_alpha := { min(P - P_alpha), if P_alpha subne P; u, if P_alpha = P; :}` 由于 `P` 是集合, 必存在最小序数 `theta` 使得 `A_theta = u`, 否则 `bb(On)` 可以嵌入 `P`, 引起矛盾. 于是 `A_alpha mapsto alpha` 是 `P` 到 `{beta: beta lt theta} = theta` 之间的同构.

我们称 `P` 的序型是 `alpha`. 因此序数是良序集的代表, 借助序数我们可以了解良序集的结构.

下面的良序定理和 Zorn 引理是选择公理的等价命题:

Zermelo 良序定理 (1904) 对任意集合 `S`, 都存在 `S` 上的二元关系 `R`, 使得 `R` 是 `S` 上的良序.

事实上, 只要把证明良序集与某个序数同构时的函数 `min` 换成选择公理赋予我们的选择函数 `g`, 就得到 `S` 与某个序数 `theta` 之间的双射, 从而导出 `S` 上的良序.

    Zorn 引理 设 `P` 为非空偏序集, 它的全序子集称为链. 我们有:
  1. 若 `P` 中每个链都有上界, 则 `P` 有极大元;
  2. 若 `P` 中每个链都有下界, 则 `P` 有极小元.
    只证 1. 反设 `P` 不含极大元. 取 `A_0 in P`, 运用超穷递归定义 `A_alpha` 如下: 设 `P_alpha := {A_beta: beta lt alpha}` 已经被定义, 且满足 `gamma lt beta rArr A_gamma lt A_beta`. 于是 `P_alpha` 是 `P` 的一条链.
  1. 若 `alpha = gamma + 1`, 由于 `P` 无极大元, 故可以选取 `A_alpha in P` 使得 `A_alpha gt A_gamma`.
  2. 若 `alpha` 为极限序数, 由题设, 链 `P_alpha` 有上界, 故可以选取一个上界 `A_alpha`. 我们证明对任意 `beta lt alpha` 有 `A_beta lt A_alpha`. 事实上若存在一个 `A_beta = A_alpha`, 则其后继 `A_(beta^+) gt A_beta = A_alpha`, 与 `A_alpha` 是 `P_alpha` 的上界矛盾.
    3. 上述步骤中发生了无数次选取的操作, 这由选择公理保证. 由上述构造知真类 `bb(On)` 可以嵌入 `P`, 从而矛盾.