[科普中國(guó)]-良基關(guān)系

良基關(guān)系(well-founded relation)是一種特殊的二元關(guān)系，是良序關(guān)系中抽去全序的成分后獲得的一種二元關(guān)系。設(shè)R為集合(或類)U上的一個(gè)二元關(guān)系，若U的每個(gè)非空子集均有R最小元，則稱R為U上的一個(gè)良基關(guān)系，亦即R為U上的良基關(guān)系，當(dāng)且僅當(dāng)對(duì)U的每個(gè)非空子集x，存在x的元素y，使得對(duì)任何z∈U，〈z，y〉均不屬于R。若U為集合，則稱〈U，R〉為良基結(jié)構(gòu)；若A為真類，通常要求U的每個(gè)元素關(guān)于R的初始段必須為一集合。良序關(guān)系一定為良基關(guān)系，反之則不成立。例如，在ZF公理系統(tǒng)中，由正則公理知，∈關(guān)系為集合論全域V上的良基關(guān)系，但不是良序關(guān)系。從直觀上講，被良基化的集合或類，可以通過(guò)其上的良基關(guān)系對(duì)其元素進(jìn)行分層。事實(shí)上，若R為U上的一個(gè)良基關(guān)系，則可利用良基關(guān)系上的超窮遞歸原理定義U中每個(gè)元素x關(guān)于R的秩rank(x，U，R)=sup{rank(y，U，R)+1：yRx∧y∈U}。如果U可傳，R=∈，則rank(x，U，∈)恰好為x的秩rank(x)1。

基本介紹良基關(guān)系是集合上的一種重要關(guān)系，它是策梅洛(E.F.F.Zermelo)于1935年提出的。設(shè)R是集合A上的一個(gè)關(guān)系，若A的任何非空子集B都有R極小元，則稱R是A的良基關(guān)系。A是關(guān)于R的良基集，記為wfR(A)。A上的任何良序關(guān)系都是A上的良基關(guān)系，但A上的良基關(guān)系不一定是A上的良序關(guān)系。如果A對(duì)于關(guān)系R不但是良基的，而且是全序的，那么A是良序集，例如，自然數(shù)集{1，2，…}對(duì)小于關(guān)系既是良序的也是良基的，如果有限偏序集的哈塞圖是有分叉的偽樹(如圖1)，則它是良基的但不是良序的。在良基集wfR(A)中，不存在無(wú)窮的單調(diào)遞降序列

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

若定義良基集到序數(shù)集內(nèi)一個(gè)映射fR：A→ord，使得當(dāng)a∈A時(shí)，

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

且fR的值域是一個(gè)序數(shù)，則fR是A到ord內(nèi)的一個(gè)確定單調(diào)增映射。fR的值域稱為R的長(zhǎng)度，即

例圖中R的長(zhǎng)度為62。

相關(guān)定理及其證明定理 —關(guān)系R為良基的的，當(dāng)且僅當(dāng)不存在具有定義域?yàn)棣氐暮瘮?shù)f，使得對(duì)于每一n∈ω，都有R(f(n+)，f(n))。

人們也稱這一序列：

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

為一降鏈，并且對(duì)于上述f，我們令

D：={f(n)|n∈ω} ， (2)

并稱這一D為f|d(R)的一降鏈子集合。

證明：假定一關(guān)系R不是良基的，那么存在一非空集合S，它沒(méi)有R極小!元素，亦即

直觀地講，因?yàn)镾不空，任取 ，由(3)就有a1，使得；R(a1，a0)成立，又由于 ，由(3)就有 ，使得R(a2，a1)成立。這里可以取a2不同a0，因?yàn)橛蒘中沒(méi)有R的極小元，那么，S1=S-{a0}中也沒(méi)有R極小元，把S1應(yīng)用于(3)即得 ，把這—·過(guò)程無(wú)限地作下去，即得到下述無(wú)窮序列；

a0，a1，a2，... (4)

并且有：對(duì)于每一n∈ω，都有

或者記做

這樣我們可以令：

由(5)與(6)，即得欲證結(jié)果。

反之，若存在一函數(shù) ，我們令：

不難證明由(7)給出的集合S中沒(méi)有R極小元。

注記：在上述證明中，我們說(shuō)“把一過(guò)程無(wú)限地進(jìn)行下去，即得到下述無(wú)窮序列"(指獲得(4)，這句話包含著有無(wú)窮多情形，并且在每個(gè)種情形下都需要由a去找一個(gè)b，使得bRa，我們知道雖然 ，但是(3)并未給出去選擇y的方案。也就是說(shuō)可能有許多元甚至無(wú)窮多元y滿足xRx，根據(jù)什么原則去挑選唯一的元素呢?人們已經(jīng)證明僅在ZF系統(tǒng)中是不可能實(shí)現(xiàn)的，它要求使用選擇公理，不過(guò)，這里僅需用選擇公理的一種較弱的形式稱之為依賴選擇原則，它意味著允許人們依次進(jìn)行ω次的選擇。

依賴選擇原則(Bernays，1942)：如果T是在不空集合S上的一個(gè)關(guān)系，使得對(duì)于每

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

使得

成立。

現(xiàn)在我們令依賴選擇原則中的T(x、y)為

據(jù)依賴選擇原則，由(3)即可獲得(4)。

本詞條內(nèi)容貢獻(xiàn)者為:

胡建平 - 副教授 - 西北工業(yè)大學(xué)