§3-2 聯集與有理數

countable 這個身分，經得起取子集與取聯集嗎？把可數多個 countable 集合合併成一個，結果會不會就此逸出 countable 之外——而有理數集落在界線的哪一邊？

社區大樓的管理室有個小麻煩。每一戶各自留了一本訪客登記簿，現在要合成一本全大樓的總簿。最直覺的作法是一本抄完再抄下一本——可是只要有任何一戶的簿子沒有最後一頁，抄寫的人就會永遠卡在那一戶，後面幾百戶連翻都翻不到。想把每一位訪客都寫進總簿，就得換一種輪流的抄法。

本篇要處理的正是這件事的數學版本：把許多份清單合併成一份，而且每一份清單、以及份數本身，都可能沒有盡頭。合併之後還數得完嗎？三條定理會給出答案，而答案的第一個獎品，就是有理數集。

三條基本定理

先立一條隨手可用的工作判準，再處理同一個問題的兩種操作：取子集會不會把 countable 弄丟，取聯集會不會把 countable 弄丟。三條都要回到定義 3.1 去構造函數，而最後一條的收口還會借用中間那條。

3.2 THEOREM

A set B is countable if and only if some one-to-one function carries B into ℕ.

B 是 countable 的充要條件：存在把 B one-to-one 打進 ℕ 的函數。從此驗 countable 只要交出一個函數，不必先分辨它是 finite 還是 denumerable。

正例：ℤ 交錯清點（§3-1 例 3）給出的正是這樣一個函數，所以 ℤ countable 一句話結案。反例：ℝ 交不出這種函數——本節最後一篇會證明，任何嘗試都必定漏掉某個實數。

3.2 的證明約定：「countable ⟹ 打得進 ℕ」是定義的直接翻譯（finite 的 Sₙ 本來就是 ℕ 的子集；denumerable 的 1-1 correspondence 更不必說）。難的方向「打得進 ℕ ⟹ finite 或 denumerable」，恰好就是下面 3.3 證明裡「像集由小到大重新編號」那一步——為避免同一段論證寫兩遍，本讀本把它併在 3.3 的證明裡一次走完。

3.3 THEOREM

Let C ⊆ B. If B is finite, then so is C; if B is countable, then so is C.

finite 集合的任何子集仍為 finite；countable 集合的任何子集仍為 countable。

正例：{1, 3, 5} ⊆ {1, 2, 3, 4, 5}，母集 finite，子集也 finite。正例二：偶數集 E ⊆ ℤ，母集 countable（§3-1 例 3：ℤ 是 denumerable），子集也 countable（§3-1 例 2 已直接驗過）。注意定理只保證 countable，不保證繼承 denumerable：{1, 3, 5} 也是 ℤ 的子集，它只是 finite。

PROOF OF THEOREM 3.3

設 C ⊆ B，以下分兩段證明：B 為 finite 時 C 為 finite；B 為 countable 時 C 為 countable。

證明計畫 · 由所求想起
要證：C 是 countable。
⇢ 依定義 3.1，要交出一個把 C one-to-one 打進 ℕ 的函數，並判定它是 finite 還是 denumerable。
⇢ 手上已有一個把母集 B 打進 ℕ 的函數——不必另造，只用它在 C 上的值。
⇢ 剩下的工作是判定像集的身分：把它由小到大重新編號，看元素點不點得完。

這張圖在證兩件事的接力。左半證「函數不必重造」：B 的 one-to-one 函數只看 C 的元素（藍色箭頭），仍然不會有兩個元素撞進同一個號碼。右下證「像集的身分判得出來」：把像集 f(C) 由小到大重新編號，元素若在某一步點完，C 是 finite；若永遠點不完，C 是 denumerable。圖中畫的是前一種結局。

Proof. Let C ⊆ B. Suppose first that B is finite, so that some one-to-one function f carries B into an initial segment Sₙ. Since every element of C is an element of B, the same f may be read on C alone; it is still one-to-one and its values still lie in Sₙ, which makes C finite.

先處理 finite 的那一半。因為 B 是 finite，定義 3.1（能被 one-to-one 打進某個 initial segment Sₙ 者為 finite、與整個 ℕ 有 1-1 correspondence 者為 denumerable，兩者合稱 countable）交給我們一個 one-to-one 函數 f，把 B 打進某個 Sₙ。接著是這一步真正的動作：不另造函數，只把 f 的定義域縮小到 C。one-to-one 要求「相異的輸入給出相異的輸出」，而這個要求對 B 的每一對元素都已成立；由於 C 的元素本來就是 B 的元素，它對 C 的每一對元素也成立——縮小定義域只會減少要檢查的配對，不可能製造出新的碰撞。輸出的落點也沒有改變，仍在 Sₙ 裡，所以 C 正好滿足 finite 的定義。

Now suppose B is countable. Then a one-to-one function f carries B into ℕ: this is immediate when B is denumerable, and in the finite case the initial segment Sₙ is itself part of ℕ. Reading f on C alone, as above, gives a one-to-one function from C into ℕ.

換成 countable 的那一半。這一步的重點只有一件事：把 denumerable 與 finite 兩種情形合併成同一種寫法——「B one-to-one 打進 ℕ」——之後就不必再分案。合併為什麼合法（以下兩句是例行核對）：B 若是 denumerable，它與整個 ℕ 的 1-1 correspondence 本身就是打進 ℕ 的 one-to-one 函數；B 若是 finite，函數的目標 Sₙ 本來就是 ℕ 的子集，把目標放寬成 ℕ 沒有任何損失。合併完成後，限制到 C 的理由與上一步一字不差，得到一個把 C one-to-one 打進 ℕ 的函數。

It remains to identify the image f(C) ⊆ ℕ. If f(C) is empty, then C is empty as well, so C is finite and the argument is over. Suppose therefore that f(C) is non-empty. Since ℕ is well-ordered, take the least element of f(C) as entry number 1, the least of what then remains as entry number 2, and continue in this manner. Either some stage leaves nothing further to number, in which case f(C) is finite, or the numbering never stops and reaches every element of f(C), which makes f(C) denumerable.

目標先講明白：現在手上只有「C one-to-one 打進 ℕ」，而定義 3.1 認可的身分是 finite 或 denumerable，所以還差一步——判定像集 f(C) 究竟屬於哪一種。先把一個邊界情形單獨處理掉（例行簿記，讀過即可）：f(C) 若是空集，因為 f(C) 蒐集的正是 C 的全部輸出，C 也只能是空集，而定義 3.1 明文把空集算作 finite，於是 C 是 finite、因而 countable，這一支到此就結束了。之所以要先切開它，是因為接下來的編號程序得從「最小元素」起步，空集拿不出最小元素，程序連第一步都跨不出去。以下設 f(C) 非空。工具是 §3-1 開頭採用的良序性（ℕ 的任何非空子集都有最小元素）——它讓「由小到大重新編號」永遠走得下去：f(C) 的最小元素編為第 1 號；拿掉之後剩下的仍是 ℕ 的子集，若仍非空就再取最小元素編為第 2 號，如此繼續。於是只有兩種結局。其一，某一步之後沒有元素可編，用掉的號碼恰好排滿某個 S_m，f(C) 是 finite。其二，程序永不停止，此時每個號碼都派得出去，而且 f(C) 的每個元素 y 都輪得到——比 y 小的自然數只有有限多個，最遲第 y 步就會編到它——這個編號既 one-to-one 又 onto，所以 f(C) 與整個 ℕ 之間有 1-1 correspondence，是 denumerable。

In both of these cases f(C) is countable, and C is in one-to-one correspondence with f(C); hence C is countable as well.∎

收口。上一步不論落在哪一種結局，f(C) 都是 countable。而 f 讀在 C 上是 one-to-one，它把 C 的每個元素送到 f(C) 的一個元素、不同元素送到不同位置，並且 f(C) 按定義就是 C 全部輸出所成的集合，所以 C 與 f(C) 之間是 1-1 correspondence——兩者的身分完全相同，f(C) 驗出什麼，C 就是什麼。因此 C 是 countable。

子集不必另造函數，借母集的函數就夠——C 是 countable；同樣的論證把 finite 的情形一併收下。

3.4 THEOREM

When finitely many finite sets are united, the union is finite; when countably many countable sets are united, the union is countable.

有限多個 finite 集合的聯集為 finite；可數多個 countable 集合的聯集為 countable。

正例：把有理數集按分母切成 A₀, A₁, A₂, … 可數多疊，每疊 countable，聯集 ℚ 因此 countable（例 4）。反例：「可數多份」這個前提少不得——若允許 uncountable 多份，即使每份只裝一個元素（單點集當然 finite），把 ℝ 的每個點各算一份聯集起來得到的仍是 ℝ，而 ℝ 並不 countable。

前半的證明（歸納法，就地解決）：先看兩個集合的情形。因為 A 是 finite，依定義 3.1 存在 one-to-one 函數 f 把 A 打進某個 S_m；同理存在 g 把 B 打進某個 S_n。定義 h : A ∪ B → S_{m+n}：x ∈ A 時取 h(x) = f(x)，x ∈ B 而 x ∉ A 時取 h(x) = m + g(x)。前一種輸出落在 1 到 m 之間，後一種落在 m + 1 到 m + n 之間，因此兩段絕不互撞；而各段內部的相異輸入分別由 f 與 g 的 one-to-one 保證輸出互異，所以 h 是 one-to-one，A ∪ B 因此 finite。接著對集合的份數 k 做歸納：k = 0 時一份集合也沒有，聯集是空集，依定義 3.1 是 finite；k = 1 時聯集就是那一個集合，本來就 finite；若 k 份 finite 集合的聯集必為 finite，那麼 k + 1 份的聯集可以寫成「前 k 份的聯集」與「第 k + 1 份」這兩個集合的聯集，由於前者依歸納假設是 finite、後者本來就 finite，剛才的兩集合結果就給出它仍是 finite。歸納完成。

前半到此結案。後半這句才是本節的主定理，也是真正需要新招的一句。以下先走一個具體個案：有理數集。走完之後再把同一條路線寫成一般的證明——想自己試的讀者，例 4 結束是最好的停手點。

例 4 · 主秀ℚ 是 countable

數線上任兩點之間都擠著無限多個有理數，自然數卻只是孤立的整點——直覺說有理數壓倒性地多。策略：把 ℚ 拆成可數多疊、每疊 countable，再一次清點完。

把 ℚ 的全部元素排成一列（允許重複，理由見下方注意②）。

按分母切疊。令 A₀ = {0}；對 n ≥ 1，令 Aₙ 收集所有分母為 n 的分數：Aₙ = { 1/n, −1/n, 2/n, −2/n, 3/n, … }，分子正負交錯排列。
檢查每一疊都 countable。A₀ 只有一個元素，是 finite，所以 countable；每個 Aₙ 的分子按 1, −1, 2, −2, … 交錯就是一份清單，這正是 §3-1 例 3（把 ℤ 從 0 起左右交錯清點）的作法搬到分子上，所以 Aₙ 是 denumerable。
檢查疊起來恰好是 ℚ。任取 x ∈ ℚ，分兩種情形。若 x = 0，因為 A₀ = {0}，所以 x ∈ A₀。若 x ≠ 0，把它寫成 x = p/q，其中 p、q 是整數、q > 0，而且 p ≠ 0；由於 A_q 收的正是所有分母為 q 的非零分數，於是 x ∈ A_q。兩種情形合起來，每個有理數都落在某一疊裡；反過來每一疊的元素本來就是有理數。因此 ⋃ₙ Aₙ = ℚ。
把二維的隊伍壓成一維。疊數也是無限的，所以「一疊清完再清下一疊」會永遠困在第一疊。改走對角線：每一條對角線只有有限格，因此任何一格都在有限步之內拿到編號。

這張圖在證為什麼「每個有理數都拿得到編號」：藍線沿對角線逐條掃過，而第 d 條對角線只有 d 格，所以掃到任何一格之前只需經過有限多格。位在第 i 疊第 j 位的分數，最遲在第 i + j 條對角線就會被點到。相對地，若一疊一疊清點，第一疊就沒有終點——第二疊永遠等不到。黃底是枚舉的前七項。

▶ 互動版：親手走一遍對角線，看逐列清點為何失敗

ℚ 的全部元素已排成一列（容許重複），所以 ℚ 是 countable。不過 countable 有兩種身分，還得再走一步才能說「一樣多」：先看 ℕ ⊆ ℚ，而 ℕ 不是 finite——§3-1 例 2 對偶數集用過的「位置不夠」論證原封不動適用，任何 Sₙ 只有 n 個位置，ℕ 裡卻挑得出 n + 1 個相異元素。因為若 ℚ 是 finite，定理 3.3 會逼得它的子集 ℕ 也是 finite，與剛才的結論矛盾，所以 ℚ 是 infinite。而依定義 3.1，countable 卻不 finite 就只剩 denumerable 一種可能：把上面那一列從頭掃過、遇到已出現過的數就跳過，剩下的清單永不終止（否則 ℚ 會是 finite）而且不遺漏任何有理數，它正是 ℕ 與 ℚ 之間的 1-1 correspondence。節首的問題到此有了答案：有理數和自然數一樣多。

兩點注意：① 疊可以是有限的（A₀ 只有一個元素），所以一般的證明必須容許有限疊。
② 枚舉允許重複（2⁄2 與 1⁄1 是同一個數，會被點到兩次），這不影響結論——重複的跳過即可，一般證明會用一個明確的函數處理掉。

PROOF OF THEOREM 3.4（後半）· 例 4 的一般化

設 A₁, A₂, A₃, … 為可數多個 countable 集合，以下證明 ⋃ᵢAᵢ 是 countable。（可數多份也可能只有有限多份；若是如此，就把其中一份重複補到清單後面，湊成以 ℕ 為索引的無窮清單——重複的份沒有帶進新元素，聯集完全不變。至於一份集合也沒有的情形，聯集是空集，依定義 3.1 已經 countable，不必再論。）

證明計畫 · 由所求想起
要證：⋃ᵢAᵢ 是 countable。
⇢ 依定義 3.1（能被 one-to-one 打進某個 Sₙ 者為 finite、與整個 ℕ 有 1-1 correspondence 者為 denumerable，兩者合稱 countable），最後要交出的是這兩種身分的其中一種。
⇢ 直接判定不容易，改走迂迴的路線：先造出反方向的東西——一個由 ℕ 打滿聯集的 onto 函數，也就是把聯集排成一列。
⇢ 排列的作法照例 4：每疊排成一隊（二維表），再用對角線編號把二維壓成一維。
⇢ 再把方向反轉：每個元素認領自己第一次出現的位置，得到一個把聯集 one-to-one 打進 ℕ 的函數。
⇢ 最後借定理 3.3 收口：這個函數的像集是 ℕ 的子集，因而 countable，再沿著這個對應把身分傳回聯集本身。

Proof. If every Aᵢ is empty, so is the union, and the empty set is countable. Otherwise fix an index k with A_k ≠ ∅ and set Bᵢ = Aᵢ whenever Aᵢ ≠ ∅, and Bᵢ = A_k whenever Aᵢ = ∅. Because only copies of A_k have been substituted, ⋃ᵢBᵢ = ⋃ᵢAᵢ, while every Bᵢ is now countable and non-empty. For each i choose a function fᵢ : ℕ → Bᵢ that is onto — list the elements of Bᵢ, repeating the list cyclically if it is finite.

例 4 的「按分母切疊、每疊排成一隊」在這裡一般化——那裡每疊有現成的排法（分子正負交錯），這裡的疊只知道 countable，而且可能是空的。先清掉空疊這個邊界情形。空集依定義 3.1 也是 countable，卻沒有任何函數能把 ℕ 打滿它（裡面一個元素也沒有，無處可打），所以排隊這一招對空疊行不通。若每一疊都是空的，聯集就是空集，本身已經 countable，證明到此結束。以下設至少有一疊非空，固定其中一疊記作 A_k。處理空疊的辦法是替換，不是扔掉：把空的那幾疊原地改填 A_k 的內容，得到新的一列 B₁, B₂, B₃, …——原本非空的疊照舊（Bᵢ = Aᵢ），原本空的疊改成 Bᵢ = A_k。之所以不直接把空疊刪掉，是因為刪掉之後索引會出現缺口，下一步要造的 g(i, j) 就會在那些缺席的 i 上無從定義；改填則保住了「每個 i ∈ ℕ 都對應到一疊」這件事。替換沒有帶進新元素（填進去的本來就是 A_k 的內容），也沒有丟掉元素（被換掉的疊原本是空的），所以 ⋃ᵢBᵢ = ⋃ᵢAᵢ，而且每個 Bᵢ 都是非空的 countable 集合。接著這一步的所求：讓每一疊都像例 4 那樣「排成一隊」。例 4 的疊有現成的排法（分子照 1, −1, 2, −2, ⋯ 交錯），一般的 Bᵢ 沒有，但 countable 這個身分本身就承諾了清單存在。而清單與函數是同一件事的兩種說法：寫下「第 1 個、第 2 個、第 3 個⋯」這份清單，就等於定義了函數 fᵢ : ℕ → Bᵢ——輸入位號 j，輸出清單上第 j 個元素。立刻拿例 4 的第 2 疊對照：它的清單是 1⁄2, −1⁄2, 2⁄2, ⋯，所以 f₂(1) = 1⁄2、f₂(3) = 2⁄2，如此而已。清單若是有限的（比方某疊只有 p、q 兩個元素），就循環重播成 p, q, p, q, ⋯——每個元素仍然被打到，onto 不受影響，這一手正是為了容許有限疊（上方注意①）。最後補一筆帳：對每個 i 同時各選一種排法，需要 Axiom of Countable Choice；本讀本以公理的形式接受它。（為什麼「各挑一種」竟要動用公理？單獨一疊當然挑得出——countable 的定義保證清單存在；§3-1 例 2、例 3 也不需要公理，因為那裡的排法是用公式明寫出來的。麻煩在「對無限多疊同時各做一次挑選、又沒有任何公式指明挑哪種」——這種無限多次的任意選擇，恰恰是集合論公理才擔保得了的動作。）

這張圖在證第一步的兩件手續都不動聯集。有限清單循環重播，多出來的號碼重複指向舊元素，onto 依然成立；空疊原地改填某個非空疊（圖中 B₃ 改填 A₁）而不刪除，索引才不留缺口。兩件手續都沒帶進新元素、也沒丟掉元素。

Define g : ℕ×ℕ → ⋃ᵢAᵢ by g(i, j) = fᵢ(j); this is well defined because every index i still carries a set Bᵢ and Bᵢ ⊆ ⋃ᵢAᵢ. Since each fᵢ is onto and every element of the union lies in some Bᵢ, the function g is onto.

這一步的所求：一個「一口氣管到全聯集」的機制。上一步的 fᵢ 每個只管自己那一疊，沒有誰管得到全部——把它們並排起來就行了：所有清單疊成一張大表（例 4 分數表的一般版，就是下圖），第 i 列是第 i 疊的清單。而 g 不是什麼新東西，它就是「查表」這個動作：給列號 i 與位號 j，回傳那一格的內容——g(i, j) = fᵢ(j)。立刻用例 4 的數字查一次：g(2, 3) = f₂(3) = 2⁄2，正是圖中圈起來的那一格。剩下兩件待驗的事。其一，每一格都查得到東西嗎？會怕的是空疊——但上一步的改填保證每個 i 都還配著一疊非空的 Bᵢ，所以第 i 列必有清單，查出來的元素落在 Bᵢ 裡、也就落在聯集裡：g 是貨真價實的函數。其二，有沒有元素躲得掉這張表？任取聯集裡的元素 x——它屬於某一疊 Bᵢ（⋃ᵢBᵢ 與 ⋃ᵢAᵢ 是同一個集合），而 fᵢ 是 onto，所以 x 在第 i 列的清單上佔著某個位號 j，於是 g(i, j) = x。每個元素在表上都至少有一格：g 是 onto。

這張圖在證 g 把整個聯集鋪成一張二維表：第 i 列就是 fᵢ 排出的 Bᵢ 清單，格子 (i, j) 的內容是 g(i, j) = fᵢ(j)。任取聯集裡的元素，它屬於某疊 Bᵢ、被 onto 的 fᵢ 排在某位 j，所以聯集的每個元素都在表上佔到至少一格——g 是 onto。補位列（B₃ = A₁，藍色）只是舊清單重播，表上不多出新元素。畫面與例 4 的分數表同一張，只是分數換成抽象元素。

Enumerate ℕ×ℕ along diagonals: for d ∈ ℕ, the d-th diagonal consists of the d cells with i + j = d + 1, taken in order of increasing i. The diagonals preceding it hold 1 + 2 + ⋯ + (d−1) = (d−1)d/2 cells, so the cell (i, j), which lies on the diagonal d = i + j − 1, receives the number (d−1)d/2 + i. Since every n ∈ ℕ satisfies (d−1)d/2 < n ≤ d(d+1)/2 for exactly one d, and i = n − (d−1)d/2, j = d + 1 − i then recover the cell, this rule inverts to a 1-1 correspondence ψ : ℕ ↔ ℕ×ℕ. Because ψ reaches every cell and g is onto, the composite g∘ψ : ℕ → ⋃ᵢAᵢ is onto as well.

這一步的所求：把二維的表壓成一維的隊伍——也就是一套「格子 ↔ 號碼」的雙向換算。走法就是例 4 的對角線，畫面同一張；差別是這裡得把走法寫成明確的公式。第 d 條對角線指的是所有滿足 i + j = d + 1 的格子——索引由 1 起算，所以第 1 條只有 (1, 1)、第 2 條有 (1, 2) 與 (2, 1)，第 d 條恰好 d 格；線內的次序規定為 i 由小到大。有了這兩件事，每一格的號碼就算得出來：因為排在第 d 條之前的格子共 1 + 2 + ⋯ + (d−1) = (d−1)d/2 個，格子 (i, j) 的號碼就是 (d−1)d/2 + i，其中 d = i + j − 1。拿 (2, 3) 驗算：d = 4，前面有 1 + 2 + 3 = 6 格，號碼是 6 + 2 = 8。反過來給定號碼 n 也找得回格子：由於三角數 d(d+1)/2 嚴格遞增且趨向無窮，恰有一個 d 使 (d−1)d/2 < n ≤ d(d+1)/2，於是 i = n − (d−1)d/2 落在 1 到 d 之間、j = d + 1 − i，而且這組 (i, j) 是唯一的。號碼與格子既然彼此都算得出對方、又都唯一，這套規則就是一個 ℕ 與 ℕ×ℕ 之間的 1-1 correspondence，記作 ψ。由於 ψ 走遍所有格子，而上一步已驗過 g 是 onto，合成的 g∘ψ 仍是 onto：ℕ 的第 n 號先經 ψ 找到一格，再經 g 找到一個元素，於是聯集的每個元素都被排進了這一列。

這張圖在證編號公式 (d−1)d/2 + i 真的給每一格一個號碼：第 d 條斜線收齊 i + j = d + 1 的 d 格、線內依 i 由小到大，所以一格的號碼就是「前面斜線的總格數 (d−1)d/2」再加「線內排第 i」。藍圈驗算 (2, 3)：它在 d = 4 那條線上，前面共 1 + 2 + 3 = 6 格，號碼 6 + 2 = 8。這正是例 4 那條藍色掃線的公式版，每一格都在有限步之內被點到。

Finally let h(x) = min { n ∈ ℕ : (g∘ψ)(n) = x } for x ∈ ⋃ᵢAᵢ. The set on the right is non-empty, since g∘ψ is onto. By the Well-Ordering Property its minimum therefore exists. Since one position carries one element, distinct elements have distinct first positions, so h is one-to-one and gives a 1-1 correspondence between ⋃ᵢAᵢ and its image h(⋃ᵢAᵢ) ⊆ ℕ. Now ℕ is countable, so Theorem 3.3 makes the subset h(⋃ᵢAᵢ) countable. Countability travels back along h: should h(⋃ᵢAᵢ) be finite, a one-to-one function carries it into some Sₙ, and composing that function with h carries ⋃ᵢAᵢ one-to-one into Sₙ; should it be denumerable instead, composing the 1-1 correspondence onto ℕ with h puts ⋃ᵢAᵢ in 1-1 correspondence with ℕ. Hence ⋃ᵢAᵢ is finite in the first case and denumerable in the second, and countable in either.∎

最後一步的所求：一個把聯集 one-to-one 打進 ℕ 的函數——定義 3.1 認的是這個方向，而目前手上的 g∘ψ 是「ℕ 打滿聯集」，方向恰好相反，所以要反轉；例 4 收口時「遇到已出現過的數就跳過」的動作，在這裡一般化成完成反轉的函數 h：h(x) 取 x 在這一列枚舉中第一次出現的位置。「第一次」確實存在，理由有兩層——集合 { n : (g∘ψ)(n) = x } 非空，因為上一步的 g∘ψ 是 onto，x 至少被打到一次；而良序性（ℕ 的任何非空子集都有最小元素）保證這個非空集合的最小值取得到。h 是 one-to-one：因為每一個位置只放一個元素，若 x ≠ y，兩者第一次出現的位置不可能是同一個——x 在列上出現再多次，h 只記第一次，上方注意②的重複問題就此了結。
但這裡還不能收工。定義 3.1 認可的身分是 finite 或 denumerable 這兩種，「被 one-to-one 打進 ℕ」並不在名單上——它只是通往那兩種身分的線索，直接宣稱它等於 countable 就等於把要證的事當成已知。缺的這一步正好由定理 3.3 補上：h 把聯集的相異元素送到相異的自然數，所以聯集與像集 h(⋃ᵢAᵢ) 之間是 1-1 correspondence；而 ℕ 與自己有明顯的 1-1 correspondence（每個 n 對到自己），ℕ 因此是 countable，於是定理 3.3（countable 集合的子集仍 countable）判定它的子集 h(⋃ᵢAᵢ) 是 countable。最後把這個身分沿著 h 傳回來，分兩種情形：像集若是 finite，存在 one-to-one 函數把它打進某個 Sₙ，這個函數接在 h 後面，合成之後就把整個聯集 one-to-one 打進同一個 Sₙ，聯集是 finite；像集若是 denumerable，它與整個 ℕ 有 1-1 correspondence，同樣接在 h 後面，合成的仍是既 one-to-one 又 onto 的函數，聯集與 ℕ 有 1-1 correspondence、是 denumerable。兩種情形都落在 countable 之內，證畢。

這張圖在證最後一步為什麼 one-to-one：枚舉這一列允許同一個數出現多次（2⁄2 與 1⁄1 就是同一個數），但 h 只認第一次出現的位置。因為每個位置上只放著一個元素，兩個相異的元素不可能把同一個位置當成自己的第一次——所以 h 把聯集 one-to-one 地打進 ℕ，聯集與圖中被圈起來的那些位置所成的集合完全對應。這個位置集合是 ℕ 的子集，接下來就交給定理 3.3 判它 countable，再沿著 h 傳回聯集。

可數多個 countable 集合的聯集仍然 countable：空疊改填非空疊讓索引不留缺口，對角線把二維壓成一維，取最小位置把 onto 反轉成 one-to-one，最後由定理 3.3 把 ℕ 的子集身分傳回聯集。

—— 第二階段到此結束 ——

兩條定理到手：取子集不會弄丟 countable，可數多個 countable 集合取聯集也不會。主秀也已兌現——把有理數集按分母切疊、沿對角線清點，ℚ 與 ℕ 一樣多，節首那個「有理數壓倒性地多」的直覺正式出局。下一篇 §3-3，這套對角線技巧就要反向登場：你會看到 0 與 1 之間的實數怎麼排都排不完。先闔上螢幕出門走一圈再回來。臨走前一則：無限旅館的櫃檯後來掛出新公告——「本店接受可數多輛滿載的巴士，恕不接待實數。」