動機
從一個非空集合取一個成員是存在量詞的實例化,有限次重複也不成問題。但這不等於存在一個函數,為任意無限集合族同時選取成員。選擇公理正是額外斷言這種函數存在。
獨立集延拓為基、偏序集中存在極大對象,看似與選擇無關,卻與它等價。這類工具在沒有顯式算法時尤其有用,但假設必須檢查。極大不是最大;每對元素有上界,也不能取代每條鏈有上界。
定義
定義 4.1.1
(選擇函數與選擇公理)
對集合索引的非空集合族 ,選擇函數是定義域為 且 的函數。選擇公理 AC 斷言每個這樣的族都有選擇函數。輸入族必須是集合;AC 沒有提供全體非空集合這個真類上的統一選擇函數。
定義 4.1.2
(鏈、上界與極大元素)
偏序具有自反、反對稱、傳遞性。鏈是其中任意兩個成員都可比較的子集。 的上界 滿足每個 都有 ,但不必屬於 。 是極大元素,若 總推出 ;它是最大元素,若所有 都有 。
定義 4.1.3
(良序原理與 Zorn 引理)
良序原理說每個集合都可賦予良序。Zorn 引理說,非空偏序集中若每條鏈都有上界,則存在極大元素。空鏈的上界可取任意成員。
定理/命題
定理 4.1.4
(Hartogs 定理(ZF))
每個集合 都有一個不能單射到 的序數,可取最小者 。不必先假設 可良序。
定理 4.1.5
(ZF 上選擇公理、良序原理與 Zorn 引理等價)
在 ZF 上,AC、良序原理、Zorn 引理彼此等價。
定理 4.1.6
(基延拓(使用 AC))
域上的向量空間 的任意線性無關子集 都包含於某個基 。
證明思路
證明
(超越子集上一切良序的序數)
的子集上的全部良序可編碼為 中的對 ,因而構成集合。替換收集其唯一序型為集合 。令
若 單射到 ,在像上運輸它的良序,就有 ,從定義推出 ,矛盾。故存在失敗的序數;在 內分離並取最小者,得到 。沒有一步要求為整個 先選良序。
證明
(AC 推出良序原理)
由 AC,對非空 的全部非空子集取選擇函數 ,並固定 。在 遞歸:若尚有未取元素,從剩餘集合用 取一個;否則取 。若始終沒有取盡,各值互異,就得到 ,矛盾。因此某個較早階段已取盡;此前的無重複枚舉把一個序數的良序運輸到 。空集本身已良序。這給出了嚴格的停止界,而不是含糊地說「一直取到完」。
證明透視
Hartogs 提供停止的界
遞歸沿預先固定的序數 進行,因此不需要含糊的「取到完為止」。選擇只出現一次,就是 的非空子集上的單一選擇函數 ;此後每一步都由先前的值唯一確定。預設值 只是讓遞歸在取盡之後仍有定義。
關鍵一步是與 的定義矛盾。若每個階段 的剩餘集合都非空,每個值都與先前所有值不同,便得到單射 。因此某個階段的剩餘集合為空。在最小的這種階段 , 之前的值互不相同且取盡 ,所以 是雙射 ,把 的次序運輸到 。
證明
(良序原理推出 Zorn 引理)
由良序原理,給 Zorn 假設中的 一個良序。依次遍歷,某元素若與此前已取的每個元素可比較,就加入 。遞歸所得 是鏈,而且是按包含關係極大的鏈:若 與整個 可比較,它在自己的階段就會被加入。設 是 的上界。若 ,則 與整個 可比較,故 ,從而 ,矛盾。所以 是 的極大元素。
證明透視
為甚麼極大鏈的上界是極大元
上的良序使遍歷成為每一步只有一個結果的遞歸,所以構造 時不再作任何選擇。真正的想法是 在鏈之中是極大的:與 每個成員都可比較的元素早已在 中。把這一點用於上界 ,便知 屬於 並且是其最大成員;用於假想的 ,便迫使 。Zorn 的鏈條件只用了一次,就是用於這一條鏈。良序的第一個元素必定被加入,所以 非空保證 非空。
證明
(Zorn 引理推出 AC)
由 Zorn 推出 AC:把所有部分選擇函數按延拓排序。其圖像屬於 ,所以這是集合,並含空函數。一條鏈的並仍是部分選擇函數,因為同一指標的兩個值出現在可比較的函數中,必相同。這個並是上界。極大部分選擇函數若遺漏 ,從一個非空 取一個成員就能延拓,矛盾。因此定義域是 。這裏取一個集合的一個成員,並沒有循環使用 AC。
證明
(以 Zorn 引理延拓為基)
基延拓中,把包含 的線性無關子集按包含排序。非空鏈的並 仍線性無關:任何線性關係只涉及有限多個向量,鏈中有限多個承載它們的成員有最大者,所以關係已在一個無關集中,全部係數為零。空鏈以上界 處理。Zorn 給出極大 ;若 ,則 仍無關,矛盾。故 生成 ,並為基。
例題
例題 4.1.7
(極大不等於最大)
的真子集按包含排序,、 都極大,沒有最大者。極大無關集不需要包含每個向量,只要求再加入任何向量都會破壞無關性。整個向量空間還含零向量,當然不會作為一個向量集線性無關。
反例模式
每對元素有上界不足以用 Zorn
聲稱:若非空偏序集中每對元素都有上界,則它有極大元素。正整數通常序中,每對元素都有上界,即較大者,但沒有極大元素。全部正整數這條鏈沒有整數上界,故缺少的 Zorn 假設是真正的障礙。
例題 4.1.8
(規範選擇無需 AC)
有限非空集合族可按族的大小歸納構造選擇函數。對任意非空自然數子集族,可取每個集合的最小元,再用替換收集唯一值。因此無限集合族也可能因存在統一規範而無需 AC。
例題 4.1.9
(延拓線性泛函)
設 是子空間, 線性。取 的基 並延拓為 的基 。在 上保留 的值,在 上賦零;唯一有限基展開定義線性延拓 。依賴選擇的是基的存在,基固定後公式唯一。這是代數結論,沒有聲稱連續性。
例題 4.1.10
(極大理想為何產生域)
下面練習中的極大理想還有重要用途。若 是有單位交換環 的極大真理想,則 是域。取非零陪集 ,即 。理想 真包含 ,故等於 。因此存在 ,使 。模 化簡得到 ,每個非零陪集都有逆。 為真還保證 。
反過來,若 是域,且理想 真包含 ,取 。非零陪集 有逆 ,所以 。又 ,相減得 ,故 。這證明極大性與商環為域等價,也說明極大對象達到了甚麼數學目的。
依賴選擇的存在性與後面的商環運算作用不同。某個極大理想一旦給定,證明它的商為域不需要新增任意選擇;每個非零陪集的逆唯一。類似地,Zorn 可給出基的存在,而座標唯一性由有限線性無關性證明。分開這些步驟,就能準確指出應用中 AC 出現在哪裏,而不把整段代數計算籠統歸為「使用選擇」。
旁註
唯一答案無需額外任意選擇
具有唯一見證的存在斷言與 AC 所處理的集合族不同。若一個集合中的每個輸入恰有一個輸出,ZF 的替換已能收集輸出及其函數圖像;沒有備選項,就不必另作選擇。域中非零元素的唯一逆、相對於固定基的唯一座標都是例子。
反之,滿射的每個纖維可能有許多點。構造右逆需要為每個纖維取一點;定義域已有良序時可以規範地取最小點,沒有這種結構時,同時選取就是另一個問題。區分二者可以避免兩種相反錯誤:無規則地挑代表卻忽略 AC,或見到「對每個」就不必要地援引 AC。關鍵不在指標集是否無限,而在已有資料是否唯一指定所需值。特別地,基存在可能依賴選擇,固定該基之後的有限座標運算卻不因此每步都需要重新選擇。清楚標明這條界線,會使代數應用的公理依賴更容易檢查。
可比較性與有限特徵
實際應用中還常見另外兩種形式的選擇。第一種關於大小:沒有選擇時,兩個集合甚至未必能用單射比較。第二種把基延拓證明中的取並論證抽出,成為可以反覆使用的引理。
定理 4.1.11
(大小的可比較性等價於 AC)
在 ZF 上,選擇公理等價於以下命題:對任意集合 、,存在單射 或單射 。
證明
(把集合與它的 Hartogs 序數比較)
設 AC 成立。由良序原理,有雙射 及 ,其中 為序數。序數比較給出 或 。前一情況下,經包含 理解的 是單射 ;後一情況下, 是單射 。
反過來,設可比較性成立,並任取集合 。把 與 Hartogs 定理給出的序數 比較。按定義 不能單射到 ,所以存在單射 。規定 當且僅當 ,便在 上得到良序:它是序數集合 的成員序沿單射拉回的結果。因此每個集合都可良序,由上面的等價定理得 AC。這個論證只用到集合與一個序數之間的可比較性。
定義 4.1.12
(有限特徵的集合族)
設 為集合。若對每個 , 當且僅當 的每個有限子集都屬於 ,則稱集合族 具有限特徵。
有限特徵的集合族對子集封閉:若 且 ,則 的每個有限子集都是 的有限子集,因而屬於 ,故 。向量空間的線性無關子集組成這樣的集合族,因為一個線性關係只涉及有限多個向量。偏序中的鏈亦然,因為可比較性是對每對元素的條件。
定理 4.1.13
(Tukey 引理)
設 AC 成立, 是集合 上具有限特徵的集合族。則 的每個成員都包含於 中某個按包含關係極大的成員。在 ZF 上,對所有具有限特徵的集合族成立的這個命題等價於 AC。
證明
(有限特徵保證鏈的並仍然合格)
固定 ,令 ,按包含排序。在 內分離可知它是集合;它含 ,而 也是空鏈的上界。設 是 中的非空鏈,。 的有限子集 中每個 都屬於 的某個成員。這有限多個成員兩兩可比較,所以其中有一個 包含其餘各個,該有限子集便落在 中(空子集落在任何成員中)。由對子集封閉,它屬於 。由有限特徵得 ,且顯然 ,故 是 中的上界。Zorn 引理給出 的極大元素 。若 ,則 ,所以 且 。因此 在 中極大。
反方向:設 是非空集合族,令 。子集 是某個部分選擇函數的圖像,當且僅當其中沒有兩個有序對第一座標相同而第二座標不同。這是對二元子集的條件,所以這些圖像組成含 的有限特徵集合族。其極大成員在每個指標處都有定義,因為若遺漏指標 ,就可以用 的一個元素把它延拓。所以它是選擇函數。
例題 4.1.14
(每個偏序都可延拓為線性序)
設 為偏序。考慮所有包含 的偏序 ,按包含排序。其中非空鏈的並仍是包含 的偏序:自反性自然保留,而檢查反對稱性或傳遞性時涉及的兩三個有序對都落在鏈的同一個成員中。空鏈以 本身為上界。Zorn 引理給出極大的 。
假設某對 在 下不可比較,令
它含 ,且自反。傳遞性:取 。若兩者都在 中, 也在。若只有 是新的,則 且 ,所以 是 的新有序對;只有 是新的情況對稱。若兩者都是新的,則 ,與不可比較矛盾,所以這種情況不會出現。反對稱性:設 且 。兩者不能都在 中。若其中之一,例如 ,是新的,則 且 ;另一個有序對給出 ,或者若它也是新的,則給出 及 。每種情況都推出 ,不可能。所以 是嚴格大於 的偏序,與極大性矛盾。因此 是延拓 的線性序。若 有限,把這一步延拓重複有限次,不用任何選擇原理即得結論。
常見錯誤
常見錯誤
(鏈不是序列)
鏈在給定的偏序下是全序的;它不必是序列,可能不可數。
常見錯誤
(取聯集還不是上界證明)
「取聯集」不是完整的上界證明,必須檢查定義性質仍成立。無關性的有限特徵保證該例成功,閉性或完備性卻未必在並下保持。
常見錯誤
(Zorn 給出存在,不給出唯一性或獨立性結果)
Zorn 不給出唯一對象,也不指定算法。這些等價不證明 AC 是 ZF 定理,也不證明其否定;獨立性與相對相容性需要本節以外的元數學。
總結
Hartogs 給出集合大小的停止界。AC 產生良序,良序構造極大鏈,Zorn 把部分選擇函數補全。大小的可比較性與 Tukey 引理是另外兩種等價形式;後者把線性無關集的取並論證變成一般工具。應用極大性時依次檢查非空、每條鏈的上界,以及極大對象為何具有目標性質。
練習
快速檢查
(設滿射 的陪域非空,且定義域、陪域都可良序,證明它有右逆。真正用於選擇的是哪一個良序?)
解答 · 答案
良序 ,對每個 取非空纖維 的最小元 。替換給出函數,且 。真正選擇來自 的良序, 可良序的條件其實多餘。
快速檢查
(詳細證明向無關集 加入 後仍無關。)
解答 · 答案
若 ,其中 互異, 會把 表為 的有限線性組合,矛盾。故 ,再由 無關得所有 。不含 的關係本來就受控制。
快速檢查
(用 Zorn 證明有單位交換環的每個真理想包含於極大真理想,說明鏈的並為何仍真。)
解答 · 答案
所有包含 的真理想組成非空偏序集。非空鏈的並是理想,因為任意兩元素同屬某個鏈成員,可在那裏完成加法及乘環元素。若並含 ,某個成員已含 ,就等於整個環,矛盾。空鏈以上界 處理。Zorn 給出的極大成員不能再包含於更大的真理想,否則仍在此偏序集中。
快速檢查
(解釋無限集合的有限子集按包含排序時,為何不自動滿足 Zorn 假設。)
解答 · 答案
鏈的並可能無限,從而不屬於有限子集偏序集。取 ,鏈 沒有有限上界,就足以反駁一般斷言。對有限個成員有上界(有向性)並不足夠。在 ZF 中討論任意無限 時,也不能暗中預設能選出可數無窮個不同元素。
快速檢查
(用 Tukey 引理證明 Hausdorff 極大原理:偏序集中的每條鏈都包含於某條按包含關係極大的鏈。)
解答 · 答案
子集 是鏈,當且僅當它的每個二元子集都是鏈,亦即當且僅當它的每個有限子集都是鏈。所以鏈在 中組成具有限特徵的集合族,Tukey 引理把任何鏈延拓為極大鏈。極大只表示沒有鏈真包含它。在按包含排序的 中, 與 是兩條不同的極大鏈。
快速檢查
(設 AC 成立。證明 作為 上的向量空間,有一個同時包含 與 的基。)
解答 · 答案
在 上的線性無關性具有限特徵。 線性無關:若 , 且 ,則 為有理數,矛盾;所以 ,從而 。Tukey 引理把 延拓為極大線性無關集 。與基延拓的證明相同,若 ,則 仍線性無關,矛盾;故 生成 。
快速檢查
(在 ZF 中證明:能單射到某個可良序集合的集合本身可良序。這一步出現在可比較性證明的哪裏?)
解答 · 答案
設 為單射, 是 上的良序。規定 當且僅當 。它反自反、傳遞,並因 迫使 而線性。非空 使 非空,其最小元恰為某個唯一 的像 ,而這個 就是 中的 最小元。在可比較性證明中,這正是從單射 得到 上良序的一步,其中 扮演可良序集合。