動機
自然數歸納之所以成立,是因為非空反例集合有最小成員。同樣的原理適用於任意良序,包括所有有限階段之後的階段。序數為這些位置提供標準表示:一個序數恰好包含所有更早的位置,成員關係本身就記錄了次序。
無限過程不必以加上最後一步作結。極限階段沒有緊接在前的一步。定義過程必須說明極限處如何處理,通常是收集全部較早階段。歸納用於證明命題,遞歸用於定義對象;兩者關係密切,卻不能互相替代。
定義
定義 3.1.1
(良序、初始段與傳遞集合)
集合 上的嚴格良序是反自反、傳遞的線性序,且每個非空子集都有最小元素。若 且 總推出 ,則 是初始段。集合 稱為傳遞的,若 推出 ,等價地每個成員都是 的子集。
定義 3.1.2
(序數、後繼與極限)
序數是被 良序排列的傳遞集合。記 為 。最初的序數是 、、、。後繼為 。不是後繼的非零序數稱為極限序數。
概念視角結構
序數即由傳遞集合組成的傳遞集合
在基礎公理下,序數恰好是所有成員都傳遞的傳遞集合。在這種集合中,由 及 傳遞得 ;基礎公理給出反自反性與最小元。至於線性,取一個有不可比較配對的 -極小 ,再取這種配對中極小的 ;把各自的成員與對方比較,得 且 ,於是 ,兩者其實可比較。若沒有基礎公理,滿足 的集合會符合條件,卻不是序數。
無窮公理給出一個歸納集合 。在 內分離出屬於每個歸納子集的元素,得到最小歸納集合 。它確實歸納;把任意歸納集合與 相交,又可證明它包含於任何歸納集合。其成員正是有限 von Neumann 序數。每個有限序數的後繼仍在 內,所以 是極限序數。
定義 3.1.3
(序數集合的上確界)
序數集合 的上確界為 。它是序數,每個 的成員都包含於其中,而且它包含於任何序數上界。上確界未必屬於 ,也未必嚴格大於每個成員。
定理/命題
定理 3.1.4
(序數的比較)
對序數 ,、、 恰有一個成立。並且 當且僅當 。序數的每個成員都是序數;每個良序集合與唯一序數序同構。
定理 3.1.5
(超限歸納)
設 為序數。若對每個 ,都有
則 對所有 成立。若 是公式且此條件對每個序數成立,也可對全體序數歸納。
定理 3.1.6
(集合長度的超限遞歸)
假設可定義規則 對每個以序數為定義域的集合函數指定唯一的集合值。對每個序數 ,存在唯一函數 ,定義域為 ,滿足
唯一指定的下一值不需要選擇公理;收集較早階段則需要替換。
證明思路
證明
(初始段迫使可比較)
若 ,傳遞性給出 。若 ,這些位置都在 中,其成員序的傳遞性給出 。所以 傳遞,且限制的良序仍良序,故 是序數。序數的每個真初始段都恰好是最小遺漏元素 的前驅集,亦即 本身。
是兩者的初始段。若在兩者中都為真初始段,它等於兩者的某個成員。記該集合為 ,就有 ,與嚴格良序矛盾。因此其中一個序數是另一個的初始段,比較定理及包含判據隨即成立。嚴格良序沒有循環,故三個可能互斥。序數的並是傳遞的;比較使其成員線性排列。非空子集的最小元可透過先取一個成員,再在其前驅中尋找最小候選得到。這也證明聯集是序數及上確界。
證明透視
為何一個交集便能決定比較
整個比較只依賴一個集合 。它是兩個序數各自的初始段,而序數的真初始段就是它的某個成員。若它在兩邊都是真初始段,集合 便同時屬於 與 ,從而屬於 ,與反自反性矛盾。所以它等於其中一個序數,而該序數就是另一個的初始段。整個證明從未構造兩個序之間的同構。
證明
(最小反例)
對 內的歸納,若有反例,分離出反例集,其最小成員違背歸納條件。對全體序數,不必收集所有反例:任取反例 ,在集合 內找最小反例即可。
證明
(相容近似與替換)
遞歸中,把在定義域 上滿足規則的函數稱為近似。兩個近似在共同定義域上必相等:若有最小分歧點,此前限制相同,規則就給出相同下一值。對 歸納構造近似。零階段取空函數;後繼階段加入唯一指定的值;極限階段用替換收集所有較短的唯一近似,再取並。兼容性保證並是函數,且滿足規則。這個論證同時證明存在、唯一性和極限處的集合存在性。
證明透視
極限階段的兩項工作
遞歸證明同時有邏輯任務和集合存在任務。唯一性保證兩個部分構造在共同定義域上相等,因而它們的並單值;替換則為每個較短長度收集唯一近似,保證準備取並的族是集合。兩項任務不能互相取代。
後繼只增加一個圖像有序對,極限卻同時需要全部較早階段。若某步的規則不唯一,兼容性就不再自動成立;若指標不限制在一個序數內而遍歷所有序數,替換也不再給出全部階段的集合。定理用唯一輸出規則處理前一個問題,用每個集合大小的界分別構造處理後一個問題。隨後可寫對所有序數適用的可定義類記號,但它不表示定義域包含全體序數的單個集合函數。檢查遞歸時,先看兼容,再看收集,最後才取並;這也解釋了極限步驟為何需要超出普通後繼歸納的論證。
證明
(以序數分類良序)
對一般良序 ,沿此前驅初始段作同樣的良基遞歸,定義 。替換收集這些值。沿 歸納可證各值都是序數,且 等價於 。值域是傳遞的序數集合,因而是序數, 即所需序同構。兩個序數之間的序同構由歸納逐點固定成員,所以序數唯一。
例題
例題 3.1.7
(極限不是最大的有限數)
的上確界是 ,但沒有最大項。 有最後元素 ,而 沒有,所以二者不序同構。不過把額外點 送到 、有限 送到 ,就得到集合之間的雙射。
例題 3.1.8
(加法保留次序)
對第二個變元遞歸定義
其中 為非零極限。這表示先排一個 ,再排一個 。於是 ,但 。前者沒有最後一點,後者有。序數加法不交換,不能用基數加法替代。
例題 3.1.9
(乘法也保留排列)
定義 、,極限處取上確界。故 ,但 。後者有連續排列的兩個無限塊;在兩塊交界處,第一塊沒有最後一點,第二塊卻有第一點。這裏 是依次排列 個 。
例題 3.1.10
(全體序數不構成集合)
若它們構成集合 ,則 是序數。 也應屬於 ,從而 ,違背比較。可以對全體序數量化,卻不能把它們全體當成替換的輸入集合。
反例模式
只有基礎與後繼步驟並不足夠
聲稱:在零成立、並由每個序數傳到其後繼的性質,對所有序數成立。考慮「此序數有限」這個性質。零滿足它;只要 滿足, 也滿足,但 不滿足。故起點與後繼步驟不構成超限歸納。完整條件要求:若極限之前的每個位置都滿足,極限自身也必須滿足。本例恰在 缺少這項條件。
例題 3.1.11
(累積層級的後繼與極限步驟)
真正的極限論證通常用聯集代替最後一步。對 層級,可同時證明每層傳遞,且 時 。若 傳遞,每個成員都包含於 ,所以 。其冪集也傳遞: 推出 ,再由傳遞性得 ,即 。極限時,遞增傳遞集合族的並仍傳遞,因為 先把 放在某層,該層傳遞性又把 放在那裏。這些分別檢查了後繼與極限機制,而不是只畫不斷變大的集合。
例題 3.1.12
(不存在無限嚴格下降序列)
假設已有函數 ,從 取序數值。替換把值域收集為非空序數集,所以有最小成員 ;但 更小且仍在值域,矛盾。證明處理的是已經給出的下降序列。如果只說每次都能找一個更小元素,還須解釋如何把這些存在性選擇轉成整條序列;唯一或規範規則可以避免額外選擇。
遞歸方向也由此清楚。超限遞歸使用較小指標的全部值,是因為前驅形成良基範圍。依賴未來值的方程是另一個問題,未必存在解,也未必唯一。例如只要求二值序列為常數,就有兩個解;這不是定理中由以前資料唯一指定下一值的規則。證明與定義時都應先寫清依賴方向及定義域。
以拼接理解算術
加法與乘法的遞歸條款便於計算,但結合律、消去律、分配律這些常用規律很難直接從條款中讀出。換成圖像就清楚得多: 是一份 之後接一份 , 則是 份 首尾相接。下面把這幅圖像寫成定理,再從中讀出各條規律。下一單元 3.2 序數乘方、Cantor 正規形與共尾數 會直接使用這些規律。
定義 3.1.13
(有序和與有序積)
設 、 為良序。有序和 是集合 ,其中每個標記為 的點都排在每個標記為 的點之前,標記相同的兩點則按 或 的序比較。有序積 是集合 ,規定 當且僅當 ,或 且 :先比較 座標。對良序 ,記 為與 序同構的唯一序數。
兩者都是線性序,而且都是良序。 的非空子集若含標記為 的點,最小元就是其中最小的標記 點,否則是最小的標記 點。對 的非空子集,先取其中出現的最小第二座標 ,再取使 屬於該子集的最小 。逐座標套用序同構,可見序同構的加項或因子給出序同構的和與積;因此 與 只依賴 與 。
定理 3.1.14
(遞歸算術計算的是序型)
對所有序數 ,
證明
(兩邊滿足同一遞歸)
證明依靠序型的兩個事實。
(i) 若良序 有最後元素 ,則 。把 到序數 的序同構以 延拓,就得到 到 的序同構。
(ii) 若良序 是初始段集合 的並,則 。設 為序同構。它把每個 映到序數 的一個初始段;這個初始段若不是整個序數,便是它的某個成員,總之是序數,並由序型的唯一性等於 。這些像的並是 ,而序數集合的並就是其上確界。
固定 ,令 。當 時 ,且 是 的初始段。 是 的一份副本,故 。 的最後元素是 ,刪去後剩下 ,由 (i) 得 。設 為非零極限。 的每一點都落在某個 的 中:點 落在 中,且 ;標記為 的點落在 中。於是 (ii) 給出 。這正是定義 的三條條款,對 歸納即得 。
乘法方面,令 。由於 ,。 是 之後再接區塊 ,後者是 的一份副本;所以它與 序同構,由加法情形得 。在非零極限 處,每點 都落在初始段 中,且 ,故 (ii) 給出 。再對 歸納便完成證明。
定理 3.1.15
(序數算術的規律)
對所有序數 :
- ,且 。
- 若 ,則 。因此 推出 。
- 若 ,則 。
- 。
- 若 ,則恰有一個序數 使 。
- 若 且 ,則 。若 ,則 。
- ,且 。
證明
(每條規律都是拼接之間的序同構)
全程用到良序的兩個觀察。第一,良序 的真初始段 序型嚴格較小:序同構 把 映成一個序數的真初始段,即該序數的成員。第二,若有嚴格遞增映射 ,則 。與序同構複合後得到序數之間的嚴格遞增映射 ;下面關於遞增映射的練習給出每個 都有 ,故 。
(1) 與 都是 的副本, 與 亦然。
(2) 若 ,則 是 中遺漏 的初始段,因而是真初始段,序型較小。若 ,比較定理給出 或 ,兩種情況下兩個和都不相等。
(3) 由於 ,從 到 的包含映射嚴格遞增。
(4) 與 都是先一份 、再一份 、再一份 。具體地,、、 定義一個序同構。和的序型只依賴加項的序型,所以前者序型為 ,後者為 。
(5) 令 ,賦予 的序,並令 。 的每個成員都小於 的每個成員,且 ,所以 、 定義序同構 。故 ;唯一性就是 (2) 中的消去律。
(6) 若 且 ,則 是 中遺漏 的初始段。至於第二個斷言,從 到 的包含映射嚴格遞增。
(7) 與 定義序同構 :兩個序都先比較標記,再比較 或 座標,最後比較 座標。同樣, 是序同構 ,因為兩個序都依次比較 、、。
反例模式
雙邊規律不成立
聲稱:序數算術滿足自然數算術的其餘規律。以下每一條都不成立。
- 交換律:,且 。
- 右消去律,以及對左變元的嚴格遞增:,但 。同樣 。
- 右分配律:,而 。
每個例子中,加在左邊的部分都被一個沒有最後點的無限區塊吸收。在 中,新的首點之後接一份 ,整體序型仍是 。保留下來的正是單邊規律 (2)、(3)、(6)、(7)。
例題 3.1.16
(用規律計算)
由規律 (1) 及遞歸,。於是由結合律及 ,
其次,每個有限 都有 : 是規律 (1),而
在極限處,。由於 ,這個上確界等於 。若右分配律成立,結果應是 ,但由規律 (2) 它嚴格更大。每個區塊多出的最後一點都被下一個區塊吞沒。
常見錯誤
常見錯誤
(傳遞集合未必是序數)
傳遞集合未必是序數。例如 傳遞,但其成員 與 在成員關係下不可比較。
允許相等, 不允許。只證明後繼步驟會遺漏極限階段。
常見錯誤
(序數相等不等於存在雙射)
雙射不能證明序數相等:序數按序同構分類良序,基數才按雙射分類集合。
常見錯誤
(「一直繼續」不是遞歸)
「一直繼續」不構成遞歸證明;極限時須說明此前資料構成集合且兼容。
總結
序數以所有前驅表示良序位置。最小反例證明超限歸納;兼容近似與替換證明超限遞歸。有序和與有序積把遞歸運算等同於良序的拼接,單邊規律、減法與帶餘除法都可從這幅圖像讀出。極限及不交換的算術表明,無限序不能直接照搬有限直覺。
練習
快速檢查
(後繼的上確界)
證明非空序數集的並若為後繼,則該集合有最大成員。反向成立嗎?
解答 · 答案
若 ,則存在 使 。於是 ,迫使相等,故 最大。反向不成立: 有最大成員,但其並是極限 。有最大成員時,並等於這個成員,可以是零、後繼或極限。
快速檢查
(被 吸收)
證明有限 滿足 ,並依遞歸定義計算 。
解答 · 答案
有限歸納給出 有限,而且這些值在 中無界,故上確界為 。有限 滿足 ,取上確界得到 。
快速檢查
(最初幾個層級)
遞歸定義 ,計算 。
解答 · 答案
定義 、,非零極限處 。每步唯一指定一個集合,故可在任意序數界內遞歸。前三項是 、、,而 。
快速檢查
(遞增映射不小於恆等映射)
證明序數之間的嚴格遞增函數 對每個 滿足 。
解答
假設對 都有 。嚴格遞增給出 ,故每個 都屬於 。因此 ,比較定理給出所需不等式。超限歸納完成證明;尤其較大的序數不能嚴格遞增地嵌入較小序數。
快速檢查
(哪些序數在左邊吸收一點?)
求所有滿足 的序數 。
解答 · 答案
恰好是所有 。在有限序數上,加法遞歸就是自然數的遞歸,由構造自然數、整數與有理數可知它可交換;所以有限 滿足 。若 ,規律 (5) 把 寫成 ,結合律給出 。
快速檢查
(帶餘除法)
設 。證明每個序數 都可以唯一地寫成 ,其中 。
解答
存在性。由規律 (6) 與 (1),,所以有最小的序數 使 。它不是 ,因為 。它也不是極限:否則 ,因為由最小性每個 。故 ,且 。規律 (5) 給出 使 ,再由規律 (2), 化為 。
唯一性。設 ,其中 。若 ,則 ,矛盾;對稱情況相同。故 ,再由消去律 (2) 得 。例如 除以 ,商為 、餘數為 ;而 除以 ,商為 、餘數為 。