查看“︁良基关系”︁的源代码

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

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

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

在[[集合论]]中，一个集合 ''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''，
:<math>G(x)=F(x,G\vert_{\{y: y\,R\,x\}})</math>。
这就是说，如果我们想构造一个 ''X'' 上的函数 ''G''，我们可以通过满足 ''y R x'' 的 ''G''(''y'') 的值来定义 ''G''(''x'')。

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

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

==例子==

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

* 正整数 {1, 2, 3, ...}，及其这样定义的一个序关系：''a'' < ''b'' [[当且仅当]] ''a'' [[整除]] ''b''且''a'' ≠ ''b''。
* 一个固定词表上的所有的有限长[[字符串]]，及其这样定义的一个序关系：''s'' < ''t''当且仅当 ''s'' 是 ''t'' 的一个真子串。
* 自然数的有序对的集合 '''N''' × '''N'''，及其这样定义的一个序关系：(''n''<sub>1</sub>, ''n''<sub>2</sub>) < (''m''<sub>1</sub>, ''m''<sub>2</sub>) 当且仅当''n''<sub>1</sub> < ''m''<sub>1</sub>且''n''<sub>2</sub> < ''m''<sub>2</sub>。
* 一个固定词表上的所有[[正则表达式]]，及其这样定义的一个序关系：''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.

[[Category:良基性|*]]
[[Category:数学关系]]