降鏈條件
數學上,偏序集 P適合 升鏈條件,若任意 P的元素的升鏈 a≤ a≤...最終固定,就是說存在正整數 n,使得對所有 m> n,有 a= a。類似地, P適合 降鏈條件,若任意 P的元素的降鏈 a≥ a≥...最終固定(就是說不存在無窮降鏈)。
P的升鏈條件等價於 最大條件:所有 P的非空子集都有極大元。類似地,降鏈條件等價於 最小條件:所有 P的非空子集都有極小元。
所有有限偏序集都適合升鏈和降鏈條件。適合降鏈條件的全序集稱為良序集。
無窮降鏈
給定帶有偏序≤的一個集合 S, 無窮降鏈是鏈 V,就是說在其上≤定義了全序的 S的子集,使得 V沒有最小元素,也就是元素 m它使得對於在 V中所有元素 n有著 m≤ n。
作為例子,在整數的集合中,鏈−1, −2, −3, ...是無窮降鏈,但是在自然數上沒有無窮降鏈,所有自然數的鏈都有一個極小元素。
如果偏序集合不包含任何無窮降鏈,則稱它為良基的。沒有無窮降鏈的全序集合是良序的。
良基
在數學中,類 X上的一個二元關係 R被稱為是 良基的,若且唯若所有 X的非空子集都有一個 R-極小元;就是說,對 X的每一個非空子集 S,存在一個 S中的元素 m使得對於所有 S中的 s,二元組 ( s, m) 都不在 R中。
等價的說,假定某種選擇公理,一個二元關係稱為是良基的,若且唯若它不包含可數的無窮降鏈,也就是說不存在 X的元素的無窮序列 x, x, x, ...使得對所有的自然數 n有著 x R x。
在序理論中,一個偏序關係稱為是良基的,若且唯若它對應的嚴格偏序是良基的。如果這個序還是全序,那么此時稱這個序為良序。
在集合論中,一個集合 x稱為是一個 良基集合,如果集成員關係在 x的傳遞閉包上是良基的。策梅洛-弗蘭克爾集合論中的正則公理,就是斷言所有的集合都是良基的。
良序
在數學中,集合 S上的 良序關係(或 良序)需要滿足:
1.是在 S上的全序關係
2. 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,∈)。