請先讀單射、初始序數、選擇公理及共尾性。良序集合的平方定理可在 ZF 中證明;將它應用於任意無限集合則使用選擇公理。後續不加限制的基數比較均在 ZFC 中進行。
動機
配對函數說明兩個自然數座標仍只有可數多種可能。每個無限基數都成立的相應結論卻不那麼直接:若直截了當地把不可數平方逐行排列,初始段可能過大。正確次序先處理最大座標較小的對,使每個較早的部分都受一個更小的平方控制。
加法和乘法隨後大幅簡化,指數卻不能同樣壓縮。Cantor 對角法已給出 。König 對角法分析另一障礙:即使候選列表分成許多部分,只要每個相應座標比該部分更大,乘積中仍有元素能避開整個列表。這會說明連續統不可能有可數共尾性,卻不會決定連續統的基數。
定義
定義 2.4.1
(基數的和、積與冪)
集合 的基數加法是帶標籤不交聯集的大小,乘法是笛卡兒積(Cartesian product)的大小,指數是函數集的大小:
雙射說明這些定義不依賴代表集合。對集合族, 指 的大小, 指相應選擇函數集的大小。選擇公理使每個集合都以某個初始序數作基數,因此這些量可互相比較。沒有選擇公理時,一般集合未必可良序。
以 記二元集合,特徵函數給出 。基數 的後繼基數 是嚴格較大的最小基數,不是序數後繼 。無限基數 的 是映入序數 的共尾映射所需的最小基數長度,定義見前章。
定理/命題
定理 2.4.2
(無限平方定理)
在 ZF 中,每個無限良序基數 都滿足 。因此在 ZFC 中,每個無限集合都與自身的笛卡兒平方等勢。若非零良序基數 至少一個無限,則
定理 2.4.3
(König 不等式)
在 ZFC 中,若每個 都有基數 ,則
比較的是整個不交和與整個乘積,並非兩個相應的和。
定理 2.4.4
(冪集的共尾性不能太小)
在 ZFC 中,對每個無限基數 ,
特別地,。這限制共尾性,並未證明連續統假設。
證明思路
證明
(以最大座標優先排列平方)
先說明無限初始序數是極限序數。無限序數 與 等勢:把新增的最後一點送到零,將每個自然數 送到 ,其餘點保持不動。因此無限後繼序數不能是其基數的最早代表。
反設平方定理失敗,取最小的反例無限基數 。將 按 優先、再按 、最後按 比較。任意非空子集依次最小化這三個序數座標,便得到最小對,所以這確為良序。最大座標為 的對之前的所有對,都落在 中。由於 ,令 。若 有限,平方仍有限;若無限,由反例最小性有 。故該良序每個真初始段的基數都小於 。
設它的序型為 。若 ,序型為 的初始段便有基數 ,矛盾。因此 ,給出平方到 的單射;反向有 。Cantor–Schröder–Bernstein 定理給出等勢,反例不存在。整個論證只處理已良序的集合,沒有暗中把任意集合良序化。
令 。乘積單射到 ,而兩因子非空使較大因子亦單射到乘積。不交和單射到 ,又包含較大加數的一份副本,所以兩個公式均成立。
無限良序字母表大小為 時,全部有限字串亦有大小 。歸納得每個正有限次冪大小為 。固定一個配對雙射,反覆使用它,便能為所有長度統一編碼;再以 標記長度,應用 。空字串僅增加一點。長度標籤不可省略,否則不同長度的字串可能得到相同編碼。
證明
(König 對角線論證)
對 König,直接取初始序數為各座標集合。假設存在滿射
對每個 ,集合 的基數至多為 ,因而漏掉 中某點。取最小的漏值 。函數 與每個 至少在第 個座標不同,所以不在值域內,矛盾。利用 ZFC 的基數可比性,不存在滿射便推出所述嚴格不等式。若 空,和為零,乘積為單點集,不等式仍成立。
證明透視
對列表的一整部分作對角化
Cantor 證明給每個列出的函數指定一個禁用座標。這裏許多輸入共用座標 ,但只有 個輸入,少於可用的 個值。因此能選一個避開整部分的座標值。不交和的標籤告訴我們用哪個座標擊敗輸入,並未假設已經枚舉整個乘積。
應用不等式前,先把指數律理解成函數的重排。不交聯集上的函數恰好對應一對函數;以函數為值的函數恰好對應兩個變量的函數。因此
這是基數公式,並不是對序數指數作同樣斷言。
證明
(短共尾族與 König 不等式矛盾)
令 ,反設 。取共尾族 ,,令 。這些基數的不交和恰好為 。上界方面,選定代表雙射後,不交和單射到 ,後者大小為 。下界方面,由於 是極限序數且該族共尾,每個 都嚴格小於某個 ;使用最小的這種指標,並利用代表雙射,把 編入帶標籤的和,就得到從 出發的單射。
每個 。現在 König 與指數律給出
矛盾。 的比較,是將 單射入 ,並在新增自變量處補零。這裏先證明平方定理與函數重排,再用它們完成推導。
證明透視
令冪集與眾不同的那條恆等式
論證分兩半。共尾性至多 ,就能把 寫成 個較小基數之和;König 不等式使這個和嚴格小於 個因子之積,而每個因子至多 。矛盾最終只依靠一條恆等式 ,它成立是因為 且 。若取 、,前一半仍然成立,卻只得到 ,並無矛盾,正符合 。選擇公理經由代表雙射和基數可比較性進入論證。
例題
例題 2.4.5
(可數序數的對)
的基數為 。這不表示序數乘法 等於 :前者在第一整塊後還有第二塊。基數運算忘掉次序,只問有否雙射。優先最大座標的良序控制前面的對,並未聲稱同一集合的各種良序有相同序型。
例題 2.4.6
(有限描述與無限串流)
可數無限字母表上的有限字串全體可數,但二進無限串流的基數為 。所以有限程式可數,並不表示全部無限輸出或實數都可計算。可變的有限長度對應可數聯集;無限長度對應函數集。混淆兩者便失去對角障礙。
例題 2.4.7
(可數聯集需要統一選取編碼)
在 ZFC 中,若每個 可數,可同時選單射 。對聯集中的元素,取它所屬的最小指標 ,再送到 ,便把聯集單射到 ,故聯集可數。在 ZF 中,逐個知道單射存在,不會自動提供整族單射。若這些單射本已作為資料給定,同一證明無需新的選擇。區別在編碼族的選取,而不在最後的配對公式。
例題 2.4.8
(連續統不能取的一個值)
前面的序數章證明了 ,所以新定理在 ZFC 中排除 。它不決定 是否成立,亦不決定所有尚未被此必要條件排除的值。這裏沒有使用力迫或相容性定理。
常見錯誤
常見錯誤
(無限基數不能消去)
無限基數能吸收自身的另一副本,所以消去律與減法不能照搬有限算術。從大小為 的集合中刪去同樣大小的子集,可能剩空集、一點,或仍有 個點。只知道兩個大小,不能決定餘集。
常見錯誤
(對所有集合的平方定理要用選擇公理)
ZF 中的平方證明針對可良序集合。推廣到所有無限集合使用良序原理,即選擇公理。可數聯集論證亦應說明整族枚舉從何而來。
反例模式
König 需要每個座標都嚴格
聲稱:若每個 都有 ,則 。取 ,並令 。和是集合 的大小,即 。乘積是 上取值都屬於 的函數全體,唯一的元素是 。因此
連非嚴格不等式也不成立。在證明中,集合 此時就是整個 ,不存在最小的遺漏值 。修正後的假設正是定理所述:每一個座標都有 。
基數指數計算函數,序數指數描述超限次序構造;符號相近,運算並不相同。
總結
優先最大座標的次序,在無選擇情況下證明良序無限基數的平方定理,由此得到非零和積的最大值規則與有限字串編碼。函數重排給出指數律,König 的逐座標對角法給出嚴格障礙。把它應用於假想的短共尾族,便得到 ,但不解決連續統假設。
練習
快速檢查
(對無限良序基數 ,證明 ,寫出雙向比較並指出平方定理的作用。)
解答 · 答案
由 得 。又由 得 。中間一步重排兩個自變量,最後一步用平方定理。再由 Cantor–Schröder–Bernstein 得等號。
快速檢查
(在 ZFC 中,設 無限,每個非空 的大小至多為無限基數 。證明 ,並說明何時必有等號。)
解答 · 答案
選擇公理同時選出單射 ,並良序化 。每個聯集元素選最小所屬指標,再送到 ,所以聯集單射到 ,大小不超過所述最大值。若聯集含有該最大大小的子集,便有等號;否則未必,例如所有非空 可以都是同一個單點集,即使指標集很大。在 ZFC 中,兩兩不交而非空的成員迫使聯集大小至少為 ;一個大小為 的成員迫使另一相應下界。
快速檢查
(直接以 König 證明 。計算左側,並以 給右側上界。)
解答 · 答案
每個 ,故 König 可用。令 。和不超過 ,又不小於每個 ,因此不小於其上確界 。故 ;上界把每個乘積元素視為取值於 的函數。這給出奇異基數處的嚴格指數界,並未算出該指數的確切值。
快速檢查
(說明大小為 的集合,不能由一個遞增可數族聯成,而各成員基數都嚴格小於 。不要預設統一大小上界。)
解答 · 答案
令 ,設聯集大小為 ,但 。若 ,可取一個無限基數 統一控制所有大小,於是聯集大小至多為 ,矛盾。因此 ,給出序數 的可數共尾族,與 衝突。有限上界情況可擴大至 。事實上不需要遞增性。
快速檢查
(構造 與 間的雙射,推出 。解釋為何這不提供一般公式 。)
解答 · 答案
把 送到 ;逆映射取這些帶標籤截面的聯集。二者互逆,空定義域亦適用。基數 表示額外不交的一點,拆分指數的定義域給出 。若 無限,這個乘積與基數和 碰巧都等於 ,但理由是無限運算,而非指數一般地對加法分配。有限例 已有 。