-
良基關係
鎖定
良基關係(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為良基的的,當且僅當不存在具有定義域為ω的函數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極小!元素,亦即
a0,a1,a2,... (4)
並且有:對於每一n∈ω,都有
反之,若存在一函數
,我們令:
註記:在上述證明中,我們説“把一過程無限地進行下去,即得到下述無窮序列"(指獲得(4),這句話包含着有無窮多情形,並且在每個種情形下都需要由a去找一個b,使得bRa,我們知道雖然
,但是(3)並未給出去選擇y的方案。也就是説可能有許多元甚至無窮多元y滿足xRx,根據什麼原則去挑選唯一的元素呢?人們已經證明僅在ZF系統中是不可能實現的,它要求使用選擇公理,不過,這裏僅需用選擇公理的一種較弱的形式稱之為依賴選擇原則,它意味着允許人們依次進行ω次的選擇。
依賴選擇原則(Bernays,1942):如果T是在不空集合S上的一個關係,使得對於每
一x∈S,都存在y∈S有T(x、y),那麼就存在一序列:
現在我們令依賴選擇原則中的T(x、y)為