降鏈(descending chain)是指任意P的元素關係為a1 ≥ a2 ≥ ...的偏序集。若任意P的元素的升鏈a1 ≥ a2 ≥ ...最終固定,就是說存在正整數n,使得對所有m>n,有am = an,為降鏈條件。降鏈條件等價於最小條件:所有P的非空子集都有極小元。
基本介紹
- 中文名:降鏈
- 外文名:descending chain
- 是指:a1≥a2≥...
- 涉及學科:離散數學
- 相關:降鏈條件
- 對立:升鏈
降鏈條件,無窮降鏈,良基,良序,性質,
降鏈條件
數學上,偏序集P適合升鏈條件,若任意P的元素的升鏈a1≤a2≤...最終固定,就是說存在正整數n,使得對所有m>n,有am=an。類似地,P適合降鏈條件,若任意P的元素的降鏈a1≥a2≥...最終固定(就是說不存在無窮降鏈)。
P的升鏈條件等價於最大條件:所有P的非空子集都有極大元。類似地,降鏈條件等價於最小條件:所有P的非空子集都有極小元。
無窮降鏈
如果偏序集合不包含任何無窮降鏈,則稱它為良基的。沒有無窮降鏈的全序集合是良序的。
良基
良序
1.是在S上的全序關係
等價的說,良序是良基的線序。集合S和這個良序關係一起就叫做良序集合。
粗略的說,良序集合的排序方式,使得我們可以逐次考慮一個它的元素,而在還沒有檢視完所有的元素的任何時候,總是有一個唯一的下一個元素可考慮。
性質
如果 (X, <) 是良基關係並且x是X中的一個元素,那么以x為始的降鏈都是有限長的,但是這不意味著它們的長度必定是有界的。請考慮下面的例子:
令X為全體正整數和一個新元素 ω 的並,ω 比任何整數都要大。這樣X是一個良基集合,但是存在以 ω 為始的降鏈其長度可以任意(有限的)大:對任意的 n,鏈 ω,n-1,n-2, ..., 2, 1 的長度為 n。
Mostowski崩塌引理蘊涵集合成員關係是一個普遍(universal)的良基關係:對任何類X上的類集的(set-like)良基關係R,存在一個類C滿足 (X,R) 同構於 (C,∈)。