良基關係

良基關係(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)。

基本介紹

• 中文名：良基關係
• 外文名：well-founded relation
• 所屬學科：數學
• 所屬問題：集合論
• 簡介：一種特殊的二元關係
• 提出者：策梅洛(E.F.F.Zermelo)

基本介紹

良基關係是集合上的一種重要關係，它是策梅洛(E.F.F.Zermelo)於1935年提出的。設R是集合A上的一個關係，若A的任何非空子集B都有R極小元，則稱R是A的良基關係。A是關於R的良基集，記為wf_R(A)。A上的任何良序關係都是A上的良基關係，但A上的良基關係不一定是A上的良序關係。如果A對於關係R不但是良基的，而且是全序的，那么A是良序集，例如，自然數集{1，2，…}對小於關係既是良序的也是良基的，如果有限偏序集的哈塞圖是有分叉的偽樹(如圖1)，則它是良基的但不是良序的。在良基集wf_R(A)中，不存在無窮的單調遞降序列

{a_n}_n∈w：a₀R^-1a₁R^-1a₂R^-1a₃R^-1…

若定義良基集到序數集內一個映射f_R：A→ord，使得當a∈A時，

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

且f_R的值域是一個序數，則f_R是A到ord內的一個確定單調增映射。f_R的值域稱為R的長度，即

例圖中R的長度為6。

圖1 良基偽樹

相關定理及其證明

定理 —關係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)就有a₁，使得；R(a₁，a₀)成立，又由於 ，由(3)就有 ，使得R(a₂，a₁)成立。這裡可以取a₂不同a₀，因為由S中沒有R的極小元，那么，S₁=S-{a₀}中也沒有R極小元，把S₁套用於(3)即得 ，把這—·過程無限地作下去，即得到下述無窮序列；

a₀，a₁，a₂，... (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)。