版权归原作者所有,如有侵权,请联系我们

[科普中国]-良基关系

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

良基关系(well-founded relation)是一种特殊的二元关系,是良序关系中抽去全序的成分后获得的一种二元关系。设R为集合(或类)U上的一个二元关系,若U的每个非空子集均有R最小元,则称R为U上的一个良基关系,亦即R为U上的良基关系,当且仅当对U的每个非空子集x,存在x的元素y,使得对任何z∈U,〈z,y〉均不属于R。若U为集合,则称〈U,R〉为良基结构;若A为真类,通常要求U的每个元素关于R的初始段必须为一集合。良序关系一定为良基关系,反之则不成立。例如,在ZF公理系统中,由正则公理知,∈关系为集合论全域V上的良基关系,但不是良序关系。从直观上讲,被良基化的集合或类,可以通过其上的良基关系对其元素进行分层。事实上,若R为U上的一个良基关系,则可利用良基关系上的超穷递归原理定义U中每个元素x关于R的秩rank(x,U,R)=sup{rank(y,U,R)+1:yRx∧y∈U}。如果U可传,R=∈,则rank(x,U,∈)恰好为x的秩rank(x)1。

基本介绍良基关系是集合上的一种重要关系,它是策梅洛(E.F.F.Zermelo)于1935年提出的。设R是集合A上的一个关系,若A的任何非空子集B都有R极小元,则称R是A的良基关系。A是关于R的良基集,记为wfR(A)。A上的任何良序关系都是A上的良基关系,但A上的良基关系不一定是A上的良序关系。如果A对于关系R不但是良基的,而且是全序的,那么A是良序集,例如,自然数集{1,2,…}对小于关系既是良序的也是良基的,如果有限偏序集的哈塞图是有分叉的伪树(如图1),则它是良基的但不是良序的。在良基集wfR(A)中,不存在无穷的单调递降序列

{an}n∈w:a0R-1a1R-1a2R-1a3R-1…

若定义良基集到序数集内一个映射fR:A→ord,使得当a∈A时,

fR(a)=sup{fR(b)+1|(b∈A∧bRa)},

且fR的值域是一个序数,则fR是A到ord内的一个确定单调增映射。fR的值域称为R的长度,即

例图中R的长度为62。

相关定理及其证明定理 —关系R为良基的的,当且仅当不存在具有定义域为ω的函数f,使得对于每一n∈ω,都有R(f(n+),f(n))。

人们也称这一序列:

...,f(n+),f(n),...,f(1),f(0) (1)

为一降链,并且对于上述f,我们令

D:={f(n)|n∈ω} , (2)

并称这一D为f|d(R)的一降链子集合。

证明:假定一关系R不是良基的,那么存在一非空集合S,它没有R极小!元素,亦即

直观地讲,因为S不空,任取 ,由(3)就有a1,使得;R(a1,a0)成立,又由于 ,由(3)就有 ,使得R(a2,a1)成立。这里可以取a2不同a0,因为由S中没有R的极小元,那么,S1=S-{a0}中也没有R极小元,把S1应用于(3)即得 ,把这—·过程无限地作下去,即得到下述无穷序列;

a0,a1,a2,... (4)

并且有:对于每一n∈ω,都有

或者记做

这样我们可以令:

由(5)与(6),即得欲证结果。

反之,若存在一函数 ,我们令:

不难证明由(7)给出的集合S中没有R极小元。

注记:在上述证明中,我们说“把一过程无限地进行下去,即得到下述无穷序列"(指获得(4),这句话包含着有无穷多情形,并且在每个种情形下都需要由a去找一个b,使得bRa,我们知道虽然 ,但是(3)并未给出去选择y的方案。也就是说可能有许多元甚至无穷多元y满足xRx,根据什么原则去挑选唯一的元素呢?人们已经证明仅在ZF系统中是不可能实现的,它要求使用选择公理,不过,这里仅需用选择公理的一种较弱的形式称之为依赖选择原则,它意味着允许人们依次进行ω次的选择。

依赖选择原则(Bernays,1942):如果T是在不空集合S上的一个关系,使得对于每

一x∈S,都存在y∈S有T(x、y),那么就存在一序列:

使得

成立。

现在我们令依赖选择原则中的T(x、y)为

据依赖选择原则,由(3)即可获得(4)。

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学