動機
序數遞歸之所以可行,是因為每個階段的前驅都構成一個良序集合。許多構造具有不同的依賴模式:一個對象可以依賴若干更早的對象,而這些對象並不位於同一個線性序中。有限的表達式樹就是一個初等的例子。正確的要求是:每個由尚未完成的對象組成的非空集合,都含有一個其依賴對象已全部落在該集合之外的元素。
集合的屬於關係提供了最重要的實例。基礎公理(正則公理)說明,非空集合含有一個在其內部沒有前驅的成員。這使我們能夠給每個集合指定一個序數高度,即它的秩。在此之前,我們先證明使這類指定合法的一般遞歸原理。同一原理還把一個抽象的、良基且外延的關係,變成傳遞集合上真正的屬於關係。因此,坍縮與秩這兩個構造表達了兩個互補的想法:由前驅結構恢復出一個典範的集合,以及量度該結構向下延伸多遠。
定義
定義 1.2.1
(良基關係與外延關係)
設 是集合上的一個關係。當 是 的直接前驅時記作 ,並令 。若每個非空的 都含有某個 使得 ,則稱該關係是良基的。若 蘊含 ,則稱它是外延的。
定義 1.2.2
(向下封閉)
若 蘊含 ,則稱集合 是向下封閉的。令 包含 以及沿前驅方向經過有限步所到達的所有對象。具體地,從 出發,令 ,並取 。由替換公理與聯集公理,它是一個集合;它是包含 的最小向下封閉子集。
定義 1.2.3
(傳遞集合與累積層級)
若 蘊含 ,則稱集合 是傳遞集合。累積層級定義為 ,,並在非零極限序數處令 。序數一章已經證明了集合長度的超限遞歸,並驗證了這些階段是傳遞的且遞增的。
在本章中,所有關係都定義在集合上。真類上的一般遞歸需要額外的集合性假設,這裏並不隱含地包括它。
定理/命題
定理 1.2.4
(良基歸納與遞歸)
對集合 上的良基關係,若一個公式在 處成立的條件是它在每個 處成立,則它在整個 上成立。此外,設可定義的規則 在 且 是 上的函數時指定唯一的集合。則恰好存在一個 上的函數 滿足
不需要選擇公理。收集遞歸資料所依靠的是唯一取值條件與替換公理,而不是任意的同時選取。
定理 1.2.5
(集合關係的莫斯托夫斯基(Mostowski)坍縮)
若 上的 是良基且外延的,則存在唯一的傳遞集合 與唯一的同構 。它們由下式給出:
這裏的同構指滿足 的雙射。外延性對單射性是必要的;良基性對遞歸構造是必要的。
概念視角結構
坍縮作為完全不變量
對良基且外延的關係, 當且僅當兩者的坍縮有相同值域。若 是同構,則 是 到傳遞集合 上的同構,由唯一性得 ,值域相等。反過來,值域相等便給出同構 。由於帶屬於關係的傳遞集合就是自身的坍縮,這類結構在同構意義下恰好與傳遞集合一一對應。
定理 1.2.6
(秩與累積層級)
在 ZF 中,每個集合 都有唯一確定的序數秩
對每個序數 ,
因此每個集合都屬於某個層級階段。但這並不表示整個宇宙或整個層級是一個集合。
證明思路
證明
(極小反例與可容許點)
歸納法由分離公理得出:由反例組成的非空集合會有一個 -極小成員,這與假設矛盾。該論證既不需要線性序,也不要求每個非極小點都有一個直接前驅。
下面是遞歸的集合存在性證明。一個良好的部分函數,其定義域是向下封閉的,並且在該定義域上滿足所要求的等式。兩個良好函數在它們的公共定義域上一致。否則,它們不一致之處所組成的集合會有一個 -極小成員,其前驅上的限制一致,從而迫使下一個取值也一致。
若在 上存在良好函數,則稱 是可容許的。由上述相容性論證,這樣的函數是唯一的。若存在由不可容許點組成的非空集合,取其中一個 -極小者 。每個 都是可容許的。因此,替換公理收集集合 上唯一的良好函數;不需要選取見證。它們的並是 上一個相容的良好函數。此定義域包含 的每個前驅,而不包含 ,因為一條有限的回路會與良基性矛盾。再添上在 處唯一被指定的值。新的定義域恰為 ,這與 的不可容許性矛盾。因此所有點都是可容許的。替換公理把它們唯一的局部取值收集成 上的一個函數,而相容性證明了它滿足等式並且是唯一的。
證明透視
相容性不能代替收集
在遞歸證明的極小壞點處,相容性保證局部圖在重疊處一致。替換公理另外保證,這些唯一確定的圖構成一個以前驅集合為指標的集合。只有這樣才能取它們的並。這與在序數極限處所作的兩部分檢驗相同,只是現在應用於非線性有序的依賴結構。
證明
(前驅像與單射性)
對於坍縮,將遞歸應用於 。替換公理使這個像成為集合。值域 是傳遞的,因為 的每個元素都是某個滿足 的 。我們仍需證明單射性:前驅像的集合相等,並不經過論證就使原來的標籤相同。
對 作歸納,證明對每個 , 蘊含 。假設該斷言對每個 成立,並設 。對於 ,由 得到某個 使 ;在 處的歸納假設給出 。反過來,對於 ,像集合相等提供了某個 使 ,同樣的假設給出 。於是 ,由外延性得 。單射性使 成為到 上的同構。若另有一個同構,其值域是傳遞的,則 的像的每個成員都是某個前驅的像,因此它滿足同樣的遞歸。遞歸的唯一性使這兩個映射及其值域重合。
證明透視
單射性的歸納為何帶著全稱量詞
歸納只對 進行,但所傳遞的命題是「對每個 , 蘊含 」。我們對配對的 一無所知,所以在每個 處的假設必須已涵蓋所有可能的配對 。像相等使前驅在兩個方向上互相匹配,假設把每次匹配變成標籤相等,而外延性只用一次,把前驅集合相等變成 。良基性只透過歸納本身進入證明。
證明
(在傳遞界上遞歸定義秩)
對於秩,固定集合 。從 出發,反覆添加聯集,得到包含 的傳遞集合 。基礎公理使限制在 上的屬於關係是良基的:把它應用於 的任何非空子集即可。在這個集合關係上作遞歸,指定 。歸納法表明所有取值都是序數;於是該公式恰好就是 。兩個包含 的傳遞集合給出相同的值,因為它們的遞歸函數在其向下封閉的交集上一致。這樣定義的 與所選的上界無關。
對 作超限歸納以證明層級公式。在零處是顯然的。在後繼處,
最後的等價由取後繼秩的上確界得到,並且對空集 也成立。在非零極限處,屬於聯集意味著屬於某個更早的階段。這等價於秩小於該極限,因為任何更小序數的後繼仍然小於該極限。子集公式由後繼情形得出。特別地,。對所有序數階段取並是類的記號,並不是被允許的以集合為指標的並。
例題
例題 1.2.7
(坍縮不一定是序數)
取三個相異的標籤 以及關係 、,沒有其他的序對。它是良基且外延的。坍縮為 ,,。其傳遞值域為 ,它不是序數:其成員 與 按屬於關係不可比較,並且該關係不是傳遞的。坍縮產生的是傳遞集合,而不一定自動是線性有序的傳遞集合。
反例模式
刪去坍縮的任一假設
聲稱:集合上任何良基關係,或任何外延關係,都同構於某個傳遞集合上的屬於關係。對於兩個相異的孤立標籤,該關係是良基的但不是外延的:兩個前驅集合都是空集。遞歸把兩者都送到 ,所以它不是單射。對於帶有一個自環的單一標籤,該關係是外延的但不是良基的。坍縮將要求 ,從而 ,這與基礎公理相違。這兩個例子分離出不同的失敗方式,而不是把兩個假設視為可互換的。
例題 1.2.8
(秩不是成員的個數)
空集的秩為零,並且 。每個有限序數 的秩為 ,而超限歸納給出對每個序數都有 ,因為 。因此 的秩為 ,而它的單元素集的秩為 。單元素集儘管永遠只含一個元素,其秩卻可以任意大。秩量度的是屬於關係的深度,而不是基數。
例題 1.2.9
(集合首次被包含的階段要晚一步)
設 ,即序數二。它的秩為二,所以 但 ;它首次被包含的階段是 。對於庫拉托夫斯基(Kuratowski)有序對 ,單元素集與二元集的公式給出
所增加的兩個後繼階段來自兩層花括號,包括 的情形。把屬於與包含區分清楚,可以避免這兩個計算中差一的錯誤。
例題 1.2.10
(無限高度不需要無限下降道路)
取 ,其中 。自然數之間令 當且僅當 ,並對每個自然數規定 。關係良基:非空子集若遇到 ,便有最小自然數成員;否則只有 。坍縮把 送到 ,把 送到 。
從 向下走,第一步先到某個有限自然數,再在自然數間嚴格下降,所以不能無限繼續。但有限下降道路的長度沒有統一界, 處坍縮集合的秩為 ,不是有限數。故沒有無限下降道路並不意味著高度有限。秩取所有前驅高度的上確界,無限多個分別有限的高度可以有極限上確界。這也說明只計算幾個有限依賴圖,不足以證明一般遞歸定理。
常見錯誤
常見錯誤
(以「沒有下降序列」取代良基性)
在 ZF 的證明中,不應當悄悄地用「沒有無窮下降序列」來替代良基性的子集定義。給定一個無窮下降序列,取其值域即與良基性矛盾。但從一個每個點都有某個前驅的集合出發去構造這樣的序列,則可能需要依賴選擇原理。極小反例的定義避免了這一隱藏的選取步驟。
常見錯誤
(外延性關乎前驅集合)
的外延性涉及的是** 之內**的前驅集合。它不是標籤的通常相等,也不是關於 是傳遞的斷言。此外,在本文的展開中,秩依賴於基礎公理;同樣的論證不能用來給任意循環的屬於結構指定秩。
總結
良基遞歸可以解決具有唯一指定輸出的集合大小的依賴圖。外延性使前驅像遞歸成為單射,從而得到莫斯托夫斯基(Mostowski)坍縮。隨後,基礎公理與傳遞閉包給每個集合指定一個秩,而層級公式確切說明了它何時進入累積層級。
練習
快速檢查
(四點坍縮)
對 上的一個關係作坍縮,其前驅集合依次為 、、 與 。它的值域是序數嗎?
解答 · 答案
像依次為 、、 與 。值域是傳遞的,因為每個所列集合的每個成員都出現在這些像之中。它不是序數: 與 仍然不可比較。相異的前驅集合與所列出的無環依賴圖驗證了這些假設。
快速檢查
(屬於與包含下的秩)
證明 蘊含 。 是否蘊含嚴格不等式?
解答 · 答案
定義中的上確界至少為 ,這就證明了嚴格性。包含關係則只給出 ,這通過比較兩族後繼秩得到。即使對真子集,它也不一定是嚴格的:偶數自然數構成 的真子集,其秩同樣為 ,因為它們的有限後繼秩在 中是無界的。
快速檢查
(聯集的秩)
證明 ,包括空集的情形,並推出以 表示的上界。
解答
展開兩個上確界:
空上確界為零,所以該公式包括 與空成員的情形。由於右邊的每個秩都以 為界,所以聯集的秩至多是該秩。它可能更小: 的秩為一,但它的聯集的秩為零。
快速檢查
(沒有外延性的同構)
解釋為甚麼一個沒有邊的兩標籤關係,可以與配備限制屬於關係的集合之間有許多同構,儘管坍縮遞歸在每個標籤處只有一種可能的輸出。
解答 · 答案
一個合適的目標是 ,其中 :兩個成員都不屬於對方,也都不屬於自身。特別地, 的唯一成員是 ,它不同於 。它的兩個標籤可以按任一順序雙射地指派,從而給出空關係的兩個同構。這個 不是傳遞的。坍縮定理要求值域是傳遞的且源關係是外延的;空的兩標籤關係不滿足外延性,其遞歸把兩個標籤都送到零,而不是給出一個雙射。