動機
數一個集合有多少個元素,結果不應取決於先數哪一個。這句熟悉的話其實包含一個定理:兩個不同的自然數之間不可能有雙射。同一個證明還會說明,為何有限集到自身的單射必定是滿射,以及集合變成無限集後,論證在哪裏不再適用。
本節在 ZF 中工作,使用已經構造的自然數及其算術。這裏 表示有限序數 ,因此 。需要可數選擇時會明確說明。本節補足基數章節的初等論證依據。
計數與抽屜原理
定義 2.3.1
(有限集與無限集)
若某個 與集合 之間存在雙射 ,就稱 為有限集。若不存在這樣的自然數,就稱 為無限集。此時我們尚未證明這個 唯一。有限序數自帶特定的次序;一個任意給定的有限集則未必附有次序或首選的枚舉。
定理 2.3.2
(有限抽屜原理)
對每個自然數 ,都不存在單射 。更一般地,若存在單射 ,則必有 。
證明
(以交換作歸納)
對 歸納。非空集 到空集 連函數也不存在。歸納步驟中,假定不存在單射 ,卻存在單射 。令 。在目標集合 上,定義置換 :交換 與 ,其餘元素不動;若 ,則取恆等置換。於是 仍是單射,且 。
由於單射性,其他輸入都不能映到 。把 限制在輸入 上,就得到單射 ,與歸納假設矛盾。第一項結論得證。若 ,把任何假定的單射 限制在前 個輸入上,又會違反第一項結論。
證明中的交換並非多餘步驟:它把一個已佔用的目標位置移到最後,使我們刪去最後一個輸入時,也能刪去最後一個目標位置。隨意各刪一個輸入與目標,並不能保證餘下的映射具有所需的陪域。
如果 和 都是雙射,用其中一個的逆與另一個複合,就得到 與 之間的雙射。定理給出 和 ,所以 。現在才能無歧義地寫有限集的基數 。特別地,空集的基數是零,而非空集的基數不可能是零。
子集、像與有限集的自身映射
先證明一條不會循環使用待證結論的封閉性質:有限集的每個子集都是有限集。只需考慮 ,並對 歸納。 時只有空子集。對 ,令 ;由歸納假設, 有限。若 ,則 。若 ,取雙射 ,再把新輸入 映到 ,就把它延伸成雙射 。對任意有限的母集,沿著它的一個枚舉把結論轉移過去即可。
基數為 的集合,其真子集的基數嚴格小於 。為證明嚴格性,設 ,取 。此時 ;交換 與 後再限制,得到雙射 。因此 單射到 。 已知有限,抽屜原理便給出 。 時根本沒有真子集。
有限集的像也有限。給定 ,對每個 取它在 中的最小原像。這些最小原像組成子集 ,而 是雙射。由子集的結論,像是有限集。最小原像由現成的有限次序唯一指定,不需要選擇公理。
定理 2.3.3
(有限集的自身映射:單射當且僅當滿射)
若 有限且 ,則 為單射當且僅當它為滿射。
證明
(兩個方向都化為抽屜原理)
用一個枚舉及其逆把問題轉成 。若 單射卻遺漏了某個元素,其像便是真子集,基數為某個 。再把像雙射到 ,就得到單射 ,與抽屜原理矛盾。
反之,設 滿射。令 包含每個目標的最小原像,則 雙射到 。若 不單射,某個纖維中至少有兩個不同的輸入,只有最小的那個屬於 ,故 是真子集。它的基數便小於 ,與存在雙射 矛盾。這也包括 :空的自身映射既單射又滿射。
例題 2.3.4
(無限集上的兩個反例)
位移 定義為 ,它是單射,卻遺漏零。另一方面,令 ,並令 。這個映射滿射,因為每個 都是 ;它卻不單射,因為 。有限定理的兩個方向分別由兩個不同的映射推翻了。單射與滿射的定義並沒有改變。
哪些構造保持有限性
設 、,固定枚舉 和 。在一個證明中取兩個存在性見證是有限的邏輯操作,不是使用選擇公理。
帶標記的不交並 與 雙射:前 個位置用於第一種標記,其後 個位置用於第二種標記。忘掉標記就得到從這個有限集到 的滿射,所以普通聯集有限,基數至多為 。如果 與 有交疊,等號未必成立。
積 的基數是 。若某個因子為空,結論直接成立。否則,以編號 枚舉 ,其中 。帶餘除法為每個小於 的編號給出唯一的逆像。再與 複合,就得到所需雙射。歸納可知,由有限集作指標的一族有限集,其並與積仍有限。初始情況分別是空聯集與空積:前者為空集,後者只有空函數這一個元素。這裏的歸納證明每個有限枚舉族的存在,並沒有選出一個無限的枚舉族。
的冪集基數為 。從 開始,它有 個元素。若 ,則 的每個子集恰有一種形式:或者是 ,或者是 ,其中 。兩種形式互不混淆,所以新冪集與 雙射。歸納給出 。
概念視角組合
把子集看成二元記錄
子集 與它的指示函數 攜帶相同資訊;這裏 當且僅當 。映射 是由 到全體函數 的雙射,其逆映射為 。透過一個枚舉 ,這樣的函數就是 個二元位置的記錄。加入一個新元素就多一個位置,這正是上面歸納中的因子 。
例題 2.3.5
(交疊會改變計數)
取 、。帶標記的不交並有五個元素,普通聯集 卻只有四個。積有六個元素,其中 與 是不同的有序對。 的冪集為 、、、,共有四個元素。這些構造雖然從同樣的兩個有限集開始,得到的對象並不相同。
例題 2.3.6
(每條記錄有限,不表示所有記錄組成有限集)
每個函數 的圖都恰有三個有序對,因為 是到該圖的雙射。然而所有這些函數組成的集合是無限集:對每個 ,常值函數 都給出不同的函數。有限的定義域使每條記錄有限;要使全部可能記錄組成有限集,還需要每個位置只有有限種取值,並且位置數也有限。
從無限的像中去除重複
給定一個無限集,與給定一個到訪其中無限多個元素的序列,是兩種不同的資訊。不過,一旦序列已經給定,就可以不用選擇公理去掉重複。
定理 2.3.7
(無限的像包含一個由序列確定的可數子集)
若 的像是無限集,就能僅由 定義一個單射 。
證明
(保留每個值的首次出現)
只保留每個值首次出現的位置。準確地說,由分離公理得到
像中的每個元素都有最小的出現下標,因此 是 到該像的雙射。若 有限,由有限像結論可知 的像也有限,矛盾。因此 是 的無限子集。
的每個無限子集都無上界,否則它會落在某個有限序數內。定義 ,並遞歸定義 。無上界保證每次取最小值的集合都非空。各步的值唯一確定,普通遞歸與替換公理便構成完整函數 。最後令 。這些下標嚴格遞增且屬於 ,所以對應的值兩兩不同。
證明透視
取最小值已經指定了規則
證明中取了無限多次最小值,但並未調用一個保證任意同時選擇存在的公理。每一步中, 已有的次序都指定了唯一的下一個下標;遞歸作用於這個單值規則。這就說明,一個像無限的序列為何提供了比「母集無限」更多的資訊:它提供了有序的位置,使首次出現規則能夠實際運作。
若 ,首次出現的位置是 ,構造得到 。
反例模式
無限多個位置不足以給出單射
聲稱:首次出現構造能把每個序列 變成單射 。取 ,當 為偶數時 ,為奇數時 。下標 是首次出現;下標 亦是,因為 。每個 都重複了值 。因此
遞歸在第三步便停止。任何其他構造也不會成功:單射 限制到 上,就是單射 ,與抽屜原理矛盾。修正後的命題正是定理本身:像無限使 無限,從而無上界,所以每次取最小值的集合都非空。
可數選擇確切用在哪裏
定義 2.3.8
(可數選擇)
可數選擇 斷言:每個非空集序列 都有函數,從每個 中選出一個元素。這些 自身不必有限,也不必可數。
在 ZF 中,已經可以證明:若 無限,則對每個有限的 都存在單射 。從空函數開始;一個有限像的單射不能窮盡 ,否則 就有限。因此可以取一個不在該像中的元素,把有限單射延長一格。歸納給出每個 對應的獨立存在性結論。
這項歸納並沒有產生一個相容選擇的無限序列。命題 本身也不是一個已經給定的函數,不能直接為每個 指定合適的 。
定理 2.3.9
(可數選擇給出無限集的可數子集)
在 ZF 加上 後,每個無限集都包含一個可數無限子集。
證明
(選取元組,而非相容的序列)
對每個 ,令 為所有單射 組成的集合。函數集已經是集合, 是其子集;前面的有限歸納證明了 。替換公理構成由定義唯一確定的序列 。可數選擇再從每個 中選出一個 。
這些元組 不必彼此延長。令 。它是集合,而且無限:若 ,單射 就違反抽屜原理。為構造滿射到 的序列,固定 ,定義
這是 到 的滿射。使用一個固定的配對雙射 ,就得到一個像為 的序列。前一定理去掉重複後,給出單射 ;其像就是所需的可數無限子集。
證明透視
為甚麼互不相容的元組仍給出無限集
選出的元組可以處處不一致: 未必延伸 。證明只需要它們的像合起來不是有限集;一旦假設大小為 ,抽屜原理單憑一個成員 就給出矛盾。填充值 使 在整個 上有定義,而不必再作第二次選取;它存在,因為 有一個輸入。其餘步驟的次序是被迫的:去除重複需要一個序列,所以先經固定的配對把聯集枚舉出來,然後首次出現定理才給出單射。
只有選出整個族 的那一步使用了可數選擇。我們沒有假定依賴選擇、 的良序,或元組間的相容性。無限像的論證解釋了為何不需要相容性。
前面的基數筆記已在 ZF 中證明:存在單射 ,等價於 與自己的某個真子集雙射;後者稱為 Dedekind 無限性。因此本節證明,在 下,每個無限集都是 Dedekind 無限集。我們證明的是這個蘊涵,並沒有證明它與 等價,也沒有構造無選擇公理的反模型。只在 ZF 中論證時,不可未經說明就把「無限」替換成「Dedekind 無限」。
常見錯誤
常見錯誤
(有限歸納不會收集無限多個見證)
有限歸納可以處理每次固定的有限次存在性選擇,卻不會自動收集無限多個見證。另一方面,無限遞歸也不一定需要選擇:上面的最小下標構造在每一步都已指定唯一輸出。
常見錯誤
(無限集到自身的單射不必滿射)
映入無限集的單射不必滿射,即使定義域就是同一個集合。有限自身映射定理依賴有限抽屜原理。
常見錯誤
(每個成員有限,不等於已有枚舉)
知道一族集合中每個成員有限,不等於已經同時得到它們的枚舉。後面的練習會說明一種足以完成這項額外任務的選擇原則。
練習
快速檢查
(對自然數 ,準確刻畫何時存在單射 、何時存在滿射 。包括定義域或陪域為空的情況。)
解答
單射存在當且僅當 :包含映射給出充分性,抽屜原理給出必要性。滿射存在當且僅當 ,或 。後一種情況中,把 映到自己,其餘輸入映到零。必要性可由每個目標的最小原像構成的單射 得到。若 ,連函數也不存在;若 ,空函數不是滿射。
快速檢查
(證明有限集不可能與自己的真子集雙射。指出位移 在哪裏避開了你的論證。)
解答
若 且 ,由真子集結論知 。雙射 便與有限基數唯一性或抽屜原理矛盾。取 時,真子集 並沒有落在某個有限序數內,因此證明有限基數嚴格不等式的歸納不適用。
快速檢查
(令 。求首次出現集合 及無限像定理構造出的單射。說明為何不能把該定理用於常值序列。)
解答 · 答案
每個值 首次出現於 ,所以 、,且 。常值序列只有一個值,;零之後沒有下一個首次出現下標。保證這些後繼下標存在的假設已經缺失。
快速檢查
(在 ZF 中證明: 無限,當且僅當對每個 都存在單射 。說明這個命題為何還不是單射 的構造。)
解答 · 答案
若 無限,就按正文的方法一次延長一個有限單射;歸納證明每種有限長度的單射存在。反之,若 與 雙射,把單射 與該雙射的逆複合,就違反抽屜原理。獨立見證未必相容,也尚未被選成一個族。量詞 不是已經給定的關於 的函數。
快速檢查
(假設 ,證明一個有限集序列的並至多可數。不得預先假定枚舉已經同時給定,並處理空聯集的情況。)
解答
對每個 ,令 是 唯一的有限基數。唯一性與替換公理給出函數 。令 為雙射 的集合,它非空;當 時,其中有空雙射。可數選擇同時選出 。設 。若 為空,空函數就是它到 的單射。否則固定一個 :當 時把 映到 ,其餘情況映到 。這給出 到 的滿射。配對得到滿射到 的序列,再把每個值映到其最小出現下標,就得到單射 。最後一步對有限或無限的 都成立。
快速檢查
(若 不與自己的任何真子集雙射,就稱它 Dedekind 有限。利用前面的 Dedekind 等價刻畫與本節的無限像定理,證明每個函數 都只有有限的像。再證明逆命題。)
解答 · 答案
若某個 有無限的像,由定理便有單射 ,再由前面的等價刻畫, 是 Dedekind 無限集,矛盾。因此所有這類像都有限。反之,若 是 Dedekind 無限集,同一等價刻畫給出單射 ,其像由抽屜原理不可能有限。 時不存在函數 ;關於所有像都有限的條件自然為空真,正合所需。