集合論/序數

有限和超限序數

序數的標準表示

序數的定義很少能揭示其本質。在這種情況中，純數學家會建立他們想要研究的物件的表示。這些表示是基於熟悉的數學結構構建的，並且等價於那些難以理解的物件。透過操作表示中的熟悉的數學結構，純數學家就可以研究那些神秘的抽象實體的結構。

序數最常見的表示法，由馮·諾依曼提出，如下所示。序數 0 被定義為空集 $\emptyset$；序數 1 被定義為集合 $\{0\}$，當然等於 $\{\emptyset \}$。類似地，序數 2 是集合 $\{0,1\}$；序數 3 是集合 $\{0,1,2\}$；序數 4 是集合 $\{0,1,2,3\}$。任何有限序數 $n$ 被定義為集合 $\{0,1,2,\ldots ,n-1\}$（或者，在嚴格的表示法中，序數 α 的後繼被定義為集合 $s(\alpha )=\alpha \cup \{\alpha \}\,$）。

事實上，這個定義可以自然地擴充套件到超限序數。序數 $\omega$ 是一個集合，它包含所有有限序數 $\{0,1,2,3,\ldots \}$。同樣，$\omega +1$ 是集合 $\{0,1,2,3,\ldots ,\omega \}$；$\omega +2$ 是集合 $\{0,1,2,3,\ldots ,\omega ,\omega +1\}$；等等。

序數 $\omega +\omega$ （或 $\omega *2$）是包含所有有限序數和形式為 $\omega +n$ 的序數的集合，其中 $n$ 是一個有限序數。因此 $\omega +\omega =\{0,1,2,\ldots ;\omega ,\omega +1,\omega +2,\ldots \}$.

序數 $\omega _{1}$ 是第一個不可數序數，它是所有可數序數的集合。

良序關係

序數的基本性質是良序性。這將使上述非正式討論能夠得到正式定義，並允許我們證明一些必要的基本事實。

定義：集合 P 的全序關係是一個 P 的良序關係，如果每個非空子集都有一個最小元素。定義：良序集合 W 的初始段是形如 {w∈W|w<v} 的集合，其中 v∈W。

良序關係是一種“通用順序”，在某種意義上，給定任意兩個良序集合，一個良序集合是另一個良序集合的序同構，或者是另一個良序集合的初始段。這將在以下幾個定理中得到證明。

定理：從良序集合到自身的任何增函式都是上升的：如果 (W, <) 是一個良序集合，而 f: W→W 是一個函式，使得 x>y→f(x)>f(y)，那麼對於所有 w∈W，都有 f(w)≥w。

• 證明：如果 {w∈W: f(w)<w} 非空，令 v=min {w∈W: f(w)<w}。則 f(v)<v，因為 f 是增函式，所以 f(f(v)) < f(v)，所以 f(v)∈{w∈W: f(w)<w}。則 f(v)≥v，因為 v 是該集合的最小元素，這與 f(v)<v 矛盾。因此，{w∈W: f(w)<w} 必須為空。

定理：良序集合上的任何序自同構都是恆等變換。

• 證明：給定任何自同構 f: W→W，該函式及其逆函式都必須是增函式。根據上述定理，我們可以得出結論
• f(x) ≥ x
• 以及 f^-1(x) ≥ x
• f 是增函式，所以 f(f^-1(x)) ≥ f(x)
• 簡化後，x ≥ f(x)。
• f(x) = x

定理：如果 *f* 和 *g* 都是良序集合 V 和 W 的序同構，則 f=g。

• 證明：g^-1∘f 和 f∘g^-1 分別是 V 和 W 上的自同構，因此它們都等於恆等函式。

定理：良序集合不存在到其任何自身初始段的序同構。

• 證明：令 (W, <) 為良序關係，令 S_v = {w∈W|w<v} 為初始段。如果 f: W→S_v 是序同構，則將 f 的範圍擴充套件到 W，f 是一個到自身的增函式，因此 f(v)≥v。但 f(v)∈{w∈W|w<v}，因此 f(v)<v。因此，這樣的 f 不存在。

定理：序同構 f: W→V 對 W 的初始段 S_w 的限制是該初始段到 V 的初始段 S_f(w) 的序同構。

• 證明：對於任何 w'∈S_w，都有 f(w')<f(w)，因此 f(w')∈S_f(w)，f 將 S_w 對映到 S_f(w) 中。此外，對於任何 v∈S_f(w)，都有 v<f(w)，因此 f^-1(v)<f^-1f(w)) = w，因此 f^-1(v) 在受限函式的域中，其中 f(f^-1(v)) = v，這意味著受限函式 f 也對映到 S_f(w) 上。因此，將 f 的域限制到 S_w，就可以將它的範圍縮減到 S_f(w)，使其成為雙射。

我們現在終於來到了良序關係背後的主要思想。

定理：給定任意兩個良序集合，一個集合是另一個集合的序同構，或者是另一個集合的初始段。

• 證明：令 (V, <) 和 (W, <) 為兩個良序集合。首先，我們使用前一個定理來建立以下事實：W 中所有 w 的集合，使得 W 中的初始段 S_w 與 V 中某個 v 的初始段 S_v 同構，是*向下閉合的*。給定任何 w∈W，如果 S_w 存在這樣的同構，那麼給定任何 w'<w，也存在 v'∈V 使得 S_w' 與 S_v' 序同構。

這是因為根據上述定理，將同構限制到 S_v 中 w' 的初始段，也是該段到 S_w 中 f(w') 的初始段的序同構，其中 f 是序同構。但 S_v 中的初始段也是 V 中的初始段，因為順序是傳遞的，W 中的初始段也是如此。

假設存在 v∈V，其中 S_v 與 W 中任何 w 的 S_w 都不序同構。則 v 屬於上述集合的補集，因此該補集非空：令 v₀ 為最小的 v。則任何 v>v₀ 也將屬於該補集：如果 S_v 與某個 S_w 同構，則 v₀<v 意味著 v 也必須如此，但事實並非如此。

對於任何 v∈S_v0，都有 v<v₀，並且鑑於 v₀ 是不存在這樣的同構的最小元素，所以 S_v 必須與 W 中某個 w 的 S_w 同構。此外，這樣的 w 必須是唯一的，因為如果 S_v 也與 W 中某個 w' 的 S_w' 同構，則不失一般性，假設 w'<w，並令 f 和 g 分別是到 S_w 和 S_w' 的同構。則 g∘f^-1: S_w→S_w' 是一個良序集合到其自身初始段的同構，這被證明是不可能的。

這建立了一個由以下定義的函式 f: S_v0→W

f(v) = S__v 與 S__w 序同構的唯一 w∈W

我們證明了 f 的範圍也是向下閉合的，這意味著如果 w∈f(V) 且 w'<w，則 w'∈f(V)。如果 w∈f(V)，則存在 v∈V 使得 f(v) = w，因此存在一個從 S__v 到 S_w 的序同構 g。對於任何 w'<w，f^-1 對 S_v 中 w' 的初始段的限制也是一個到 S_v 中 g^-1(w') 的初始段的序同構。如前所述，初始段中的初始段也是整個集合的初始段，這是由於傳遞性。因此，S_g^-1(w') 與 S_w' 序同構，這意味著 f(g^-1(w')) = w'。因此，w'∈f(V)。

現在要證明 f 是一個滿射函式。注意，如果它不是，則像集的補集 W-f(V) 非空，因此令 w₀=min W-f(V)。w₀ 是最小值意味著對於任何 w<w₀，都有 w∈f(V)，因此 S_w0⊆f(V)。反之，如果 w∈f(V)，則 w≠w₀，因為 w₀∉f(V)。第二，如果 w>w₀，則因為範圍是向下閉合的，所以 w₀∈f(V)，這是錯誤的。因此，w<w₀，所以 w∈S_w0，所以 f(V)=S_w0。但這意味著 f 是 S_v0 到 S_w0 的序同構，這與 v₀ 被定義為不存在這樣的同構的 V 中的最小元素相矛盾。因此，W-f(V) 必須為空，而 f 是滿射的。

有了所有這些，f 因此是 S_v0 和 W 之間的序同構。

這處理了存在 v∈V 的情況，其中 S_v 與 W 中任何 w 的 S_w 都不序同構。同樣的論點適用於存在 w∈V 的情況，其中 S_w 與 V 中任何 v 的 S_v 都不序同構，方法是應用相同的結果，交換 V 和 W，並在 V 和 W 的初始段之間找到一個同構。

最後，假設兩者都不存在，並且對於每個 v∈V，S_v 與某個 w∈W 的 S_w 序同構，並且每個 S_w 與某個 v∈V 的 S_v 序同構。則定義的函式，這次是 f: V→W，其域為整個 V，將是 V 和 W 之間的序同構。

注意，這三種情況中只有一種可能成立，這是因為良序集合與自身初始段的序同構是不可能的。

傳遞集和序數

序數的基本排序是集合包含關係 ∈。我們建立一個集合類，使得 a<b 當且僅當 a∈b。成為序數的基本要求是傳遞性。

定義：如果 S∈T 則 S⊆T，則集合 T 是傳遞的。擴充套件子集的定義：如果對於所有 S∈T 和 R∈S，都有 R∈T，則集合 T 是傳遞的。

在某種意義上，傳遞集是“向下閉合的”，這是透過 ∈ 關係實現的。

定義：序數是透過 ∈ 關係良序的傳遞集。

請記住，良序也意味著線性排序。因此，符號 ∈ 和 < 將在序數的元素中可互換使用。

我們現在為使用序數建立一些基本事實。

• 定理：∅ 是一個序數。
• 證明：它是透過 ∈ 在空虛意義上傳遞的且良序的。

• 定理：如果 β∈α 且 α 是一個序數，則 β 是一個序數。
• 證明：α 是傳遞的，所以 β⊆α，因此 β 也透過 ∈ 良序。如果 γ∈β，則 γ∈α，因為 β⊆α，而且 γ⊆α，因為 α 是傳遞的。那麼，如果 δ∈γ，則 δ∈α。因此，δ、γ 和 β 都是 α 的元素，且 δ∈γ∈β，所以 δ∈β，因為 ∈ 是 α 中的傳遞關係。

• 定理：如果 β⊆α 且 β≠α，且 α 和 β 都是序數，則 β∈α。
• 證明：α-β 非空且是 α 的子集，令 γ = min(α-β)。

如果 δ∈γ，則 δ<γ=min(α-β)，所以 δ∉α-β，這意味著 δ∈β。反之，如果 δ∈β，則 δ∉α-β，而且 δ∈α，因為 β⊆α，且 α 是全序的，因此 δ>γ 或 δ<γ，因為它們都是 α 的元素。第一種情況實際上是不可能的：γ<δ（或 γ∈δ）與 δ∈β 一起意味著 γ∈β，因為 β 是一個傳遞集，但 γ 應該是一個 α-β 的元素。因此，δ<γ 或 δ∈γ。

因此，γ=β，且 γ∈α-β，所以 γ∈α。

• 定理：如果 α 和 β 是序數，則其中一個必須是另一個的子集。
• 證明：交集 α∩β 也是一個序數：作為 α 的子集，它透過 ∈ 良序。它是傳遞的，因為如果 γ∈α∩β，則 γ⊆α 且 γ⊆β，所以 γ⊆α∩β。

α∩β 必須等於 α 或 β。假設情況並非如此：那麼 α∩β⊆α 但 α∩β≠α，所以根據前面的定理 α∩β∈α。類似地，α∩β⊆β 但 α∩β≠β，所以 α∩β∈β。但 α∩β∈α∩β，與 α 透過 ∈ 良序（特別是，∈ 必須是一個嚴格排序，因此它具有反自反性）相矛盾。

然後可以很容易地建立以下推論。

• 定理：如果 α 和 β 是序數且 α≠β，則 α∈β 或 β∈α。從這裡開始，將 α∈β 也表示為 α<β。因此，∈ 是所有序數類的全排序。

證明：首先，驗證 ∈ 是否滿足傳遞性和反自反性。如果 α 是一個序數且 α∈α，則 α 的元素需要良序，特別是透過 ∈ 反自反的，這被 α∈α 違反。因此，對於所有序數，α∉α。其次，如果 α、β 和 γ 是序數且 α<β，β<γ，則 β∈γ 且 α∈β，因此 α∈γ，因為 γ 是一個傳遞集。

∈ 是一個全排序是上述定理的結果。

現在驗證良序性。如果 C 是一個非空的序數類，令 α∈C。如果 α 是 C 的最小值，則 C 有一個最小值。否則，存在一個 β<α 其中 β∈C。然後 α∩C 是 α 的一個非空子集，並且有一個最小元素，所以令 γ=min α∩C。然後對於所有 δ∈C，根據剛才證明的，要麼 δ=α，δ<α，要麼 δ>α。在第一種情況下，γ∈α，所以 γ<α=δ。在第二種情況下，δ∈α，所以 δ∈α∩C，所以 γ≤δ。在第三種情況下，γ<α 且 α<δ，所以 γ<δ。在所有三種情況下，γ≤δ。

• 定理：如果 α 是一個序數，則 α = {β | β < α}

證明：根據序數之間 < 的定義，即 ∈。

• 定理：一個非空的序數類的交集是另一個序數，實際上是該類的最大上界（inf）。此後，它將表示為 inf。

證明：令 C 為一個序數類。假設 β∈∩C。那麼對於任何 γ∈β 和 δ∈C，β∈δ 且 δ 是一個序數，所以 γ∈δ。因此，γ∈∩C，所以 ∩C 是傳遞的。此外，∩C 是一個序數的子集，因此透過 ∈ 良序。

• 定理：一個序數集的並集是另一個序數，實際上是該集的最小上界（sup）。此後，任何序數集的並集將表示為 sup。

證明：令 S 為一個序數集，令 α∈∪S。那麼存在 β∈S，α∈β。β 是一個序數，並且是傳遞的，因此對於任何 γ∈α，γ∈β，因此 γ∈∪S。因此，α⊆∪S，所以 ∪S 是傳遞的。此外，∪S 的所有元素都是序數，並且因為所有序數在 < 下都是良序的（意味著 ∈），任何序數集，特別是 ∪S 在 < 下都是良序的。

• 定理：如果 α 是一個序數，則 α∪{α} 是一個序數。如果 β>α 是大於 α 的一個序數，則 β≥α∪{α}。

證明：α∪{α} 是一個序數集，因此在 < 下是良序的。它是傳遞的：如果 β∈α∪{α}，要麼 β∈α 要麼 β=α。在第一種情況下，如果 γ∈β，則 γ∈α 且 γα∪{α}，所以 β⊆α∪{α}。在第二種情況下，β=α⊆α∪{α}。

用 S(α)=α∪{α} 表示。S(α) 被稱為 α 的後繼，因為根據上面的說法，它們之間沒有序數：沒有序數 β 對於任何序數 α 滿足 α<β<S(α)。對於任何 α，如果存在一個序數 β 使得 α=S(β)，則 α 被稱為 **後繼序數**。否則，α 被稱為 **極限序數**。

所有序數類 *Ord* 不是一個集合。如果它是一個集合，則 sup Ord 是一個序數，並且對於任何序數，sup Ord≥α。但 S(sup Ord) 也是一個序數，並且 S(sup Ord)>sup Ord，這是一個矛盾。

我們終於來到了序數的主要意義：作為“通用的良序函式”。

• 定理：每個良序集都與唯一的序數同構。

證明：令 W 為一個良序集。考慮公式“當 S_w（W 中由 w 確定的初始段）與序數 α 同構時，F(w) = α”。

首先，注意對於給定的 w∈W，如果這樣的序數存在，它是唯一的（否則，一個序數將與它自己的初始段同構），並且它也存在於所有 w'<w，實際上，S_w 上的同構等於 F，限制在 S_w 上。這是因為如果 o 是 S_w 和 α 之間的同構，則對於任何 w'<w，o 對 S_w' 的限制是 S_w' 和 o(w')<α 之間的同構。所以 F(w') = o(w') < F(w)。這也表明當 F 被定義時，F（以及 F^-1）是單調的。

反之亦然：如果 α=F(w) 對於某些 w∈W 且 β<α，則存在一個 w'<w 使得 β=F(w')。這是因為正如前面所述，F 限制在 S_w 上是 S_w 和 α 之間的同構，特別是它是滿射的。此外，注意對於任何 w∈W，如果 F 為所有 w'<w 定義，則它在 w 上定義，實際上等於 F(S_w)。首先，F 是單調的，所以它是其域和像之間的同構，因此只需要證明 F(S_w) 是一個序數。它是序數的集合，因此透過 ∈ 良序。此外，如果 α ∈ F(S_w) 且 β<α，則根據剛才證明的內容，β ∈ F(S_w)，因此 F(S_w) 是一個傳遞集。因此，F(S_w) 是一個序數。

這表明實際上 F 在整個 W 上都定義：否則，令 v = min { w∈W | S_w 不與任何序數同構 }。然後 F 在所有 v'<v 上定義，因此根據上一段，它在 v 上定義，這是一個矛盾。

現在在 W 中新增一個大於 W 中所有元素的元素，將其稱為 m。結果集仍然是一個良序集。那麼上述陳述也適用於這個新的良序集，因此 F(m) 在其中定義，這意味著 S_m 與序數 F(m) 同構。但 W=S(m)。

前幾個序數

定義 0 = ∅。然後定義 0 的後繼

1 = S(0)，2 = S(1)，3 = S(2)，等等。

0 是一個極限序數。用 ω 表示第一個非零極限序數。ω 的存在來自無窮公理。小於 ω 的序數被稱為 **有限** 或 **自然數**。自然數集有時用 N 表示，它也等於 ω。

歸納法，遞迴

良序性允許“向上計數”。這在歸納原理中給出

如果一個類 C 滿足 3 個屬性

1. 0∈C 2. α∈C → S(α)∈C 3. α 是極限序數，並且 (β<α→β∈C) 一起意味著 α∈C

那麼 C 包含所有序數。這來自良序性：如果 Ord-C 非空，則 min(Ord-C) 要麼是 0，要麼是一個後繼序數，要麼是一個非零極限序數。那麼要麼 0∉C（違反 1），對於某個 α，S(α)=min(Ord-C) 意味著 α∈ 且 S(α)∉C（違反 2），要麼 min(Ord-C) 是一個極限序數，並且所有 β<min(Ord-C) 都是 C 的元素，根據最小性，違反 3。

歸納法的一個主要目的是定義遞迴函式，即證明這樣的遞迴函式存在。當遞迴在序數上進行時，它通常被稱為“超限遞迴”。主要思想是，給定一個“類函式”G，它接收域為序數的函式，存在一個唯一的類函式 F，使得 F(α)=G(F 限制在 α 上) 對於所有序數 α。注意“限制在 α 上”意味著一個域限制在 α 的所有元素上，意味著所有小於 α 的序數。

超限遞迴的證明

序數算術

加法、乘法和乘方現在可以使用超限遞迴定義。