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

[[分类:序理论]]{{DEFAULTSORT:liang2ji1guan1xi5}}
{{#seo:
|keywords=良基关系
|description=本文介绍良基关系的定义、性质和应用，包括良基关系作为不允许无穷下降链的二元关系特征，以及在数学归纳法、递归定义中的重要性。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-02-24
}}
{{InfoBox
|name=良基关系
|eng_name=well-founded relation
}}
'''良基关系'''('''well-founded relation''')是指一个二元[[关系]]中，任何一个非空子集中都存在[[极小元]]。

== 定义 ==

对集合 <math>A</math> 上的二元关系 <math>R</math> ，若 <math>(\forall S \subseteq A) (S\neq\varnothing \rightarrow (\exists s \in S) (\forall s' \in S) (s'\neq s \rightarrow \lnot s' R s))</math> ，称 <math>R</math> 是一个'''良基关系'''('''well-founded relation''')，也称这一关系是'''良基的'''('''well-founded''')。

注：根据是否自反，也有的定义不要求 <math>s' \neq s</math> 。

=== 归纳定义 ===

<math>A</math> 中满足下列条件（可 <math>R</math>-归纳）的子集 <math>S</math> 只有 <math>A</math> 本身。

<math>(\forall a\in A) ((\forall t\in A) (t R a \rightarrow t\in S) \rightarrow a \in S)</math>

=== 下降链定义 ===

关系 $R$ 是良基的当且仅当不存在无穷下降链 <math>a_0, a_1, a_2, \cdots</math> 满足 <math>x_{n+1} R x_n</math> 。

== 性质 ==

* 基本特征
** 良基关系不允许无穷下降链；
** 每个非空子集都有极小元；
** 良基关系不一定是传递的、自反的或反对称的。

== 关联 ==

* 每个[[良序]]都是良基关系。
* 每个[[严格偏序]]如果是良基的，则称为'''良基偏序'''。

== 关联概念 ==

=== 良基归纳法 ===

设 <math>R</math> 是集合 <math>A</math> 上的良基关系， <math>P</math> 是 <math>A</math> 上的性质。
如果有：
<math>\forall (a \in A) ((\forall b \in A \ (b R a \rightarrow P(b))) \rightarrow P(a))</math>
则可推出 <math>(\forall a \in A) (P(a))</math> 成立。

=== 良基递归 ===

设 <math>R</math> 是集合 <math>A</math> 上的良基关系，可以在 <math>A</math> 上递归定义函数 <math>f</math> ：
<math>f(a) = G(a, f_{|\{b \in A \mid b R a\}})</math>
其中 <math>G</math> 是给定的函数。


{{关系}}