良基关系

Confusion grey.svg提示：此条目的主题不是良序关系。

在数学中，类 X 上的一个二元关系 R 被称为是良基的，当且仅当所有 X 的非空子集都有一个 R-极小元；就是说，对 X 的每一个非空子集 S，存在一个 S 中的元素 m 使得对于所有 S 中的 s，二元组 (s,m) 都不在 R 中。

等价的说，假定某种选择公理，一个二元关系称为是良基的，当且仅当它不包含可数的无穷降链，也就是说不存在 X 的元素的无穷序列 x0, x1, x2, ...使得对所有的自然数 n 有着 xn+1 R xn。

在序理论中，一个偏序关系称为是良基的，当且仅当它对应的严格偏序是良基的。如果这个序还是全序，那么此时称这个序为良序。

在集合论中，一个集合 x 称为是一个良基集合，如果集成员关系在 x 的传递闭包上是良基的。策梅洛-弗兰克尔集合论中的正则公理，就是断言所有的集合都是良基的。

归纳和递归

良基关系之所以引人关注的一个重要原因是因为超限归纳法的一个版本可以应用到它上面。(X, R) 是良基关系，并且 P(x) 是 X 的元素的某种属性，你期望 P(x) 对 X 的所有元素都成立，那么良基关系有能力做到这一点：

如果 x 是 X 的一个元素并且对所有的满足 y R x 的 y 都有 P(y) 为真，那么 P(x) 也一定为真。

和归纳法类似，良基关系可以支持通过超限递归来构造对象。令 (X, R) 是一个良基的二元关系，F 为一个函数，且对所有的 x ∈ X 和 X 上的每一个偏函数 g 有 F 赋值于一个对象 F(x, g)，那么存在唯一的一个函数 G 满足对任意的 x ∈ X，

 。

这就是说，如果我们想构造一个 X 上的函数 G，我们可以通过满足 y R x 的 G(y) 的值来定义 G(x)。

最为一个例子，考虑一个良基关系 (N, S)，此处 N 为自然数集合，且 S 是后继函数 x → x+1 的图像。S 上的归纳就是通常的数学归纳法，而 S 上的递归给出了原始递归。如果我们考虑序关系 (N, <)，我们就得到一个完全归纳法和一个（course-of-values recursion）。命题 (N, <) 是良基的也被称为良序原理。

还有其他一些令人感兴趣的良基归纳的例子。当良基关系是通常的序数上的序关系，那么对应的归纳法是超限归纳法；当良基集合是递归定义的数据结构，那么对应的归纳法称为结构归纳法；当良基关系是全类上的集合成员关系，对应的归纳法称为∈归纳法。请参阅相关主题的论文来获得更多的细节。

例子

下面给出一些是良基关系但不是全序关系的例子：

  • 正整数 {1, 2, 3, ...}，及其这样定义的一个序关系：a < b 当且仅当 a 整除 b且a ≠ b。
  • 一个固定词表上的所有的有限长字符串，及其这样定义的一个序关系：s < t当且仅当 s 是 t 的一个真子串。
  • 自然数的有序对的集合 N × N，及其这样定义的一个序关系：(n1, n2) < (m1, m2) 当且仅当n1 < m1且n2 < m2。
  • 一个固定词表上的的所有正则表达式，及其这样定义的一个序关系：s < t 当且仅当 s 是 t 的真子表达式。
  • 任何以集合为元素的类，及其这样定义的一个关系：a R b 当且仅当 a 是 b 的一个元素（假定正则公理成立）。
  • 任何一个有限的有向无环图，及其这样定义的一个关系：a R b 当且仅当存在一个有向边 a→b。

其他性质

如果 (X, <) 是良基关系并且 x 是 X 中的一个元素，那么以 x 为始的降链都是有限长的，但是这不意味着它们的长度必定是有界的。请考虑下面的例子：

令 X 为全体正整数和一个新元素 ω 的并，ω 比任何整数都要大。这样 X 是一个良基集合，但是存在以 ω 为始的降链其长度可以任意（有限的）大：对任意的 n，链 ω, n-1, n-2, ..., 2, 1 的长度为 n。

莫斯托夫斯基塌陷引理蕴涵集合成员关系是一个普遍(universal)的良基关系：对任何类 X 上的类集的（set-like）良基关系 R，存在一个类 C 满足 (X,R) 同构于 (C,∈)。

参考资料

  • Just, Winfried and Weese, Martin, Discovering Modern Set theory. I, American Mathematical Society (1998) ISBN 0821802666.