良序關係

數學中,集合S上的良序關係(或良序)需要滿足:①是在S上的全序關係。②S的所有非空子集在這個次序下都存在最小元素。等價的說,良序是良基的線序。集合S和這個良序關係一起就叫做良序集合

粗略的說,良序集合的排序方式,使得我們可以逐次考慮一個它的元素,而在還沒有檢視完所有的元素的任何時候,總是有一個唯一的下一個元素可考慮。

例子

  • 自然數的標準排序≤是良序的。
  • 整數的標準排序≤不是良序的,因為比如整數的集合不包含最小元素。
  • 整數的下列關係R是良序的:
x R y,當且僅當下列條件之一成立:
  1. x = 0
  2. x是正數,而y是負數
  3. xy都是正數,而xy
  4. xy都是負數,而yx
R可以顯示為如下:
0 1 2 3 4 ..... -1 -2 -3 .....
R 同構序數ω + ω。
  • 可以定義整數的另一個良序關係如下:x <z y 當且僅當 |x| < |y| 或 (|x| = |y| 且x ≤ y)。
這個良序可以顯示為如下:
0 -1 1 -2 2 -3 3 -4 4 ...
  • 實數的標準次序≤不是良序的,因為例如開區間 (0, 1)不包含最小元素。存在着依賴於選擇公理的證明,其能夠證明實數可以被良序化,但是這些證明是非構造性證明

性質

在良序集合中,除了整體上最大的那個,所有的元素都有一個唯一的後繼元:比它大的最小的元素。但是,不是所有元素都需要有前驅元。作為例子,考慮自然數的一個次序,這裡的所有偶數都小於所有奇數,並在偶數和奇數內應用正常的次序。

0 2 4 6 8 ... 1 3 5 7 9 ...

這是個良序集合並被指示為ω + ω。注意儘管所有元素都有後繼元(這裡沒有最大元素),有兩個元素缺乏前驅元:零和一。

如果一個集合可被良序化,超限歸納法證明技術可以用來證明給定陳述對於這個集合的所有元素為真。

良序定理,等價於選擇公理,聲稱所有集合都可以被良序排序。良序定理還等價於庫拉托夫斯基-佐恩引理

等價表述

如果一個集合是良序的,則下列是等價的:

  1. 所有非空子集合都有最小元素。
  2. 超限歸納法在整個有序集合上成立。
  3. 所有嚴格遞減序列必定在有限多步驟內終止(假定依賴選擇公理)。

序數

所有良序集合都唯一地序同構於一個唯一的序數。實際上,這個性質是定義序數背後的動機。

參見