動機
而 ,說明無限序保留了基數所遺忘的資訊。乘方把位置組織成更大的塊;Cantor 正規形把每個非零序數寫成有限個遞減的 冪之和,並帶有正的有限係數。
這裏的「有限」需要解釋:項數有限,指數自身卻可能是很大的序數。繼續展開每個指數,未必得到只用自然數寫出的有限表達式。共尾數研究另一件事:從下方趨近一個序數,需要多少個位置?很大的序數也可能有很短的共尾序列。只有把序數算術、集合大小與共尾數分開,這些現象才不會顯得矛盾。
定義
定義 3.2.1
(序數冪)
對正序數 ,沿指數遞歸定義
其中最後一式適用於非零極限。正規形定理使用底數 。加法與乘法均為序數運算,因此 是依次排列 個 ;係數寫在右邊。
定義 3.2.2
(Cantor 正規形)
Cantor 正規形是
其中 為正的有限數,各 為正自然數。零用空和表示。
定義 3.2.3
(共尾子集與共尾數)
若 ,且每個 都不大於某個 的成員,則稱 共尾於 。定義共尾數 為使某個函數 的值域共尾的最小初始序數 。由於 可良序,這樣的初始序數存在。規定 ;後繼序數有最大前驅,故共尾數為一。非零極限沒有有限共尾子集,所以其共尾數無限。
定義 3.2.4
(正則基數與奇異基數)
無限初始序數 若滿足 ,稱為正則基數,否則稱為奇異基數。這兩個形容詞針對基數;不能僅因為某個普通序數的共尾數比其序型小,就把它叫作奇異基數。除非另作說明,本節不假設選擇公理。
以下使用由有序拼接直接得到的基本算術性質:加法結合,對第一變元單調不減,對第二變元嚴格遞增且在非零極限連續。三塊拼接改變括號而不改變位置,便給出結合律。有限倍數滿足 ,並有 。
定理/命題
定理 3.2.5
( 的冪與加法不可分解性)
函數 嚴格遞增,在非零極限連續,並滿足 。對任意 ,若 ,則 。當 時,還得到
定理 3.2.6
(Cantor 正規形的存在唯一性)
每個非零序數恰有一個 Cantor 正規形。構造反覆取出最大 冪、唯一正有限係數及更小餘項。若過程不在有限步結束,就產生指數的無限嚴格下降序列,所以它必終止。
概念視角算法
透過正規形比較序數
正規形也提供比較序數的程序。比較兩個非零序數時,先比較領先指數;若相同,再比較領先係數;若兩者都相同,便以同樣方法比較餘項。這是正確的,因為領先指數 與係數 把序數放在由 起、不含 的區間內;領先項相同時,加法對第二項嚴格遞增,把比較轉移到餘項。因此 ,儘管左邊的項較多。
定理 3.2.7
(共尾數本身是正則基數)
對每個非零極限序數 , 有嚴格遞增共尾映射 ,並滿足 。這些結論在 ZF 中成立,但沒有斷言每個序數或每個無限基數都正則。
證明思路
證明
(遞增、連續與加法不可分解)
後繼冪嚴格增加,因為正序數後面再排一個自身副本就更大,而 至少包含兩個副本。在極限處,每個較早冪之後還有更大的冪出現在上確界中。超限歸納遂給出 :後繼至少增加一,極限則支配所有較早指標。
對 歸納證明加法不可分解性。零指數時,唯一小於一的序數是零。若 ,令 。由於 ,可取正有限 使 、,於是
極限時,把兩序數同時界在一個更早的冪之下,應用歸納假設。當 , 是極限;加法對第二變元的連續性及剛證明的界給出 。另一方向由第一變元的單調性及 得到。這就是吸收公式。
右邊加數是 的冪這一假設,不能減弱為它是極限序數。
反例模式
極限序數不一定吸收較小加數
聲稱:若 是非零極限序數且 ,則 。取 、。有限倍數的左分配律給出 ,而 ,所以吸收失敗。對加法封閉亦失敗:,但 並不小於 。定理只適用於 ;這裏 嚴格介於 與 之間,不是這樣的冪。
證明
(以首項冪作除法)
固定 。存在最小 使 ,因為 給出集合大小的搜尋界。這個 不是零,也不是極限:若為極限,此前各冪都至多為 ,其上確界也至多為 。所以 ,且
令 ,取第一個嚴格大於 的有限倍數,就得到唯一正有限 滿足 。初始段 之後的良序尾部有唯一序型 ,從而 。加法對第二變元嚴格遞增,保證餘項唯一;又必有 ,否則下一個有限倍數已不大於 。
若餘項非零,就繼續同一構造。餘項小於先前的領先冪,因此新指數嚴格變小。若永不終止,普通遞歸會給出真正的無限下降序列;其值域的最小成員又有更小的下一項,矛盾。因此展開只有有限項。
任意候選正規形的領先項之後,尾部都小於其領先冪。每個較低指數的有限倍數都小於該冪,而加法不可分解性保證有限個這樣的項之和仍較小。所以整個形式準確落在相鄰冪之間,再準確落在相鄰有限倍數之間。領先指數、係數及餘項因此與上述構造相同。對有限尾部繼續比較,便得唯一性。
證明透視
終止證明排除的是哪條序列
證明中的下降序列,是各次餘項的領先指數,不是不斷展開某一項內部的指數。後一過程可在不動點回到同一序數,如 例子所示。前一過程則在每個未結束步驟嚴格下降,因為新餘項小於先前冪。各值已由除法論證唯一指定,所以若過程不停,普通遞歸便給出整條序列,沒有暗中作依賴選擇。這才是最小元論證所排除的具體無限下降。
證明
(最小長度的遞增共尾映射)
對共尾數,固定見證最小初始序數的共尾映射 。 為極限,所以 無限。無限初始序數必為極限序數:無限後繼序數可透過移動最初 個位置並把額外點放到起點,與其前驅建立雙射。每個 的基數小於 ,因此由這些指標取得的值不可能已經共尾,否則更小基數就成為見證。
遞歸定義
較早值域的基數小於 ,故在 中有界;由於 是極限,顯示的後繼上確界仍小於 。構造於是始終留在目標內,嚴格遞增,並因支配 而共尾。若某個更小基數 有共尾映射 ,則遞增性保證 共尾於 ,違背 的最小性。恆等映射本來就共尾於 ,故 。沒有一步為任意集合族同時挑選枚舉。
證明透視
共尾數的最小性如何用了兩次
遞歸取給定值 與一個嚴格越過所有較早值的累進界兩者中的較大者。 的最小性用了兩次。第一,每個較早值域都由某個基數較小的 編號,所以在 中有界;又因 是極限,累進界仍留在 內。第二,若有更短的共尾映射進入 ,與遞增的 複合便得到進入 的更短共尾映射。支配 提供共尾性;加上的後繼則提供嚴格遞增。
例題
例題 3.2.8
(相加會刪除較低的尾部)
令 、。吸收公式給出
第一式中,右邊的 開始時吞掉 ,但不吞掉較大的 。第二式中整個左加數小於 ,所以都被吞掉。正規形顯示運算次序,並沒有把加法變成逐項係數相加。
下面的互動圖讓你輸入兩個小於 的 Cantor 正規形序數,按任一次序相加或相乘,並看到哪些較低的項被吞掉,以及運算元的次序是否影響結果。
正規形顯示序數加法吞掉哪些較低的項
把兩個小於 ω^ω 的序數寫成 Cantor 正規形,選擇運算,逐項閱讀結果:被吞掉的項會加上刪除線,保留的項照舊,並比較兩種運算次序。
每個運算元有四個項位置。不用的位置會被忽略;計算前先合併相同指數,並把指數由大到小排列。
| 算式 | 正規形 |
|---|---|
| α | ω^4·2+ω^2·3+5 |
| β | ω^3+ω·2+7 |
α+β: ω^4·2+ω^2·3+5 + ω^3+ω·2+7 = ω^4·2+ω^3+ω·2+7
加上刪除線的項已被吞掉,不會出現在結果中。
規則:由右加數的領先指數 e 決定一切。左邊指數高於 e 的項保留,低於 e 的項消失,左邊在 e 處的係數加到右邊的領先係數上,然後接上右加數其餘各項。
- 右加數的領先指數:e = 3。
- 左邊高於 e 的項,保留:ω^4·2。
- 左邊低於 e 的項,被吞掉:ω^2·3+5。
- 左加數在指數 3 處沒有項,所以右邊的領先係數 1 不變。
| 算式 | 正規形 | 被吞掉的項 |
|---|---|---|
| α+β | ω^4·2+ω^3+ω·2+7 | ω^2·3+5 |
| β+α | ω^4·2+ω^2·3+5 | ω^3+ω·2+7 |
序型圖(每個 ω 塊只畫出頭三個點)
只有當所有序數都具 ω·a+n 的形式時才顯示圖。
- α
- ω^4·2+ω^2·3+5
- β
- ω^3+ω·2+7
- 原來次序: α+β
- ω^4·2+ω^3+ω·2+7
- 對調次序: β+α
- ω^4·2+ω^2·3+5
- 對這些運算元可交換
- 否
α+β = ω^4·2+ω^3+ω·2+7,但 β+α = ω^4·2+ω^2·3+5,而且 ω^4·2+ω^3+ω·2+7 > ω^4·2+ω^2·3+5:運算元的次序改變了結果,所以這個運算不可交換。
為何會出現吞掉
若 ξ < ω^γ 且 γ > 0,則 ξ + ω^γ = ω^γ:序型為 ξ 的一塊放在 ω^γ 前面會被吞掉,因為 ω^γ 在加法下不可分解。
所以在 α+β 中,α 內低於 β 的領先冪 ω^e 的每一項都被吞掉,高於 ω^e 的項則不受影響;這就是 1+ω = ω 而 ω+1 > ω 的原因。
運算元的指數取 0 至 6,係數取 1 至 9,每個至多四項。乘積的指數可達 12。所有比較都是精確的:序數以整數對的列表表示,不使用小數。
例題 3.2.9
(序數冪與基數冪回答不同問題)
序數冪 ,因為有限冪在自然數中無界。基數記號 則計數全部二值函數,等價於全部自然數子集,由 Cantor 定理不可數。看似相同的乘方記號,一處是有序遞歸極限,另一處是函數集合的大小,必須先看所屬的定義。
例題 3.2.10
(有限正規形可以含有不動點指數)
令 、,並取 。序列嚴格遞增;連續性及該序列的共尾性給出
這是最小正不動點:若 且 ,則它界住 ,歸納界住每個 ,故界住 。通常記為 。其正規形僅一項 。因此「有限正規形」不保證反覆展開指數後會得到只用自然數構成的有限表達式。顯示的共尾序列還給出 。
例題 3.2.11
(帶有指定共尾序列的奇異基數)
定義 , 為下一個初始序數,其存在由 Hartogs 保證,令 。此上確界仍是初始序數:任意較小序數都落在某個 之下,不可能與整個上確界等勢。指定序列共尾,而有限集不可能共尾於極限,故 ,它是奇異基數。序列由唯一的序數規則指定,沒有任意的同時選擇。
常見錯誤
常見錯誤
(不合規範的正規形)
正規形係數在右,指數嚴格遞減。留有零係數或相等的相鄰指數,就沒有寫成規範形式。正規形也不讓序數算術交換,更不表示基數決定序數。
常見錯誤
(共尾數不是單調的)
較大序數的共尾數未必更大: 的共尾數為 , 卻為一。
常見錯誤
(共尾映射不必遞增)
原共尾映射不必遞增,定理在最小基數長度上構造遞增版本。最後,在 ZF 中必須區分明確指定的序數列與為任意集合族逐項挑選枚舉。
總結
的冪遞增、連續且加法不可分解。反覆取領先冪及餘項給出唯一有限 Cantor 正規形。共尾數量度極限的另一面,它本身是正則基數,而原來的基數可能奇異。其他正則性論證中的選擇假設仍須明確指出。
練習
快速檢查
(兩種次序的正規形相加)
計算 與 按兩個次序相加的結果。
解答 · 答案
記兩者為 ,則 ,因為 被吸收;,因為 。被吸收項的有限尾部不會在最後再次相加。
快速檢查
(兩個等於 的共尾數)
給出共尾映射,證明 、,並說明有限長度不夠。
解答 · 答案
與 分別由乘法及乘方的極限定義給出共尾值域。兩目標都是非零極限,有限值域有最大元而遺漏更大前驅,所以共尾數恰為 。
快速檢查
(沒有統一上界的終止)
為甚麼正規形構造總能停止,卻沒有適用於全部輸入的固定有限項數界?給出項數任意多的例子。
解答 · 答案
不停止就會給出定義域為 的嚴格遞減序數函數,違背最小元性質。但對每個有限 , 都有 項。逐個輸入的終止證明不需要提供全部輸入共用的有限界。
快速檢查
(遞增共尾序列)
為甚麼可用最小基數長度的遞增共尾序列,而不改變 ?證明中的哪項構造提供該序列?
解答 · 答案
定義已給出某個從 出發的共尾映射,並排除更小基數。遞歸的運行上界 嚴格遞增、留在 內且支配原映射,所以仍有同一個最小定義域基數。較早值域已經是已給序數指標集的像,不需要另為它選枚舉。
快速檢查
(奇異基數)
奇異為何不違背共尾數的正則性定理?
解答 · 答案
定理應用於 時,指出它的共尾數是正則基數 ,沒有把 等同於 。兩者的差距正是此處「奇異」的含義。指定的 aleph 序列使這兩項結論同時成立。