良基关系

维基百科,自由的百科全书
跳转至: 导航搜索

在数学中,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的所有元素都成立,那么良基关系有能力做到这一点:

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

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

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

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

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

例子[编辑]

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

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

其他性质[编辑]

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

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

Mostowski崩塌引理蕴涵集合成员关系是一个普遍(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.