降鏈

降鏈(descending chain)是指任意P的元素關係為a1 ≥ a2 ≥ ...的偏序集。若任意P的元素的升鏈a1 ≥ a2 ≥ ...最終固定,就是說存在正整數n,使得對所有m>n,有am = an,為降鏈條件。降鏈條件等價於最小條件:所有P的非空子集都有極小元。

基本介紹

  • 中文名:降鏈
  • 外文名:descending chain
  • 是指:a1≥a2≥...
  • 涉及學科:離散數學
  • 相關:降鏈條件
  • 對立:升鏈
降鏈條件,無窮降鏈,良基,良序,性質,

降鏈條件

數學上,偏序集P適合升鏈條件,若任意P的元素的升鏈a1a2≤...最終固定,就是說存在正整數n,使得對所有m>n,有am=an。類似地,P適合降鏈條件,若任意P的元素的降鏈a1a2≥...最終固定(就是說不存在無窮降鏈)。
P的升鏈條件等價於最大條件:所有P的非空子集都有極大元。類似地,降鏈條件等價於最小條件:所有P的非空子集都有極小元。
所有有限偏序集都適合升鏈和降鏈條件。適合降鏈條件的全序集稱為良序集

無窮降鏈

給定帶有偏序≤的一個集合S無窮降鏈是鏈V,就是說在其上≤定義了全序S的子集,使得V沒有最小元素,也就是元素m它使得對於在V中所有元素n有著mn
作為例子,在整數的集合中,鏈−1, −2, −3, ...是無窮降鏈,但是在自然數上沒有無窮降鏈,所有自然數的鏈都有一個極小元素。
如果偏序集合不包含任何無窮降鏈,則稱它為良基的。沒有無窮降鏈的全序集合是良序的。

良基

在數學中,類X上的一個二元關係R被稱為是良基的,若且唯若所有X的非空子集都有一個R-極小元;就是說,對X的每一個非空子集S,存在一個S中的元素m使得對於所有S中的s,二元組 (s,m) 都不在R中。
等價的說,假定某種選擇公理,一個二元關係稱為是良基的,若且唯若它不包含可數的無窮降鏈,也就是說不存在X的元素的無窮序列x0,x1,x2, ...使得對所有的自然數n有著xn+1Rxn
序理論中,一個偏序關係稱為是良基的,若且唯若它對應的嚴格偏序是良基的。如果這個序還是全序,那么此時稱這個序為良序
在集合論中,一個集合x稱為是一個良基集合,如果集成員關係在x傳遞閉包上是良基的。策梅洛-弗蘭克爾集合論中的正則公理,就是斷言所有的集合都是良基的。

良序

數學中,集合S上的良序關係(或良序)需要滿足:
1.是在S上的全序關係
2.S的所有非空子集在這個次序下都存在最小元素
等價的說,良序是良基的線序。集合S和這個良序關係一起就叫做良序集合
粗略的說,良序集合的排序方式,使得我們可以逐次考慮一個它的元素,而在還沒有檢視完所有的元素的任何時候,總是有一個唯一的下一個元素可考慮。

性質

如果 (X, <) 是良基關係並且xX中的一個元素,那么以x為始的降鏈都是有限長的,但是這不意味著它們的長度必定是有界的。請考慮下面的例子:
X為全體正整數和一個新元素 ω 的並,ω 比任何整數都要大。這樣X是一個良基集合,但是存在以 ω 為始的降鏈其長度可以任意(有限的)大:對任意的 n,鏈 ω,n-1,n-2, ..., 2, 1 的長度為 n。
Mostowski崩塌引理蘊涵集合成員關係是一個普遍(universal)的良基關係:對任何類X上的類集的(set-like)良基關係R,存在一個類C滿足 (X,R) 同構於 (C,∈)。

相關詞條

熱門詞條

聯絡我們