動機
有限集合用自然數計數;無限集合則先比較映射。兩個集合可以雙射配對時,稱它們大小相同。真子集可能與母集合等勢,所以有限計數的直覺需要重新檢查。
公理也影響論證。給出一個枚舉,和知道每個集合各自存在某個枚舉後,再為整族集合同時選取枚舉,是不同的步驟。後者可能涉及選擇原則。本節在 ZF 中證明主要比較結果,並指出可數性證明中隱藏選擇的位置。
定義
定義 2.1.1
(大小比較與可數性)
存在雙射 記為 ;存在單射記為 。若前者不成立而後者成立,記為 。符號 可理解為這種大小比較,不必預設每個集合都對應某個最小等勢序數。
能單射到 的集合稱為至多可數,與 雙射的稱為可數無限。非空的至多可數集合是某序列的值域:在單射的像上取逆,未使用的指標填入一個固定元素。反過來,若 滿射,把每個元素送到首次出現的指標,就得到到 的單射。所以枚舉允許重複。
對可良序集合,最小的等勢序數稱為初始序數,也稱基數。 是第一個無限基數,記為 。沒有選擇公理時,不應預設任意集合都可良序。
命題 2.1.2
(大小比較的基本法則)
對任意集合 :
- 具自反性、對稱性和傳遞性; 具自反性和傳遞性。
- 若 ,則 。若 且 ,則 當且僅當 。
- 若 且 ,則存在滿射 。
- 若 且 ,則 。
證明
(複合、限制,並以一個固定點補足)
恆等映射給出自反性。雙射的逆仍是雙射,單射(或雙射)的複合仍是單射(或雙射)。這證明第 1 項。第 2 項中,包含映射 是單射。若 、 是雙射, 是單射,則 是單射;反方向同理。
第 3 項中,固定單射 及一個元素 。從一個非空集合中固定一個元素只是一次存在例示,不是使用選擇公理。定義 :當 時, 是滿足 的唯一 ;否則 。其圖像可從 中分離出來,而且 ,所以 是滿射。
第 4 項中,傳遞性給出 。若 ,則 ,再加上 ,由下文的 Cantor–Schröder–Bernstein 定理得 ,與 矛盾。
沒有選擇公理時,第 3 項的逆命題可以不成立;見常見錯誤中關於反轉滿射的一條。另有兩點需要留意。第一, 在相差 的意義下具反對稱性,全靠 Cantor–Schröder–Bernstein 定理,而這需要證明。第二,ZF 不能證明任意兩個集合都可比較。事實上,「對任意集合 ,都有 或 」等價於選擇公理;選擇一章會把集合與它的 Hartogs 序數比較,以證明這一點。
定理/命題
定理 2.1.3
(Cantor–Schröder–Bernstein 定理)
若存在單射 和 ,則 。不需要選擇公理。
定理 2.1.4
(Cantor 定理)
對每個集合 ,不存在滿射 ,所以 。
概念視角組合
把 Cantor 對角論證看成一張表
經由第二道練習的雙射 ,映射 就是一張表:每個 對應一行,每個 對應一列,元素為 。對角集 的指示函數,就是讀出對角元素 後把每一個翻轉所得。這個新行在第 列與第 行不同,所以它不是表中任何一行。當 時,這正是二元序列列表的熟悉圖像。
定理 2.1.5
(已給枚舉的並)
若同時給定每個非空 的滿射 ,則 至多可數。在 ZF 中,僅說每個 至多可數,尚未提供該證明所用的整列枚舉。
證明思路
證明
(以從 出發的鏈分割)
令 ,遞歸定義 ,並令 。定義
第二分支有定義,因為 ,且 單射。每個分支單射;若 ,其中 、,則 ,矛盾,所以兩分支的像不交。對任意 ,若 ,第二分支取到 ;若 ,它不在 ,故屬於某個 。由 的單射性,,其中 ,所以第一分支取到 。這證明雙射。
證明透視
鏈的起點與反向分支的定義域
集合 收集了從 出發、反覆作用 所能到達的每一點。證明依賴 的三個性質。第一,,所以 以外的每一點都屬於 ,分支 在那裏有定義。第二, 在 下封閉;這正是兩個分支不會相撞的原因,因為一旦相撞, 以外的某點就會落入 。第三, 的每一點都形如 ,其中 ,這正是滿射性所需。
整個論證只用到 、 的單射性、 上的普通遞歸和分離公理。每個 都唯一確定,所以沒有作任何選擇。在 本身已是滿射的邊界情況,、,而 。
證明
(對角集合)
假設 滿射。分離構造
若 ,便有 ,矛盾。另一方面 單射;雙射必為滿射,已被排除。此證明也適用於空集。
證明
(配對各個枚舉)
從 滿射到聯集,而
把第 條對角線依次排列,給出到 的雙射。複合後再取首次出現指標,即得可數性。若允許空 ,按自然順序枚舉非空指標;若全空,聯集為空。關鍵是已經給出整族枚舉。
例題
例題 2.1.6
(枚舉有理數)
每個有理數有唯一既約表示 ,其中 、 為正整數。 顯式枚舉整數,配對函數枚舉整數與正整數的所有配對,再送到 。重複無妨。又有 ,故由 Cantor–Schröder–Bernstein 定理或首次出現構造得 。
例題 2.1.7
(有限字串與無限序列)
二進制有限字串按長度、同長度按字典序排列,每個長度 有 個,所以每個字串出現在有限位置。用固定有限字母表書寫的程式只是有限字串,合法程式集合至多可數。無限二進制序列則對應 ,由 Cantor 定理不可枚舉。這裏各長度的順序已明確,無需逐項任意選擇。
例題 2.1.8
(實數與冪集等勢)
映射 將 單射到 :有理數稠密保證不同實數的下割不同。固定有理數枚舉後,其冪集與 等勢。反向把 送到
若兩集合首次在 不同,該項差的絕對值為 ,後續項總差至多 ,所以值不同。Cantor–Schröder–Bernstein 定理給出 。這個構造避開而非忽視小數表示不唯一的問題。
例題 2.1.9
(區間與整條直線等勢)
映射 是雙射 。它在 上由 遞增趨向 ,在 上由 遞增趨向 ,逆映射是 :事實上 ,所以 。每個滿足 的開區間 都可經仿射映射與 雙射。因此每個非空開區間都與 等勢。
閉區間還需要多走一步,因為不存在連續雙射 。沿一個指定序列移位便足夠。定義 為
記 、,以及當 時 ;這個映射把每個 送到 ,即把序列向後移兩位,映到 ,其他點全部固定。所以 是雙射。這與下文 Dedekind 無限例子中的移位是同一手法,只是用在一個明確給出的序列上。另一種做法是:包含關係 與單射 (由 到 )經 Cantor–Schröder–Bernstein 定理給出同一結論,只是沒有把雙射寫出來。
例題 2.1.10
(平面、序列與整數序列都具連續統大小)
以 表示上文證明中的配對雙射。由此得到三個雙射。
- 。把由 的子集組成的序列 送到 。逆映射把 送到第 項為 的序列。兩個方向都由公式給出,不涉及選擇。
- 。把 送到 ;偶數和奇數重新把兩個座標分開。
- 。映射 把 單射到 。反方向, 是單射,因為 是雙射,而函數由其圖像決定。Cantor–Schröder–Bernstein 定理完成論證。
現在固定一個雙射 ,它的存在由上文關於實數的例題保證。逐座標應用 ,便可轉移前兩個雙射,所以 且 。一個平面,甚至全體實數序列,點數都不比一條直線多。這裏只用了一個固定的雙射,並非對每個座標分別作選擇。這種比較只涉及大小。雙射 不可能連續,因為它在一個圓上的限制會是由圓到 的連續單射,而介值定理排除這種情況。拓撲能區分這兩個集合,基數卻不能。
例題 2.1.11
(代數數與超越數)
整係數多項式是有限整數串,按長度和係數界可顯式枚舉。每個非零多項式只有有限多個複根;先按實部、相同實部再按虛部排列,可規範地枚舉根,不必任意選擇。因此代數複數至多可數。實數不可數,故存在超越實數;這個存在證明沒有指出某個具體常數。
例題 2.1.12
(可數網格與有限記錄)
配對函數給出 ,迭代該公式可枚舉任意固定有限長度的自然數元組。長度可變的有限元組也能顯式排列:以「長度加各項之和」為權重,按權重遞增排列,同權重內按字典序。權重固定時長度和每項均有界,所以只有有限多個元組。空元組置於權重零。每個有限元組最終都會出現,這完全指定了枚舉過程。
因此,由有限多個整數標籤、自然數地址及有限控制符號組成的有限記錄,只要各部分編碼預先固定,就至多可數。這解釋了有限證明、程式及數學表達式為何可編碼為自然數;它沒有把無限記錄或任意實參數也變成可數。把有限有理係數串換成無限二進制序列,會改變可用資料的基數。
例題 2.1.13
(Dedekind 無限性揭示隱藏假設)
集合若與自身的一個真子集雙射,稱為 Dedekind 無限。在 ZF 中,這等價於包含可數無限子集。若 是不同元素,把 移到 ,其餘點固定,就給出 到 的雙射。
反過來,若單射 遺漏 ,令 。若 且 ,逐次用單射性消去 ,便有 ,把 放回 的像,矛盾。因此這些值互異,形成可數無限子集。這裏只固定一個點,其他點均由迭代唯一確定,沒有同時任意選擇。
有限鴿巢原理排除有限集合具有此性質。在 AC 下,無限集合可以良序,再每次取最小剩餘元素,便得到所需序列;若有限步就取盡,原集合本來就有限。但 ZF 中「無限」的定義只是與任何有限序數都不等勢,不能默默換成「含可數無限子集」。熟悉的 Hilbert 旅館移位需要的是已給出的無重複序列。序列一旦有了,移位完全正確;需要辨別的是該序列的存在性是否已獲保證。這個例子也說明,某個明確的組合構造可以不使用選擇,而在所有無限集合上統一斷言該構造的輸入可用,卻可能涉及更強公理。
反例模式
等勢不保持原來的次序
一個貌似合理的錯誤推論是:兩個有序集合等勢,就有相同序型。把最後一點 送到 、把每個有限 送到 的雙射 已反駁它。前者有最大元素,後者沒有;序同構必保持「最大」這個性質,所以任何雙射在這裏都不可能是序同構。
正確修復要說明映射必須保持甚麼。比較基數只要求單射和滿射,不要求次序;比較序型則要保持前驅關係。同一個底集可以賦予不同次序,同一個可數基數也容納這兩個不同序型。配對函數把無限網格排成一列也是如此:它無需保存平面位置,也無需保存原先指定的字典序,所證明的只是每個點恰出現一次。
因此讀到「相同」「可編碼」或「同構」時,必須問保留的是哪些結構。字串編碼為自然數只是集合間的有效對應,不會把字串的前綴關係變成自然數的通常大小關係。忘記保留條件,往往會把一個正確的可數性證明誤用為錯誤的序數結論。
常見錯誤
常見錯誤
(單向單射不是雙射)
只有一個方向的單射不足以證明雙射: 單射到 ,反方向的比較卻不可能。
常見錯誤
(反轉滿射可能需要選擇)
ZF 中滿射也不自動給出反向單射,因為從每個纖維選一個點可能需要選擇。以首次出現選取元素能成功,是因為 有指定良序。
常見錯誤
(對角化需要指明列表)
對角化必須指明假定的列表,再構造不在列表中的對象。「無限太大」不是矛盾。
的序數值不同於 ,但基數仍可相同。
總結
相互單射透過明確分區給出雙射。冪集經對角化嚴格增大。可數性依靠可用的枚舉;任意同時選擇則是選擇一章單獨研究的原則。
練習
快速檢查
(顯式枚舉 的全部有限子集,並說明任意子集為何更多。)
解答 · 答案
是有限子集到 的雙射,空集對應零;二進制表示唯一。全部子集構成的 則由 Cantor 定理不可數。兩類子集不能混淆。
快速檢查
(證明 ,其中後者表示所有函數 組成的集合。)
解答 · 答案
取 ,其中恰在 上取值 ;逆映射為 。兩個複合都是恆等,因此不經選擇便得到雙射。
快速檢查
(由 證明 。Cantor 定理是否推出 總給出 ?)
解答 · 答案
設 單射,則 單射,因為像相等時可用 的單射性恢復元素。嚴格性並不由 Cantor 推出;該定理比較集合與自身冪集。此證明沒有嚴格比較兩個不同無限集合的冪集大小;那需要另外的論證或附加假設。
快速檢查
(不用選擇公理證明 的每個無限子集可數無限。)
解答 · 答案
取 ,。無限性保證每步剩餘非空。序列嚴格遞增;若遺漏 ,最小剩餘規則不允許越過 ,而有限集合 又不能容納無限多個不同前項,矛盾。因此它雙射到 ;每步值都唯一。
快速檢查
(用不動點給出 Cantor–Schröder–Bernstein 定理的第二個證明。對單射 與 ,就 令 。證明 有不動點 ,並且 給出一個雙射。)
解答 · 答案
若 ,則 ,所以 ,從而 。令 ,它包含 ;再令 。對每個 都有 ,故 ;因此 。再由單調性得 ,所以 ,即 。於是 。這就是 上單調映射的 Knaster–Tarski 不動點論證。
不動點等式說明 。在 上令 ,在 上令 。第一支把 雙射到 ;由於 是單射,第二支把 雙射到 。這兩個像分劃 ,所以 是雙射。由於 是單射,,而這樣得到的最小不動點正是鏈證明中的集合 。兩個證明構造的是同一個雙射。
快速檢查
(利用 Cantor 定理及大小比較的基本法則,再證明一次不存在由所有集合組成的集合。)
解答 · 答案
假設 是包含每個集合的集合。 的每個子集都是集合,所以 ,從而 。由於 非空(它包含 ),基本法則第 3 項給出滿射 ,這是 Cantor 定理所禁止的。事實上每個集合都是 的子集,所以由包含映射構造出的滿射就是恆等映射,其對角集合正是 Russell 集合 。
快速檢查
(證明由連續函數 組成的集合 滿足 ,儘管所有函數 組成的集合嚴格大於 。)
解答 · 答案
常值函數給出 。反方向,把 送到其限制 。這是單射:給定 ,有理數 組成一個指定的、收斂到 的序列,所以由連續性得 ;兩個在 上相同的連續函數處處相同。固定 的一個枚舉,便把 等同於 ,而由序列的例題,。因此 ,Cantor–Schröder–Bernstein 定理給出 。所有函數 包含所有函數 ;後者與 等勢,由 Cantor 定理及基本法則第 4 項,它嚴格大於 。
快速檢查
(證明所有雙射 組成的集合與 等勢。)
解答 · 答案
雙射 組成 的子集;由例題, 與 等勢,所以這些雙射單射到 。反過來,對 ,令 對每個 交換 與 ,並固定其他所有數。每個 都是自身的逆,因此是雙射。若 ,則 而 ,所以 是單射。Cantor–Schröder–Bernstein 定理完成證明。特別地,可數集合有不可數多個排列。