除明確指出額外選擇原則外,均在 ZF 中工作。使用完備度量空間的基本分析知識,不預設選擇原則的等價性或獨立性定理。
動機
有限次存在性選擇可以用歸納證明。但無限次連續選擇需要更謹慎:若下一次決定依賴之前的決定,知道每個有限階段都可延伸,還沒有直接給出一個無限序列。遞歸定理根據已指定的規則構造數值,不會把一個未指定選法的非空後繼集合自動變成規則。
可數選擇從一個固定集合序列的每個成員取一個元素;依賴選擇則容許每次新選擇依賴前一個狀態。樹使區別清楚:節點記錄已完成的有限決定,無限分支給出相容的全部完成。Baire 定理的巢狀球證明是有用的分析例子,因為下一球必須放進剛選好的球。
定義
定義 4.2.1
(可數選擇與依賴選擇)
可數選擇 指:對每個由非空集合組成的序列 ,存在函數 滿足每個 都有 。各集合本身不必有限或可數;可數的是指標集。
關係 稱為處處有後繼,若每個 都有 滿足 。本文使用帶指定起點的依賴選擇 DC:對非空 、處處有後繼的 及指定 ,存在以 為首項的序列,滿足每個 都有 。
定義 4.2.2
(樹、無終端樹與分支)
集合 上的有限序列樹是非空的 ,且對取前綴封閉,根為空序列。若每個節點 都有一步延伸 ,稱樹無終端節點。分支是函數 ,滿足每個 都有 。這些樹與函數空間在 ZF 中都是集合,不假設 已有枚舉。
定義 4.2.3
(無處稠密集與 Baire 空間)
度量空間中,一個集合的閉包若內部為空,稱該集合無處稠密。每個可數開稠密集交都稠密的空間稱為 Baire 空間。完備性指每個 Cauchy 序列都收斂到該空間中的一點。
定理/命題
定理 4.2.4
(這裏實際證明的蘊涵)
在 ZF 之上,
可數選擇亦推出可數個可數集的聯集仍可數。後者必須選出一整族編碼,不能只指出各編碼分別存在。
定理 4.2.5
(DC 等價於無終端樹分支原則)
在 ZF 之上,DC 等價於任意集合上的每棵無終端有限序列樹都有無限分支。對於任意分支數的樹,不能把「無終端」直接換成「有任意大有限長度的節點」。
定理 4.2.6
(DC 下的 Baire 定理)
假設 DC,每個完備度量空間都是 Baire 空間。特別地,非空完備度量空間不能是可數個無處稠密集的聯集。
證明思路
證明
(後繼函數、無終端樹與部分選擇)
在 AC 下,所有後繼集合 有選擇函數 。現在才用普通的 遞歸,從指定 定義 。這證明 AC 推出 DC,亦說明選擇規則來自哪裏。
假設 DC,令 無終端。把節點當作狀態,以一步延伸為處處有後繼的關係,從空節點開始。DC 給出 ,其中 且各步相容。它們的聯集是定義於 的函數,就是所需分支。反向,給定 上的 及 ,取空序列和所有以 開始的有限 -鏈構成樹。根可延伸為 ,非空節點由後繼性質可延伸,所以無限分支從 出發且一直沿 ,證明 DC。
要推出 ,取全部有限部分選擇構成的樹:長度 的節點滿足 ,。因為下一個單獨的集合非空,每個節點均可延伸。這裏只為一個節點驗證存在性,沒有同時作整族選擇;分支原則才提供無限相容的選擇函數。
最後設每個 可數。所有單射 組成非空集合 ,當 空時亦有唯一空單射。可數選擇同時取 。對聯集元素 ,取最小所屬指標 ,將它送到 ,便單射到已由顯式配對證明可數的 。從逐項存在編碼到實際編碼序列,使用的正是所述選擇原則。
證明透視
遞歸需要規則,不只是可能的下一步
後繼關係可能有許多輸出。遞歸在得到一個單值後繼函數後才適用,第一證明透過 AC 得到它。DC 則直接斷言存在相容鏈。在知道分支存在前,有限選擇樹已經無終端;逐點核實有延伸,並沒有暗中完成無限分支的構造。
證明
(依賴地選取巢狀閉球)
證明 Baire 時,設 是完備度量空間中的開稠密集, 是任意非空開集。構造閉球
使 、。這裏 表示閉度量球 ,它由三角不等式可知是閉集;沒有斷言它在一般度量空間中等於相應開球的閉包。
首球存在,因為 非空且開,取一點和充分小的正半徑即可。給定第 球,開球 與 相交。在交集中選一點,利用開性取更小閉球放進其中,半徑再限制為至多 。
要正當化無限繼續,取所有合格三元組 為狀態,條件為 、。將一個狀態關聯到第 層、且閉球包含於原開球內的狀態。前面的觀察證明關係處處有後繼。由一個第零層狀態出發,DC 給出所需序列。把層數包含在狀態中,才會保證下一要求是 ,而不是不確定的稠密集。
若 ,巢狀性使 ,所以 時 ,球心序列 Cauchy。設極限為 ;每個 閉且包含尾段球心,故包含 。於是 。 是任意非空開集,故交集稠密。空完備空間的稠密性陳述直接成立。
若 且各 無處稠密,則 開且稠密。 非空時,已證稠密性使這些 的交非空,卻與聲稱覆蓋全空間的聯集不交,矛盾。證明沒有使用球的緊緻性,亦沒有用收斂子序列定理;完備性和半徑趨零才是收斂機制。
例題
例題 4.2.7
(任意長有限路徑卻沒有無限路徑)
令 為空序列和全部自然數嚴格遞減有限序列組成的樹,取前綴仍在 。每個 都有長度 的節點,例如 時的 。但起於 的遞減序列長度至多為 ,所以沒有無限分支。以零結束的節點不能延伸,樹並非無終端,所以不違反 DC。這說明分支數不受限制時,只有無界有限高度並不足夠。
例題 4.2.8
(二元樹有規範的下一步)
對於 上的無終端樹,若補零仍在樹中就補零,否則補一;無終端性保證後一選擇存在。這樣已指定後繼函數,普通遞歸便在 ZF 中給出分支。一般分支原則處理任意標籤集合,不帶規範次序;不能從這個特殊二元情況判斷它的全部強度。
例題 4.2.9
(有理數直線缺少完備性)
通常度量的 中,單點集閉且內部為空。因此可數集 是可數個無處稠密集的聯集,不是 Baire 空間。完備性失敗:逼近 的二進有理數構成 Cauchy 序列,卻沒有有理數極限。Baire 構造仍會產生 Cauchy 球心,但最後缺少空間中的落點。
例題 4.2.10
(給定可數資料能消去一次選擇)
假設完備度量空間帶有指定的可數稠密序列,枚舉以這些點為球心、正有理數為半徑的所有球。任意非空開集內都有這樣的球,連同其閉球亦在該開集內:先取小環境球,再取附近稠密點及更小有理半徑。巢狀球的每一步便選滿足包含關係和半徑界的最小指標。這是唯一指定的規則,所以 Baire 構造可在 ZF 中遞歸進行。最小合格指標未必可計算,因為未假定集合包含條件可判定。規範的數學選法與有效算法是不同斷言。
常見錯誤
常見錯誤
(可數選擇計算的是指標集,不是各成員)
可數選擇中的各集合本身不必可數。另一方面,有限選擇可在 ZF 中歸納證明,卻不能據此跳到無限多次相容選擇。「依此繼續」必須給出後繼規則,或指出產生序列的原則。
常見錯誤
(特殊樹不能推出完整的 DC)
分支原則涉及任意集合上的每棵無終端樹。標籤已良序的特殊樹可作規範選擇,並不會單獨推出完整 DC。本文只證明了給定的正向蘊涵和一個特定等價關係,沒有建立模型論的逆向失敗或獨立性結論。
在 ZF 中兩個箭頭都不能反轉,而 Baire 定理其實與 DC 本身一樣強。
自然延伸的下一個問題
這些蘊涵能否反過來?
在 ZF 中兩個箭頭都不能反轉,而 Baire 定理其實與 DC 本身一樣強。
兩個正向蘊涵都不能反轉。若 ZF 一致,則存在可數選擇成立而 DC 不成立的 ZF 模型,也存在 DC 成立而 AC 不成立的 ZF 模型;這些模型以力迫法和對稱模型方法構造,超出本課程範圍。另一方面,已知在 ZF 上,完備度量空間的 Baire 定理蘊涵 DC,所以巢狀球證明中對 DC 的使用一般無法避免。
常見錯誤
(完成 Baire 論證的是完備性,不是緊緻性)
Baire 證明需要稠密集開,才能放進下一閉球;極限要留在定義域內,則需要完備性。閉球未必緊緻。半徑即使趨零,若無完備性,交集仍可能為空。
反例模式
不開的稠密集可以互不相交
聲稱:在完備度量空間中,可數多個稠密集的交總是稠密。在帶通常完備度量的 中,取
兩者都稠密:區間 含有有理數,而 含有有理數 ,於是 。若 ,則 且 ,其中 ,於是 會是有理數。因此 。巢狀球證明在第一步便失效: 不含任何區間,放不進半徑為正的閉球。定理要求稠密集是開集,正是這一點使每個新閉球能放進下一個 。
總結
AC 提供後繼函數,進而給出 DC;DC 恰好等價於任意無終端樹有分支,並提供可數同時選擇。可數選擇使分別存在的可數編碼成為一個整族。Baire 的巢狀球證明顯示依賴選擇的步驟;有指定可數資料時,有時能用規範規則取代這一步。
練習
快速檢查
(在 ZF 中證明有限選擇。若一個非空可數集的可數族有可數聯集,直接說明它有選擇函數,不要分別選取各成員的枚舉。)
解答 · 答案
零個集合用空函數。若一個有限族已有選擇函數,再加入一個非空集合,只須取其中一個元素來延伸。存在性歸納證明每個有限斷言,並未選擇無限族。對題設可數族,固定一個單射 ,它由聯集可數性提供。從 取唯一元素,使其 值為非空集合 的最小元。替換公理收集這個唯一確定的選擇函數,無須整族分別枚舉。
快速檢查
(設 已良序、 處處有後繼,在 ZF 中由指定起點構造鏈。若 且 可判定,為何所得鏈可計算?)
解答 · 答案
定義 為給定良序下最小的 -後繼,後繼性質保證存在,再遞歸令 。若底集為 且 可判定,按 搜尋,直至 ;後繼性質保證終止,逐次搜尋便計算每項。任意抽象良序卻未必提供「取最小元」的算法。
快速檢查
(去掉開性後,證明實直線的可數個稠密子集之交未必稠密,只須用兩個不同稠密集。)
解答 · 答案
取 ,每個 取 。有理數和無理數都稠密:任意區間有有理數,亦可用充分小的無理數倍移位得到無理數。它們的交為空。這兩個集合在通常實拓撲中都不開,故不違反 Baire 定理。
快速檢查
(構造 中非空閉球的巢狀序列,半徑趨零而交為空。使用包含 的二進區間。)
解答 · 答案
令 ,取 。二進區間巢狀,端點有理且非空,在 中是中心 、半徑 的閉球。相應實區間都含 ,直徑趨零,故在 中交為 ,在 中則為空。障礙是缺失極限,並非巢狀失敗。
快速檢查
(有些 DC 定義只要求每個非空且處處有後繼的關係有鏈,不指定首項。在 ZF 中證明這種無指定起點的形式推出本文指定起點的形式。)
解答 · 答案
給定 ,以所有從 開始的非空有限 -鏈為狀態,以一步延伸為關係。至少存在單項狀態 ,關係處處有後繼。無指定起點的原則給出這些有限狀態的無限鏈,即使從較長狀態開始亦無妨。各狀態相容之聯集定義於整個 ,從 開始且沿 。定義域確為 ,因為每步有限長度增加一。這樣,指定起點已編碼入狀態空間。反向只須忘掉指定起點。