動機
假設一個輸入集合中的每個對象,都有滿足指定條件的輸出。對於同一輸入,合適的輸出可能有很多。我們能否找到一個集合,為所有輸入提供足夠的見證?能否為每個輸入選定恰好一個輸出?又能否把一切可能的輸出收集起來?這三個問題需要分開處理。
替換公理模式直接處理一個特殊情況:若每個輸入的輸出唯一,所有輸出便組成集合。然而,替換中的唯一性條件不能直接刪去。儘管如此,ZF 仍可證明:只要輸入形成集合,就有一個集合,對每個輸入保留至少一個合適輸出。這就是收集公理模式。證明會先限制所需輸出的秩,而不用預先為每個輸入挑選一個輸出。
我們在 ZF 中工作,並使用前文已建立的序數秩和累積層級。特別地,
除非另有明確說明,以下不假設任何形式的選擇公理。
收集所保證的事情
定義 1.3.1
(收集公理模式)
固定一個含集合參數 的一階公式 。它不一定對每個 給出唯一的 ,量詞也不一定有界。對於集合 ,相應的收集實例為
所得 為見證提供一個共同範圍:每個輸入都能在 內找到至少一個合適輸出。 可以含有無關對象,也可以漏掉其他合適輸出。它亦不一定指明應將哪個輸出配給哪個輸入。
定義 1.3.2
(強收集)
強收集進一步要求 的每個成員都對某個輸入有用:
這裏的「強」是指加入了排除無用成員的條件,並不表示得到選擇函數。同一輸出可以服務多個輸入;對同一輸入, 中仍可能保留多個合適輸出。
正如分離和替換,收集是一個公理模式:每個公式各有一個實例。我們沒有在 ZF 中加入遍歷所有公式的變量,也沒有加入整個集合宇宙的真謂詞。以下每個論證中的 均為固定公式。
先限制秩,毋須選定見證
定理 1.3.3
(ZF 證明收集與強收集)
對每個固定公式 ,ZF 均證明上述收集實例及強收集實例。兩者的證明均不需要選擇公理。
證明
(最小見證秩為輸出定界)
假設 。對每個 ,考慮其合適輸出可能具有的序數秩。這個非空的可定義序數類有最小成員,記作 。準確來說,
尚未把所有見證的秩構造成集合,怎能取最小秩?在關於單一固定 的論證中,取一個已存在的見證 。在序數 內使用分離,找出所有不超過 的可達秩。這個集合非空,故有最小序數。其餘更大的可達秩不可能比該最小序數更小,所以所得最小秩不依賴 。這樣便證明了 的存在與唯一,並沒有同時為全部 選擇見證。
現在 是可定義的單值規則。替換給出集合
每個 都有至少一個秩為 的合適輸出。由於 ,這些最小秩輸出全都屬於 。因此 滿足收集。我們收集的是唯一確定的序數界,而非一族已選定的見證。
要取得強收集,再用分離定義
最小秩見證仍保留在 中,故每個輸入繼續有見證。定義條件又確保每個保留的成員都能服務某個輸入。若 ,則 、,且 ,兩項結論仍成立。
證明透視
唯一的輔助對象是秩,而非見證
前提提供每個輸入的見證,卻一般不提供唯一見證。但合適見證所能具有的最小序數秩是唯一的。替換作用於這個新得到的單值規則。冪集及超限遞歸提供一個層級階段,容納這些最小秩的全部輸出;有需要時,再以分離刪除無關成員。
整個論證沒有從「每個纖維非空」跳到「在每個纖維選一個成員」。最小秩論證暫時取一個見證 ,只是針對單一固定輸入的局部步驟。最終的 定義並不依靠一整族這樣的選擇。
這亦說明這裏的「界」是甚麼意思。定理保證足夠高的層級階段存在,沒有提供從公式有效算出該階段的算法。判斷某個秩上是否有見證,仍可能涉及任意無界的集合論量化。
恢復單值的替換
定理 1.3.4
(收集與分離一起推出替換)
在通常其餘的 ZF 公理之上,保留分離時,收集和替換是等價的公理模式。上文由替換推出收集時使用了 ZF 的秩定理;由收集推出替換則只須先收集,然後分離。
證明
(由收集推出替換)
假設公式 對每個 恰有一個輸出。收集給出集合 ,其中每個輸入至少有一個合適輸出。分離得
若 是某個輸入 的輸出,收集保證這個相同輸入亦有輸出 。唯一性迫使 ,因此 。反過來, 的每個成員按定義都是輸出。於是
正好得到替換所要求的像集。
這一步實際用到了唯一性;以下的失敗例子說明它不可省去。
反例模式
沒有唯一性時從見證界分離
聲稱:若每個 至少有一個輸出,則從收集界 中分離出輸出,就得到全部輸出的集合。取 ,令 表示 是序數。集合 是收集界,分離得 。但 也是合適輸出,而 。更甚者,這裏沒有任何集合能包含全部輸出,因為序數形成真類。修正後的陳述要求每個輸入恰有一個輸出;此時上面的論證說明 就是完整的像集。
本定理也不是說任何極弱的集合論片段都有這種等價:由替換推出收集時,已使用秩、層級階段及其餘明確指出的 ZF 資源。
集合關係尚未成為選擇函數
收集給出 後,可在 內分離出集合關係
定義 1.3.5
(處處有定義的關係與選擇函數)
每個輸入都有一個 -後繼。我們稱這個關係在 上處處有定義,意指每個輸入至少有一個對應輸出;這個說法與全序無關。它未必是函數,因為纖維
可能有多個成員。原條件的一個選擇函數,是定義域為 的集合函數 ,使每個 均滿足 。
定理 1.3.6
(任意集合指標的見證選擇等價於選擇公理)
在 ZF 之上,要求每個條件 都有選擇函數的模式,與選擇公理等價。每個實例均以一個集合 作定義域;它沒有要求一個在整個宇宙中作選擇的類函數。
證明
(在纖維中選擇,並反推選擇公理)
假設 AC。先用收集構造上述非空纖維 。每個纖維由 唯一確定,替換故可形成集合 。AC 提供定義在 上的函數 ,對每個 都滿足 。定義 。替換構造其圖,而 保證所需條件。若幾個輸入有相同纖維,也沒有障礙:可以使用相同的被選元素。當 為空時,直接取空函數。
反之,設 為任意以集合為指標的非空集合族。把這個已給定的族用作參數,令 表示 。選擇函數模式給出對每個 均有 的函數,這正是 AC。
此等價辨認出一項附加原則,並沒有在本節證明 AC 獨立於 ZF。某些具體選擇函數可以不靠 AC 而定義。例如合適輸出全是序數時,可取最小的合適序數;每個纖維為 的非空子集時,可取最小成員。判斷的重點是:眼前的具體規則,是否已唯一確定所需輸出。
例題
例題 1.3.7
(實際計算有限例子的秩界)
設 , 表示 是序數且 。最小的合適見證是 ,秩也是 。故一般構造給出 、、,以及 。
內每個輸入都有見證,但亦有許多無關對象。強收集刪去無關成員,留下 。這仍不是選擇函數:對輸入 而言,、 和 都合適。另行定義 才為每個輸入指定一個見證;序數順序在此提供了規範的最小選擇。
例題 1.3.8
(已給定的集合族可以直接用聯集作界)
設 是定義在 上的集合函數,且 均非空。其值域是集合,故 也是集合。每個 都包含在 內,因此對條件 , 已是一個見證界。這個特例不用動用一般收集定理。
例如取 、。最小秩為 ,所以秩構造只需 ,其中有用的見證為 。直接的聯集界另外保留了較大的見證 、、。不同的見證界可以保留不同數量的備選輸出。然而,形成聯集或按秩篩選,都不等於為任意非空集合族逐一選定成員的一般任務。
例題 1.3.9
(見證的秩可能需要極限界)
對 ,要求 。這些輸出唯一,故替換已可直接構造其值域。要與一般證明比較,先記起 : 各成員的秩恰為所有小於 的序數,代入秩定義的上確界便得到 。
因此最小見證秩為 ,並且
每個指定對象 都是 的成員。但是對有限 ,階段 不可能包含所有指定見證:其秩等於階段指標的對象 自身已不在其中。輸入雖然只有可數多個,成員關係深度的界卻是一個極限序數,不能當成有限階段或輸入的數目。
例題 1.3.10
(收集不會收集一切可能輸出)
取 ,讓 表示「 是序數」。 可以作界, 也可以。但所有合適輸出不能組成集合,因為序數形成真類。若集合 恰好包含所有序數,則 是序數,其後繼也在 中。於是 推出 ,與序數性質矛盾。
因此,「有集合提供足夠見證」與「沒有集合包含全部見證」並無衝突。這個例子的最小見證秩為零,秩構造便給出 。
常見誤解與小結
常見錯誤
(把替換用於多值公式)
不要把替換直接用於多值公式。先找出真正唯一的輔助對象,如本節的最小見證秩;又或先提供一個現有集合,讓分離能在其中操作。
常見錯誤
(以每個輸入各取一個見證來證明收集)
在 ZF 中,「為每個輸入取一個見證」不能代替收集的證明,因為這正好加入了秩證明所避開的選擇問題。
見證界不是函數、精確像集、可計算的搜尋界,也不是一切可能性的集合。收集提供有共同範圍而又足夠的備選輸出。若輸出唯一,這些備選已足以恢復替換所需的精確像集。要為每個任意的集合指標問題同時選定一個備選,則是等價於 AC 的附加選擇函數原則。本節沒有因此宣稱獨立性結果或整門課程已經完成。
練習
快速檢查
(檢查 時收集和強收集各有何要求。哪些集合 滿足強形式?選擇函數是甚麼?)
每個條件都只對 中的輸入量化。
解答 · 答案
斷言 空真,所以任何集合 都滿足普通收集。強收集亦要求每個 有一個來自 的輸入,這不可能發生;故只有 滿足強形式。定義域為空的唯一函數是空圖,其選擇條件也空真。
快速檢查
(取 ,令 表示 是大於 的序數,重新計算有限例子的秩界。列出 並辨認有用見證的子集;解釋該子集為何不是定義在 上的函數。)
先算出每個輸入的最小見證秩。
解答 · 答案
最小秩分別是 和 ,故 。各階段為 、、、。當中大於至少一個輸入的序數成員為 與 ,所以 。它只是可能取值的集合,沒有為每個輸入指明唯一輸出;輸入 仍有兩個合適值。例如 才是一個實際選擇函數的圖。
快速檢查
(設 、, 表示 。明確寫出 ,證明它在 上處處有定義卻不是函數,並給出兩個選擇函數。)
在 內分離出所需的有序對。
解答 · 答案
分離得 。輸入 有後繼,故 在 上處處有定義。然而有限序數 、 不同,所以 有兩個不同後繼,違反函數的唯一性。圖 及 分別給出兩個不同的選擇函數,均滿足條件。
快速檢查
(假設 , 只是收集給出的界。證明精確像集包含於 ,並指出刪去唯一性後哪一步不再成立。)
把任意一個輸出與 為同一輸入提供的輸出比較。
解答 · 答案
若 是輸出,取滿足 的某個 。收集提供 ,使 。同一輸入的輸出唯一,因此 。沒有唯一性, 與 可以不同。例如只有一個輸入、全部序數都合適時, 是有效的收集界,但合適輸出 不在其中。
快速檢查
(設 是一個序數集合。對每個 ,要求序數 。在 ZF 中構造選擇函數,再給出一個可同時服務全部輸入的序數。包括 為空的情況,並解釋兩個構造為何均不用 AC。)
後繼與聯集都是對序數唯一指定的運算。
解答 · 答案
定義 。後繼唯一確定,故替換構造其圖,而且 。另取 、。序數的聯集仍是序數,而每個 都有 。因此只用共同取值 , 便是見證界。當 , 為空、,共同見證的要求空真。後繼與聯集都是指定的構造,並無任意的同時選擇。
快速檢查
(假設 AC。若每個輸入的合適見證可具有無界多種秩,選擇函數定理如何應用?解釋為何證明依然成立,而不必先構造全部見證的集合。)
按證明的次序:先收集,後選擇。
解答 · 答案
收集先提供一個層級階段 ,其中每個輸入都有合適輸出。以分離構造非空有界纖維 ,再如定理般對這些纖維形成的集合指標族應用 AC。AC 只在已存在的非空集合內作選擇。較高秩的見證可忽略,因為目標是找一個合適輸出而非全部輸出。全部見證所形成的類不一定是集合,也沒有被用作替換或 AC 的輸入。