序數
各式各樣的數 |
基本 |
延伸 |
其他 |
數學集合論中,序數(ordinal number,ordinal)是自然數的一種擴展,與基數相對,着重於次序的性質。大於有限數的序數也稱作超限序數。
超限序數是由數學家格奧爾格·康托爾於1897年引入,用來考慮無窮序列,並用來對具有序結構的無窮集進行分類。
序數對自然數的擴展
自然數可以用來做兩件事:描述一個集合的大小,或者描述序列中一個元素的位置。在有限的世界裏這兩個概念是一致的,當處理無限集合時人們不得不區分這兩者。從大小的概念可以引申出如康托爾描述的「基數」,而位置的概念則被推廣到這裏將要說明的序數。
基數這一概念可以適用於沒有特殊結構的集合,而序數卻和同一種稱為良序集的特殊集合有着密切的關聯(這種關聯如此密切,以至於一些數學家不去區分這兩個概念)。簡單說來,一個良序集是一個全序集(任意給定兩個元素,可以定義一個大的、一個小的),不存在無窮降鏈(但可以有無窮升鏈),換言之有最小元素。序數可以用來標定任何給定的良序集的元素(最小的元素標定為0,其後的標定為1,再後的標定為2,依此類推),同時也可以用來給出良序集的「長度」—沒有用來標定良序集的元素的最小序數就是這個良序集的長度。這個「長度」也稱為集合的序類型。
任何一個序數都是通過先於它的所有序數構成的集合來定義:實際上,序數最常見的定義就是把每個序數等同於先於它的所有序數構成的集合。比如,序數42就是比它小的序數的序類型,也即,我們把從0(所有序數中最小的)到41(42的直接前驅)這些序數組成集合{0,1,2,…,41},該集合就是序數42。相反的,任何下閉的序數集合—意思是說,任何比該集合中一個序數小的序數都在該集合中—就是(或者等同於)一個序數。
目前為止,我們只考慮了有限的序數,即自然數。但無限的序數也是存在的:最小的無限序數是ω,它是自然數(有限序數)的序類型,或者等同於自然數集(實際上,自然數集是良序的—正如所有的序數集合一樣—並且自然數集也是下閉的,所以它等同於一個序數,也就是我們定義的ω)。
或許對序數更清晰的直覺可以通過檢視最初的幾個序數建立起來:如上所述,序數開始於自然數,0, 1, 2, 3, 4, 5, …;然後在所有的自然數之後是第一個無限序數,ω,緊接其後的是ω+1, ω+2, ω+3,等等(加號的確切含義將會在後面給出,這裏把它看作標籤就可以了)。在這些之後就是ω·2(也即ω+ω), ω·2+1, ω·2+2,等等,緊接着是ω·3,然後是後來的ω·4。我們通過這種方式形成的序數集合(形如「ω·m+n」的序數,這裏m和n是自然數),一定有一個序數等同於它:即ω2。更進一步,我們可以得到ω3,ω4,等等,以及ωω和其後的ωω²,乃至其後很多的ε0(這只是給出了幾個最小—可數—的序數)。我們可以按照如上方式無限的進行下去。
定義
良序集定義
良序集合是在其中所有非空子集都有一個最小元素的有序集合:這等價於(至少在假定依賴選擇公理下)說這個集合是全序的並且沒有無限遞減序列,這樣說可能較直觀。在實踐中,良序的重要性體現於超限歸納法的應用,大致上它是聲稱,若有一性質可從一個元素的前驅傳遞到這個元素自身,那麼該性質必定對(給定良序集合的)所有元素成立。如果一個計算(電腦程式或遊戲)的狀態可以被良序,即在每一個步驟都伴隨着「更低」的步驟的方式下,則這個計算必然會終止。
現在我們不想區分兩個良序集合,如果它們只是在「它們元素的標記」上不同,或者更加形式的說:如果我們可以把第一個集合的元素和第二個集合的元素配對起來,使得如果在第一個集合中一個元素小於另一個元素,則在第二個集合中第一個元素的配對者也小於第二個元素的配對者,反之亦然。這種一一對應叫做序同構(或嚴格的遞增函數),而這兩個有序集合被稱為序同構的,或相似的(明顯的這是一個等價關係)。假定在兩個有序集合之間存在一個序同構,這個序同構是唯一的:所以,把兩個集合視為本質上同一的,並尋求同構類型(類)的「規範」代表,就顯得很自然了。這就是序數所提供的作用,並且它還給任何良序集合的元素提供了規範的標記方式。
所以我們本質上希望定義序數為良序集合的同構類:就是說,作為「是序同構」這一等價關係的等價類。但是這涉及一個技術上的困難,事實上這個等價類實在太大了,所以在策梅洛-弗蘭克爾集合論中並不是一個集合。但是這不是個嚴重的困難。我們稱序數是在這個類中任何集合的序類型。
以等價類來定義序數
序數的最初定義,例如在《數學原理》中,把一個良序的序類型定義為,由類似(序同構)於這個良序的所有良序組成的集合。換句話說,序數是良序集合的等價類。這個定義在ZF和相關的公理化集合論中必須拋棄,因為這些等價類太大而不能是集合。但是這個定義,在類型論、蒯因的新基礎集合論和有關的系統中仍可使用(就最大序數的布拉利-福爾蒂悖論,在這裏它給出了頗令人驚訝的另一種解決方式)。
序數的馮·諾伊曼定義
與其定義序數為良序集合的等價類,我們可以嘗試定義它為(規範的)代表這個類的某個特定良序集合。因此我們希望把序數構造為特殊的良序集合,使得所有良序集合都同構於一個且只是一個序數。
馮·諾伊曼提議了巧妙的定義,現在被作為了標準:定義每個序數為特殊的良序集合,也就是在它之前的所有序數的集合。形式的說:
- 一個集合S是一個序數,若且唯若S中的元素在集合從屬關係下為全序集,並且S的任意元素也是S的子集。
自然地,這樣的一個集合S在集合包含關係下為良序集。這依賴於良基公理:所有非空集合B都有一個元素b不相交於B。
按此定義,自然數也是序數。(參見自然數的集合論定義)例如,2是4 = {0, 1, 2, 3}的一個元素,而2等於{0, 1},因而它是{0, 1, 2, 3}的子集。
可以通過超限歸納法證明,所有有限的良序集合都精確的同構於這樣構建的序數的其中一個。
進一步的,所有序數的元素也是序數自身。給定兩個序數S和T,S是T的一個元素,若且唯若S是T的真子集。此外,要麼S是T的一個元素,要麼T是S的一個元素,要麼它們是相等的。所以所有的序數集合都是全序集。事實上: 所有的序數集合都是良序集。這個重要結果一般化了「所有的自然數集合是良序集」此一事實,並允許我們自由地通過序數使用超限歸納法。
另一個推論是所有序數S都是完全由小於S的序數作為元素的一個集合。這個陳述以其他序數完全確定了所有序數的內部結構。它被用於證明關於序數的很多其他有用的結果。其中的一個例子是在序數間的次序關係的重要性質:所有的序數集合都有一個上確界,這個序數是通過取在這個集合中的所有序數的併集而獲得的。另一個例子是所有序數的搜集不是集合的事實。因為所有序數隻會是包含其他序數,從而所有序數的搜集的所有成員也是它的子集。所以,如果這個搜集是個集合,通過定義它自身將必定是個序數;那麼它將是自身的成員,這跟正規公理矛盾。(請參見布拉利-福爾蒂悖論)。所有序數的類通常寫為"Ord"、"ON"或"∞"。
一個序數是有限的,若且唯若它的反序也是良序的,即若且唯若它的所有子集都有最大元素。
假設良序定理,所有集合都可加上良序關係。利用超窮遞歸可證明所有良序集都與某序數同構(即存在雙射使得a>b ⇔ f(a)>f(b))。有限集合所有良序關係都是同構的,若有n個元素,對應序數就是n。無限集合有無限的良序關係,如自然數集配以0<2<4<...<1<3<5<...對應的序數是ω+ω。
注意,序數的元素必然是序數,而序數的子集亦必然是序數。兩個序數是可以比較大小,即會存在單射f使得a>b ⇒ f(a)>f(b)。一個集合對應的最小序數,就是這集合的基數。
其他的定義方式
還有序數定義的其他現代公式化。這些定義在本質等價於上面給出的定義。下面給出其中的一個。一個類S被稱為傳遞性的,如果S的每個元素x是S的子集,也就是。序數接着被定義為其成員也是傳遞的傳遞集合。從它得出成員們自身也是序數。注意使用了正規公理(基礎公理)來證實這些序數通過包含(子集)是良序的。
超限歸納法
超限歸納法在任何良序集合中成立,但是它與序數的關係如此重要而值得在這裏重申。
- 若有一性質可從小於給定序數α的序數的集合傳遞到α自身,則此性質對所有序數都成立。
就是說,如果「若P(β)對所有β<α為真,P(α)就為真」,則P(α)對所有α都為真。或者更加實際的說:為了證明性質P對所有序數α成立,你可以假定它對於所有β<α的更小的序數們已經是成立的。
超限遞歸
超限歸納不只能用來證明各種結論,而且還可以用於定義(這種定義方式通常稱為超限遞歸—我們使用超限歸納法證明這個結果是良好定義的):形式陳述寫起來太冗長,但重點在於,為了在序數α上定義一個(類)函數,你可以假定它對所有β<α更小的序數們已經定義了。你可以通過超限歸納法證明有且只有一個函數滿足直到並包括α的遞歸公式。
下面是通過在序數上超限歸納定義的一個例子(後面還會給出):通過設F(α)是不在對於所有β<α的F(β)的集合中的最小序數,定義出一個函數F。注意我們如何假定F(β)在真正定義F的過程中是已知的:這種表面的悖論完全是超限歸納所允許的。現在實際上F(0)是有意義的,因為沒有β<0,所以β<0的所有F(β)的集合是空集,所以F(0)必定是0(所有序數中最小的),現在我們知道了F(0),那麼F(1)有意義(它是不等於F(0)=0的最小序數),以此類推(這裏的「以此類推」正正就是超限歸納)。不過,這個例子不是太有趣,因為對於所有序數α有F(α)=α:而這可以通過超限歸納嚴格的證明。
後繼與極限序數
任何非零序數都有一個最小元素(就是零)。但它可以有或沒有最大元素:42或ω+6有最大元素,而ω沒有(沒有最大自然數)。如果一個序數有最大元素α,則它是在α之後的下一個序數,它叫做後繼序數,就是α的後繼者,寫做α+1。在序數的馮·諾伊曼定義中,α的後繼者是,因為它的元素是α的那些元素和α自身。
不是後繼者的非零序數叫做極限序數。使用這個術語的一個理由是,極限序數實際上是在拓撲意義上的所有更小序數的極限(參見序拓撲)。
相當一般的說,在 (αι<γ)是一個序數序列(由極限γ標定的族)的時候,並且如果我們假定 (αι)是遞增的(αι<αι′只要ι<ι′),或者至少非遞減的,我們定義它的極限是集合{αι}的最小上界,就是說大於這個序列任何一項的最小序數(總是存在)。在這個意義上,極限序數是所有(由自身標定的)更小序數的極限。
因此,所有序數要麼是零,要麼是一個後繼者(有一個良好定義的前驅者),要麼是極限。這個區別是重要的,因為很多通過超限歸納的定義依賴於它。經常地,在通過超限歸納在所有序數上定義一個函數F的時候,你定義F(0),和F(α+1)(假定F(α)已定義了),並接着對極限序數δ定義F(δ)為對所有β<δ的F(β)的極限(這裏的極限,要麼是指上述的序數極限,要麼是別的極限概念,如果F的值並非序數)。所以,在這個定義中有意思的步驟是後繼步驟,而不是極限序數。這種函數(特別是非遞減和接受序數值的F)被稱為是連續的。我們將看到序數加法、乘法和指數作為它們的第二個參數的函數是連續的。
標定序數類
我們已經提到了任何良序集合都類似(序同構)於一個唯一的序數,或者換句話說,它的元素可以通過小於的序數以遞增的方式標定。這尤其適用於任何的序數集合:任何的序數集合都自然的通過小於某個的序數來標定。對於序數的類(通過某個性質而定義的序數的搜集,可能對於形成一個集合太大了),帶有稍微的修改同樣成立:任何的序數類都可以用序數標定(並且在這個類是無界的時候,這使它處在與所有序數的類的類雙射中)。所以我們可以自由的談論在類中的第個元素(一般而言,第「0」個是指最小的,而第「1」個是次小的,以此類推)。形式上說,這個定義本質上是超限歸納法:一個類的第個元素被定義為(假定對於所有的情況已經定義了),大於對於所有的第個元素的最小元素。
又例如,我們可以應用它於極限序數的類:要麼是極限要麼是零的第個序數是(參見序數算術中關於序數乘法的定義)。類似的,我們可以考慮「加法不可分解」的序數(意味着它是非零序數,且不能是兩個嚴格更小的序數的和):第個加法不可分解序數被標定為。標定序數類的技術經常在不動點的論述中有用:例如,使得的第個序數被寫為。
閉無界集合與類
一個序數被稱為是無界的或共尾的,當給定任何序數,總是有這個類的某個元素大於它的時候(則這個類必定是真類,就是說不能是集合)。它被稱為是閉合的,如果在這個類中序數的一個序列的極限總會在這個類中:或者等價的說,當標定(類-)函數是連續的,即對於這個極限序數,(在這個類中第個序數)是所有對於的的極限;這在拓撲意義上對於序拓撲也是閉合的,(為了避免談論在真類上的拓撲,你可能要求這個類與任何給定序數的交在序數的序拓撲上是閉合的,這再次是等價的)。
特別重要的序數類是閉合無界的。例如,所有極限序數的類是閉合且無界的:也就是說,總是有一個極限序數大於給定序數,而且極限序數的極限是極限序數。加法不可分解序數的類,序數的類,基數的類,都是閉合無界的;而正規基數的類是無界但不閉合的,序數的任何有限集合則是閉合但非無界的。
一個類是固定的,如果它與所有閉合無界類有非空交集。任何閉合無界類的超類都是固定的,並且固定類必然是無界的;但也有着不閉合的固定類,以及那些沒有閉合無界子類的固定類(比如帶有可數共尾性的所有極限序數的類)。因為兩個閉合無界類的交集是閉合和無界的,所以固定類和閉合無界類的交集是固定的。但是兩個固定類的交可以為空,比如帶有共尾性ω的序數的類和帶有不可數共尾性的序數的類。
與其考慮作適用於序數的(真)類的公式化定義,我們可以對在給定序數之下的序數的集合作公式化定義:極限序數的子集被稱為是在之下無界的(或共尾的),假定小於的任何序數會小於在這個集合中的某個序數。更加一般的說,我們可以稱任何序數的子集為共尾於,如果小於的所有序數會小於或等於在這個集合中的某個序數。稱這個子集下閉合,如果它對在內的序拓撲是閉合的,就是說,在這個集合中的序數的極限要麼在這個集合中,要麼等於自身。
序數算術
在序數上有三個常見運算:加法、乘法和(序數)指數。每個大致上都可以用兩種不同的方式定義:要麼構造一個明確的良序集合去表示這個運算,要麼使用超限遞歸。康托爾範式提供了一個表示序數的標準方式。所謂的"自然"算術運算保持了交換律,但代價是損失了連續性。
序數與基數
基數的初始序數
每個序數都有一個關聯的基數,就是通過簡單的忘記次序而獲得的它的勢。如果某良序集合的序類型就是該序數,那麼它們都會有相同的勢。有給定基數作為它的勢的最小序數,叫做這個勢的初始序數。所有有限序數(自然數)是初始的,而絕多數無限序數都不是初始的。選擇公理等價於聲稱所有集合都可以良序化,就是說所有基數都有一個初始序數。在這種情況下,傳統上把基數等同為該初始序數,並稱這個初始序數是一個基數。
第α個無限序數被寫為。它的勢被寫為。例如,ω0 = ω的勢為,它也是ω²或ε0(都是可數序數)的勢。所以(假定選擇公理)我們把ω等同於,除了記號用在寫基數的時候,而ω用在寫序數的時候(這一點很重要,因為而)。還有,是最小的不可數序數(要看出其存在性,只需考慮由自然數的良序的等價類組成的集合:每個這樣的良序都定義了一個可數序數,然後是這個集合的序類型),是勢大於的最小序數,以此類推,而是對自然數n的極限(任何基數的極限是基數,所以這個極限實際上是在所有之後的第一個基數)。
共尾性
序數的共尾性是作為的共尾子集的序類型的最小序數。注意一些作者只對極限序數定義或使用共尾性。序數或任何其他良序集合的集合的共尾性是這個集合的序類型的共尾性。
因此對於極限序數,存在着一個極限為的-標定的嚴格遞增序列。例如,ω²的共尾性是ω,因為序列ω·m(這裏的m在自然數上取值)趨向於ω²;但是,更加一般的說,任何可數極限序數都有共尾性ω。一個不可數的極限序數可以有要麼同一樣的共尾性ω,要麼有不可數共尾性。
0的共尾性是0。任何後繼序數的共尾性是1。任何極限序數的共尾性至少是。
等於其共尾性的序數叫做正規的,並且它總是初始序數。任何正規序數的極限都是初始序數的極限,因而也是初始的,即使它不是正規的(它通常不是)。如果有選擇公理,則對於每個α,都是正規的。在這種情況下,序數0, 1, , ,和都是正規的,而2, 3, ,和ωω·2是非正規的初始序數。
任何序數α的共尾性都是正規序數,就是說α的共尾性的共尾性等同於α的共尾性。所以共尾性運算是等冪的。
某些「大的」可數序數
我們已經提及了(參見康托爾範式)序數艾普塞朗數ε0,它是滿足等式的最小序數,所以它是序列0, 1, , , ,等的極限。很多序數可以用特定序數函數的不動點的方式定義(如果使得的第個序數叫做,則我們總可以繼續嘗試找到使得的第個序數,「以此類推」,但微妙在於「以此類推」)。我們可以嘗試有系統的這麼做,而不管用什麼系統來定義和構造序數,總是有一個序數正好位於這個系統所構造的所有序數之上。也許以這種構造系統的方式限定的最重要的序數是邱奇-克萊尼序數(儘管名字中有,這個序數是可數的),它是不能以可計算函數表示的最小序數。不過,還是可以在之下定義相當大的序數,它們有的標誌着特定形式系統的「證明論強度」(例如,標誌着皮亞諾算術的強度)。也可以在邱奇-克萊尼序數之上定義更大的序數,這些大序數會在邏輯的多個部分有研究價值。
參見
參考資料
- Conway, J. H. and Guy, R. K. "Cantor's Ordinal Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 266-267 and 274, 1996.
- Sierpiński, W. (1965). Cardinal and Ordinal Numbers (2nd ed.). Warszawa: Państwowe Wydawnictwo Naukowe. Also defines ordinal operations in terms of the Cantor Normal Form.
- Patrick Suppes, Axiomatic Set Theory, D.Van Nostrand Company Inc., 1960