§3-1  配對取代計數

一個集合的元素能不能一個一個數完？兩個都數不完的集合之間，又該用什麼標準判定它們的元素一樣多——偶數集是自然數集的真子集，整數集卻反過來包含自然數集，這三者要怎麼比較？

為什麼要重新學數數

幼兒園老師點名，其實有兩種辦法。第一種是唸名冊：唸一個名字，答一聲有，唸到最後一個就知道今天來了幾個人。第二種更快——每個小朋友坐一張椅子，椅子剛好排滿、沒有空位也沒有人站著，那就到齊了，一個都不必數。

第二種辦法有個好處：它從頭到尾沒有用到任何數字。它問的不是「幾個」，而是「配不配得起來」——人與椅子一對一配好，不多不少，兩邊就一樣多。日常生活裡這只是偷懶的技巧，因為人數本來就數得完，兩種辦法給的答案一定相同。

可是把場景換成一群數：全體自然數 1, 2, 3, … 與全體偶數 2, 4, 6, …，哪一邊比較多？唸名冊的辦法立刻失效，因為兩邊都唸不完。剩下的只有配對這一招——而配對這一招接下來會給出一個相當違背直覺的答案。要把話說得精確，我們得先挑一把量尺：拿什麼東西來當作「數到幾」的標準。最現成的標準就是自然數自己的前一段。

量尺：ℕ 的前一段

以下假設讀者熟悉自然數集 ℕ = {1, 2, 3, …} 與它的大小順序，並自由使用數學歸納法。我們另外採用 ℕ 的一條性質：ℕ 的任何非空子集都有最小元素（Well-Ordering Property，良序性）——它與數學歸納法互相等價，下一篇的兩段證明都靠它。

量尺定義如下：對每個 n ∈ ℕ，記 Sₙ = { x ∈ ℕ : x ≤ n }，稱為 ℕ 的一個 initial segment（前段）。S₂ = {1, 2}、S₄ = {1, 2, 3, 4}，依此類推。要注意 initial segment 是「從 1 起連號到底」的集合：{1, 3, 5} 就不是任何 Sₙ，因為它收了 3 卻沒收 2、收了 5 卻沒收 4。

S₄：從 1 起連號到 4 1234 5678 ⋯ 24 678⋯ 135 {1, 3, 5} 跳過 2 與 4，不是任何 Sₙ

這張圖在說明量尺的形狀要求：Sₙ（藍框）必須從 1 起連號、中間不留空位；{1, 3, 5}（紅點）跳過了 2 與 4，所以它不是任何一個 Sₙ。接下來的定義並不要求集合「就是」某個 Sₙ，只要求配得進去——例 1 會示範這個差別。

3.1  DEFINITION
Call a set B finite when B is empty, or when some one-to-one function carries B into an initial segment of ℕ. Failing that, B is infinite.
When a one-to-one function carries B onto the whole of ℕ — a 1-1 correspondence — the set B is denumerable.
Finally, countable covers both cases: B is countable when it is finite or denumerable.
集合 B 為 finite，意思是 B 是空集，或存在某個 one-to-one 函數把 B 打進 ℕ 的某個 initial segment；找不到這種函數時，B 為 infinite。若存在把 B 打到「整個 ℕ」上的 one-to-one 函數（也就是 1-1 correspondence），B 為 denumerable。finite 與 denumerable 兩種情形合稱 countable。
正例：{1, 3, 5} 是 finite——配得進 S₃（例 1）。反例：偶數集 E = {2, 4, 6, …} 不是 finite，它是 infinite，而且與整個 ℕ 有 1-1 correspondence，所以是 denumerable（例 2）。
術語條件中譯
finiteB = ∅，或存在 one-to-one 函數 B → Sₙ（某個 n）有限
infinite非 finite（這種函數一個也找不到）無限
denumerable存在 1-1 correspondence B ↔ ℕ可枚舉
countablefinite 或 denumerable可數

定義裡有兩個關鍵字要分開記。one-to-one（單射）說的是不同的輸入給出不同的輸出，也就是「不擠在一起」；onto（滿射）說的是目標集合的每個元素都被打到，也就是「不留空位」。兩者同時成立就是 1-1 correspondence（雙射），正是點名時「人與椅子剛好配滿」的那個狀態。finite 只要求 one-to-one，denumerable 則兩個都要求。

術語警示：本讀本的 countable 包含有限集。部分文獻用 countable 專指「可數無限」（本讀本稱 denumerable）。閱讀其他資料時，先查清楚對方站在哪一邊，否則同一句話會讀出兩種意思。
例 1{1, 3, 5} 是 finite
這一例的重點在於分辨兩件事：「是不是某個 Sₙ」與「配不配得進某個 Sₙ」。前者剛才已經否定了，後者才是定義 3.1 真正的要求。
找出某個 n，以及一個 one-to-one 的函數 f : {1, 3, 5} → Sₙ。
  1. 取 n = 3，也就是 S₃ = {1, 2, 3}。
  2. 定義 f(1) = 1、f(3) = 2、f(5) = 3。
  3. 檢查 one-to-one：定義域只有三個元素，直接把輸出全部列出來——1、2、3 互不相同，所以不同的輸入確實給出不同的輸出。✓
{1, 3, 5} S₃ = {1, 2, 3} 135 123 三個箭頭指向三個不同的位置

這張圖在證 {1, 3, 5} 為什麼 finite：定義 3.1 要的不是「等於某個 Sₙ」，而是一個不把兩個元素擠到同一格的函數。三個箭頭各自落在 S₃ 的不同格子上，one-to-one 成立——至於 S₃ 是否還有剩餘的格子，定義並不過問。

{1, 3, 5} 是 finite。同樣的作法適用於任何能被 one-to-one 打進某個 Sₙ 的集合，例如 {2, 4, 6, 8, 10} 配進 S₅。
例 2偶數集 E = {2, 4, 6, …} 是 infinite，而且 denumerable
偶數只佔自然數的一部分，直覺上應該比 ℕ 少。以下分兩步走：先確認 E 數不完，再確認它與整個 ℕ 之間仍然配得起來。第二步的結論會直接和直覺對撞。
第一部分 · E 是 INFINITE
證明不存在 E 到任何 Sₙ 的 one-to-one 函數。要證「不存在」，用反證法：先假設它存在，再推出矛盾。
  1. 假設存在某個 n 與 one-to-one 函數 f : E → Sₙ。
  2. 因為 f 是 one-to-one，E 的每個元素在 Sₙ 裡各佔一個不同的位置；而 Sₙ 總共只有 n 個位置，所以 E 最多只能有 n 個元素。
  3. 另一方面，2, 4, 6, …, 2(n+1) 是 E 裡 n + 1 個互不相同的元素，所以 E 至少有 n + 1 個元素。
  4. 「最多 n 個」與「至少 n + 1 個」不能同時成立，所以假設不成立：這樣的函數不存在。依定義 3.1，E 是 infinite。
246810 E 裡任取 5 個相異元素 1234 S₄ 只有 4 個位置，第 5 個元素必定與人共用一格

這張圖在證第一部分的矛盾機制：反證法假設 E 配得進某個 Sₙ（圖中取 n = 4），可是 E 裡永遠挑得出 n + 1 個相異元素——第 5 個箭頭（紅色）只能落進已被佔用的格子，one-to-one 因此破功。n 換成任何自然數，同一件事都會發生。

第二部分 · E 是 DENUMERABLE
找出 ℕ 與 E 之間的 1-1 correspondence，也就是一個既 one-to-one 又 onto 的函數。作法：明確寫出函數，再把兩個性質分開檢查。
  1. 取 f : ℕ → E，f(n) = 2n。
  2. 檢查 one-to-one：設 f(m) = f(n)，也就是 2m = 2n，兩邊除以 2 得 m = n。不同的輸入不可能給出相同的輸出。✓
  3. 檢查 onto（任取目標元素，把對應的輸入找出來）：任取 E 裡的元素 e。e 是偶數，而偶數就是 2 的倍數，所以寫得成 e = 2k，其中 k 是某個自然數。拿這個 k 當輸入，就有 f(k) = 2k = e。因為 e 是任取的，E 的每個元素都被打到。✓
  4. f 既 one-to-one 又 onto，所以它是 ℕ 與 E 之間的 1-1 correspondence。方向不必介意：對應一旦雙向都不重不漏，反著讀就是 E 到 ℕ 的 1-1 correspondence（這裡反讀恰是 e ↦ e/2，也是貨真價實的函數）——定義 3.1 認的正是「對應存在」這件事。依定義 3.1，E 是 denumerable。
  5. 奇數集 O = {1, 3, 5, …} 完全平行：取 g(n) = 2n − 1。one-to-one：2m − 1 = 2n − 1 整理得 m = n。✓ onto：任取奇數 o，依奇數的定義寫成 o = 2k − 1，而 g(k) = 2k − 1 = o。✓ 所以 O 也是 denumerable。
ℕ E 12345⋯ 246810⋯ n ↦ 2n 上排沒有人落單，下排沒有位置空著

這張圖在證 E 是 denumerable：n ↦ 2n 把 ℕ 的每個號碼派給 E 的一個元素，不同號碼派到不同元素（one-to-one），而 E 裡每個偶數 2k 都被號碼 k 領走（onto）。E 只用掉 ℕ 的一部分元素，卻仍與整個 ℕ 配得剛剛好。

E 與 O 都是 infinite 而且 denumerable。E 是 ℕ 的真子集（E ⊆ ℕ 且 1 ∉ E），卻與整個 ℕ 之間存在 1-1 correspondence——真子集與全體「一樣多」，是無限集才有的現象。有限集絕不會這樣：拿掉一個元素，配對立刻對不上。
例 3整數集 ℤ 是 denumerable
ℤ 把 ℕ 整個包含在內，還多出 0 與全部負整數，直覺上應該比 ℕ 多。技術難點在於 ℤ 往兩個方向都無限延伸、沒有最小元素，所以「由小到大逐一清點」這條路一開始就走不通。
找出 ℕ 與 ℤ 的 1-1 correspondence，也就是把全部整數排成一列，每個整數恰好出現一次——排在第 n 個位置的整數，就是函數在 n 的輸出。
  1. 既然沒有最小的整數，就別從最小的開始。改從 0 出發，左右交錯清點：0, 1, −1, 2, −2, 3, −3, …
  2. 把它寫成明確的函數 g : ℕ → ℤ：g(1) = 0；對 k ≥ 1，g(2k) = k、g(2k+1) = −k。
  3. 檢查 onto（逐情況把輸入交出來）：任取整數 m。若 m = 0，它排在第 1 位。若 m > 0，它排在第 2m 位，因為 g(2m) = m。若 m < 0，則 −m > 0，它排在第 2(−m) + 1 位，因為 g(2(−m)+1) = −(−m) = m。三種情形涵蓋全部整數。✓
  4. 檢查 one-to-one（分組討論）：g 的輸出分成三組——第 1 位輸出 0，偶數位輸出正整數，其餘奇數位輸出負整數。兩個位置若落在不同組，輸出的正負號不同，必不相等；同為偶數位第 2j 與第 2k 且 j ≠ k，輸出是 j 與 k，不相等；同為奇數位則輸出 −j 與 −k，同樣不相等。✓
−3−2−1 0123 123 4567 藍字是清點順序，從 0 起左右交錯

這張圖在證清點順序為什麼不漏任何整數：從 0 出發、左右交替跳，每一跳的步幅只增加 1，所以距離 0 為 k 的整數最遲在第 2k + 1 步就被點到——不會有整數一直輪不到。相對地，若堅持「由小到大」，連起點都找不到。

ℤ 是 denumerable。交錯清點把「雙向無限」壓成「單向無限」；下一篇的主秀會把同一個念頭推廣到二維的情形。
—— 第一階段到此結束 ——

你已經把「數不數得完」換成了配對的問題：finite 是配得進某個 Sₙ，denumerable 是與整個 ℕ 配得剛好，countable 收下這兩種情形。三個試金石也走完了——{1, 3, 5} 有限，偶數集與 ℤ 雖然無限卻仍與 ℕ 一樣多。下一篇 §3-2 把配對的技巧升級成三條定理，並拿有理數集開刀。先起身走幾步、喝口水再回來，配對這件事想久了容易頭暈。回來前配一則：據說有家旅館房間編號 1, 2, 3, ⋯ 永遠住滿，卻從不拒客——來一位新客人，就請每位房客往後挪一間，1 號房就空出來了。