6.1 基數、可數性與基數不等式

第 6 章改變了我們提問的方式。前面的章節發展數系及其運算；現在我們問一 個集合有多大，即使它沒有最後一個元素可以數。答案透過函數表達：雙射精確 配對兩個集合，單射則把一個集合無碰撞地記錄在另一個集合中。這樣，關於無 限大小的說法也能變得精確。

用來比較集合的函數

設 $f:X\to Y$ 為函數。它的像集為

$$f(X)=\{f(x)\mid x\in X\}\subseteq Y,$$

對 $B\subseteq Y$ 的原像為

$$f^{-1}(B)=\{x\in X\mid f(x)\in B\}.$$

記號 $f^{-1}(y)$ 可以表示單點集 $\{y\}$ 的原像；它不表示逆函數一定存在。 只有雙射才有逆函數。

定義

單射、滿射與雙射

函數 $f:X\to Y$ 稱為單射，如果

$$f(x_1)=f(x_2)\Longrightarrow x_1=x_2 \qquad (x_1,x_2\in X).$$

因此 $Y$ 中每個元素至多有一個原像。它稱為滿射，如果

$$\forall y\in Y\;\exists x\in X\text{ 使得 }f(x)=y,$$

等價地說 $f(X)=Y$；陪域中的每個元素都被擊中。如果同時是單射與滿射，就 稱為雙射。

陪域很重要。例如 $f:N\to N$、$f(n)=n+1$ 是單射而不是滿射，因為 $0$ 沒有 被擊中。若把陪域改成 $N\setminus\{0\}$，同一個規則就成為雙射。因此，關於 基數的命題必須同時寫清楚定義域與陪域。

例題

檢查三種性質

考慮 $u:\{0,1,2\}\to\{a,b,c,d\}$，其中

$$u(0)=a,\qquad u(1)=c,\qquad u(2)=a.$$

它不是單射，因為 $u(0)=u(2)$ 但 $0\ne2$；它也不是滿射，因為 $b$ 與 $d$ 不是輸出。這個小例子把兩個條件分開：單射關注輸出是否重複，滿射關注陪域 元素是否遺漏。

相同基數與可數性

定義

相同基數

若存在雙射 $f:X\to Y$，就稱集合 $X$ 與 $Y$ 有相同基數，並寫成

$$|X|=|Y|$$

被配對的元素不必具有相同性質。把數與有序對配對，與把兩列數字配對一樣合 法。對有限集合，這個定義與普通數數一致。

概念視角結構

把基數理解為數數與配對

對於有限集合，大小很容易令人聯想到清點：把元素逐一數出來。對於任意集合，定義則把這種清點改成配對檢驗：能否把 $X$ 的每個元素與 $Y$ 的恰好一個元素配對，而且反向也能做到？這就是為甚麼 $N$ 與偶數自然數 $2N=\{0,2,4,\ldots\}$ 透過 $n\mapsto 2n$ 具有相同基數，儘管 $2N$ 是 $N$ 的真子集。雙射記錄了相同的大小；真包含本身並不表示基數嚴格較小。

定義

有限集合

若某個 $n\in N$ 滿足 $|X|=|n|$，其中我們把 $n$ 表示為有限標籤集 $n=\{0,\ldots,n-1\}$；當 $n=0$ 時，這表示 $n=\varnothing$，就稱 $X$ 為有限集合，並寫 $|X|=n$。空集也是有限的，而且 $|\varnothing|=0$。

定義

可數與至多可數

在本課程中，如果 $X$ 是有限集合，或者

$$|X|=|N|$$

就稱 $X$ 可數。等價地，若 $X$ 有限或可數無限，就稱它至多可數。有 些教材只把無限情形稱為 countable，因此「至多可數」可以消除這種約定差異。 不是至多可數的集合稱為不可數。

對可數無限集合來說，一個列舉是序列 $x_0,x_1,x_2,\ldots$，其中每個元素恰 好出現一次。「恰好一次」同時包含列舉的滿射性與索引映射的單射性。僅僅寫 出一條無限序列還不夠；必須說明為甚麼沒有遺漏，也沒有重複。

可數集合的明確列舉

整數

定理

整數是可數的

$|Z|=|N|$。

設 $N=\{0,1,2,\ldots\}$，定義

$$e(0)=0,\qquad e(2k-1)=k,\qquad e(2k)=-k\quad(k\ge1)$$

這給出序列 $0,1,-1,2,-2,3,-3,\ldots$。

證明。 每個整數或者是 $0$，或者是正整數 $k$，或者是 $k\ge1$ 時的負 整數 $-k$。它們分別出現在索引 $0$、$2k-1$、$2k$ 處，因此 $e$ 是滿射。三 種情形的值互不相同，而在正數或負數情形中，顯示的索引又唯一確定 $k$，所 以 $e$ 是單射。因此 $e$ 是雙射。若 $N$ 從 $1$ 開始編號，只需把索引整體平 移一個單位；基數結論不變。

這個例子體現無限集合的基本驚訝之處：把所有負整數加入 $N$ 並沒有產生更大 的基數。比較的是是否存在雙射，而不是一個集合是否包含另一個集合。

有理數

定理

有理數是可數的

有理數集合 $Q$ 至多可數，事實上是可數無限的。

每個正有理數都有唯一的最簡表示 $p/q$，其中 $p,q\in\{1,2,3,\ldots\}$ 且 $\gcd(p,q)=1$。把 $p/q$ 放在第 $p$ 行、第 $q$ 列，然後沿有限對角線 $p+q=2,3,4,\ldots$ 掃描。每條對角線內按分子遞增掃描（固定任何一種順序 都可以），只保留互素的數對。開頭可以是

$$1,\ \frac12,\ 2,\ \frac13,\ 3,\ \frac14,\ \frac23,\ \frac32,\ 4,\ldots.$$

例題

為甚麼有理數的對角掃描有效

例如 $7/5$ 已經是最簡形式，位於對角線 $p+q=12$。在第 12 條對角線之前 只有有限條對角線，而第 12 條也只有有限個數對，所以 $7/5$ 會在有限位置 被掃到。另一方面，只保留互素數對意味着兩個被記錄的數對不可能表示同一個 正有理數：最簡表示的唯一性迫使 $(p,q)$ 相同。因此，這個掃描對 $Q_+$ 既是 滿的，也是單的。

這個論證同時證明了兩個方向。每個正有理數都有最簡數對，所以沒有遺漏；最 簡數對唯一，所以沒有重複。若所得列舉為 $q_1,q_2,q_3,\ldots$，則

$$0,q_1,-q_1,q_2,-q_2,q_3,-q_3,\ldots$$

列出每個有理數恰好一次。零出現一次，每個非零有理數都有唯一的符號和唯一 的正絕對值。因此 $Q$ 可數。 它不是有限集：包含映射 $n\mapsto n$ 從 $N$ 到 $Q$ 是單射，所以 $Q$ 包含無 限多個互不相同的整數。

圖示。對角掃描把二維格點變成一條序列；最簡形式條件消除了同一個有理數 的不同表示。

稠密性是另一個性質。有理數與實線的每個非空開區間相交，但對角線程序仍然 能把它們放入一條序列。稠密不等於不可數。

可數集合的乘積

網格論證也給出兩個 $N$ 的明確配對。對 $a,b\in N$，令

$$\pi(a,b)=\frac{(a+b)(a+b+1)}2+b$$

滿足固定 $a+b=s$ 的數對形成有限對角線；三角數 $s(s+1)/2$ 正好跳過此前 的對角線。因此 $\pi$ 每個數對恰好列出一次。更形式地，從 $n=\pi(a,b)$ 可以恢復唯一的對角線 $s$，使 $s(s+1)/2\le n\lt(s+1)(s+2)/2$，再得到 $b=n-s(s+1)/2$ 與 $a=s-b$。所以 $\pi:N\times N\to N$ 是雙射。

定理

可數三元組仍然可數

$|N\times N\times N|=|N|$。

證明。 定義

$$\Phi(a,b,c)=\pi(\pi(a,b),c)$$

兩次使用的 $\pi$ 都是雙射，所以它們的合成是從 $N^3$ 到 $N$ 的雙射。逆映 射先恢復 $(\pi(a,b),c)$，再恢復 $(a,b)$。這就是「可數乘可數乘可數」仍然 可數的具體含義：有限維網格可以用一串有限對角線掃描。若某個乘積因子為空， 乘積就是空集，因而有限；上面的雙射針對的是三個 $N$ 的乘積。

同一個配對也能處理有限個帶標籤的可數集合。例如用 $(n,i)\mapsto\pi(n,i)$ 把 $(n,0)$ 與 $(n,1)$ 映入 $N$。這個映射是單射，所 以兩個 $N$ 的副本可以存放在一個 $N$ 中；在合適的座標上使用配對映射的逆， 便能恢復標籤與原來的數字。這說明無限列舉可以吸收有限的額外標記，但並不 表示任意擴張都與原集合等大：仍然必須證明具體映射存在。

更一般地，基數比較可以沿映射傳遞。若 $X\to Y$ 與 $Y\to Z$ 是單射，合成便 給出 $|X|\le|Z|$；若兩個映射都是雙射，合成也是雙射。這兩個簡單規則正是本 節整數、有理數與三元組列舉背後的映射記賬。

基數不等式

定義

基數不等式

對集合 $X$、$Y$，若存在單射 $X\to Y$，就寫

$$|X|\le |Y|$$

若 $|X|\le|Y|$ 且 $|X|\ne|Y|$，就寫 $|X|\lt|Y|$。

箭頭方向不可忽略：從 $X$ 到 $Y$ 的單射說明 $Y$ 有足夠多互不相同的位置存放 $X$ 的每個元素，所以定義域是「不更大」的一方。包含映射 $N\to Z$、$n\mapsto n$ 證明 $|N|\le|Z|$，但單憑它不能證明相等。整數的列 舉給出反向比較，而前面的明確雙射直接給出相等。

例題

陪域有未使用元素的有限比較

定義 $r:\{1,2,3\}\to\{a,b,c,d\}$ 為 $r(1)=b$、$r(2)=d$、$r(3)=a$。它是單射，所以 $|\{1,2,3\}|\le|\{a,b,c,d\}|$。它不是滿射，因為 $c$ 沒有被使用，這正 是嚴格不等式可能出現的原因。

定理

基數不等式具有偏序結構

基數上的關係 $\le$ 具有自反性、傳遞性和反對稱性。因此 $\lt$ 具有非自反性 和傳遞性。

證明。 恆等映射 $id_X:X\to X$ 是單射，所以有自反性。若 $f:X\to Y$、$g:Y\to Z$ 都是單射，則 $g\circ f$ 也是單射：合成後的輸出相等 先給出 $f$ 的輸出相等，再給出輸入相等，所以有傳遞性。反對稱性正是下面的 Cantor-Bernstein 定理。最後，因為 $|X|=|X|$，不可能有 $|X|\lt|X|$；結合 $\le$ 的傳遞性即可得到嚴格不等式的傳遞性。

不存在一個以所有集合為元素的集合。假設有這樣的全集，就可以構造 Russell 類型的自指成員關係而得到矛盾。因此，這裏的 $\le$ 不是定義在某個 以「所有集合的集合」為定義域的全局關係；偏序性質只針對我們選定、正在比較 的一族集合，或由它們表示的那一族基數。這個限定只是基礎層面的記賬，不會 改變上面的映射或證明。

滿射 $X\to Y$ 直觀上表示 $Y$ 不比 $X$ 大，但要把它轉成 $Y\to X$ 的單射， 就要為每個 $y\in Y$ 選擇一個原像。下一篇筆記會討論這個選擇問題；本節直 接使用單射與雙射，不額外假設選擇函數。

Cantor-Bernstein：把兩個單射拼起來

定理

Cantor-Bernstein 定理

若 $f:X\to Y$ 與 $g:Y\to X$ 都是單射，則 $|X|=|Y|$。

這個定理即使兩個單射都不是滿射，也能構造雙射。令

$$A_0=X,\qquad B_0=g(Y),$$

並遞歸定義

$$A_{n+1}=g(f(A_n)),\qquad B_{n+1}=g(f(B_n)).$$

由於 $g(Y)\subseteq X$，這些集合滿足

$$A_0\supseteq B_0\supseteq A_1\supseteq B_1\supseteq A_2\supseteq B_2\supseteq\cdots$$

這些包含關係可以歸納得到：先有 $A_1\subseteq B_0$，再有 $B_{n+1}\subseteq A_{n+1}$；而前一步的 $A_n\subseteq B_{n-1}$ 又給出 $A_{n+1}\subseteq B_n$。若 $X$ 或 $Y$ 為空，兩個單射的存在會迫使兩個集合 都為空，唯一的空映射就是所需雙射；下面的構造也涵蓋這個情形。

層 $A_n\setminus B_n$ 是使用 $f$ 的部分；其餘點位於 $g(Y)$ 中，在那裏使用 $g$ 在像集上的逆。

證明。 首先 $g\circ f:X\to X$ 是單射。對每個 $n$，它把 $A_n\setminus B_n$ 雙射到 $A_{n+1}\setminus B_{n+1}$。單射性給出不重複性。 若 $z\in A_{n+1}\setminus B_{n+1}$，可寫成 $z=g(f(x))$ 且 $x\in A_n$；若 $x\in B_n$，則 $z\in g(f(B_n))=B_{n+1}$，矛盾。因此 $x\in A_n\setminus B_n$，從而得到滿射性。

定義 $h:X\to Y$：

$$h(x)= \begin{cases} f(x),&x\in A_n\setminus B_n\text{ 對某個 }n,\\ g^{-1}(x),&x\notin A_n\setminus B_n\text{ 對所有 }n \end{cases}$$

這裏 $g^{-1}$ 指雙射 $g:Y\to g(Y)$ 的逆，而不是整個 $X$ 上的逆。第二種情 形確實有定義：不在任何層中的點不可能在零層 $A_0\setminus B_0=X\setminus g(Y)$ 中，所以它屬於 $g(Y)$。層彼此不交，因 此 $h$ 定義良好。

證明單射性。若 $h(x_1)=h(x_2)$，且兩點都在層中，則由 $f$ 單射得 $x_1=x_2$；若兩點都在第二種情形，則由 $g^{-1}$ 單射得相等。若情形混合， 不妨設 $x_1\in A_n\setminus B_n$，且 $h(x_2)=g^{-1}(x_2)$。等式給出 $x_2=g(f(x_1))$，由層之間的雙射性可知 $x_2\in A_{n+1}\setminus B_{n+1}$，這與第二種情形矛盾。

證明滿射性。任取 $y\in Y$，令 $x=g(y)\in X$。若 $x$ 不在任何層中，則 $h(x)=g^{-1}(x)=y$。否則 $x\in A_n\setminus B_n$。它不可能在零層，因為 零層是 $X\setminus g(Y)$ 而 $x\in g(Y)$，所以 $n\ge1$。層之間的雙射性給出 $x'\in A_{n-1}\setminus B_{n-1}$，滿足 $g(f(x'))=x=g(y)$。由 $g$ 單射得 $f(x')=y$，所以 $h(x')=y$。故 $h$ 是滿射，也是雙射，$|X|=|Y|$。整個構造 只使用給定的 $f$ 與 $g$，沒有使用選擇函數。

為甚麼粗分層會遺漏元素

單憑集合 $A_n$ 不能記錄在哪裏可以使用 $g$ 的逆。 令 $A=\bigcap_{n\ge0}A_n$。第一個簡化構造在每個差集 $A_n\setminus A_{n+1}$ 以及 $A$ 上都使用 $f$。這些部分窮盡 $X$， 所以這個構造其實就是

$$h_1(x)=f(x)\qquad(x\in X).$$

第二個構造為

$$h_2(x)=\begin{cases} f(x),&x\in A_n\setminus A_{n+1}\text{ 對某個 }n,\\ g^{-1}(x),&x\in A. \end{cases}$$

由於 $A\subseteq A_1\subseteq g(Y)$，逆映射這一分支有定義， 但定義良好還不足以保證雙射。取 $X=Y=N$、$f(n)=n+1$、$g(n)=n$。 此時 $A_n=\{n,n+1,\ldots\}$ 且 $A=\varnothing$，兩個構造都給出 $h_1(n)=h_2(n)=n+1$，從而遺漏 $0$。已證明的構造使用 $B_n$ 分層， 保留了這兩個簡化方案丟失的資訊：逆映射分支在哪裏可用，以及兩個分支 怎樣避免輸出碰撞。

常見錯誤與細節

常見錯誤

一個單射只給出一個方向的不等式

單射 $X\to Y$ 只證明 $|X|\le|Y|$，不證明相等。相等需要雙射，或兩個方向的 單射再應用 Cantor-Bernstein 定理。

常見錯誤

滿射不等於單射

滿射容許多個輸入映到同一個輸出；單射則容許陪域中有元素未被擊中。請檢查正 確的量詞條件。

常見錯誤

最簡形式是 Q 證明的一部分

若沒有互素條件，$1/1$、$2/2$、$3/3$ 會重複表示同一個有理數。網格雖然可數， 但所寫列舉也必須是單射。

思考檢查

哪一個方向的映射證明 $|X|\le|Y|$？它必須保持甚麼？

寫出定義域、陪域以及碰撞條件。

解答 · 答案

單射 $f:X\to Y$ 證明 $|X|\le|Y|$。它保持不同性的意義是 $f(x_1)=f(x_2)$ 必須推出 $x_1=x_2$；它不必擊中 $Y$ 的每個元素。

思考檢查

為甚麼對角線列舉會列出每個正有理數？

使用最簡形式與有限的 $p+q$。

解答 · 答案

每個正有理數都有唯一的最簡數對 $(p,q)$。該數對位於有限對角線 $p+q$ 上， 而掃描會到達每一條有限對角線。

思考檢查

Cantor-Bernstein 的定義為甚麼同時需要 $B_n$ 與 $A_n$？

解答 · 答案

$B_0=g(Y)$ 保證不在任何層中的點屬於 $g(Y)$，所以 $g^{-1}$ 有定義。 此外，$g\circ f$ 把 $A_n\setminus B_n$ 映滿 $A_{n+1}\setminus B_{n+1}$。因此，若兩個分支的輸出相同，逆映射分支的 點就必須落在某一層中，與它的分支條件矛盾。

練習

思考檢查

給出從 $N$ 到 $Z$ 的明確雙射，並證明它既是單射又是滿射。

解答 · 引導解答

使用 $e(0)=0$、$e(2k-1)=k$、$e(2k)=-k$（$k\ge1$）。零、每個正整數 $k$ 和每個負整數 $-k$ 分別在指標 $0$、$2k-1$、$2k$ 處出現，所以是滿射。 這三類值互不相交，而且每個公式都唯一確定 $k$，所以也是單射。

思考檢查

用配對映射 $\pi(a,b)=\frac{(a+b)(a+b+1)}2+b$ 直接證明 $|N\times N\times N|=|N|$。

解答 · 引導解答

先證明 $\pi$ 可逆：恢復唯一的對角線 $s=a+b$，再恢復 $a,b$。複合映射 $\Phi(a,b,c)=\pi(\pi(a,b),c)$ 是兩個雙射的合成，所以是從三元組乘積到 $N$ 的雙射。

思考檢查

Cantor-Bernstein 證明中，為甚麼第二種情形的 $g^{-1}(x)$ 有定義？

解答 · 引導解答

零層是 $X\setminus g(Y)$。不在任何層中的點不在這個集合中，所以它屬於 $g(Y)$，而 $g:Y\to g(Y)$ 的逆在那裏有定義。

相關筆記

可先閱讀2.2 函數與關係， 了解像集、原像、單射、滿射與逆函數；然後繼續閱讀 6.2 Cantor 定理、連續統與選擇公理。