可數性深入：列舉、樹與錯誤的枚舉

學習目標與準備

列出集合的元素需要說明順序，證明每個元素在有限位置出現，並處理重複和空集。本章比較遞增列舉、對角列舉與有限字符串樹，檢查有關無限對象的錯誤推理。預備知識包括函數、自然數良序、有限積、等比級數和對角線定理。

取 $\mathbb N=\{0,1,2,\ldots\}$。“可數”包含有限和可數無限。空集可數，但非空的 $\mathbb N$ 不可能滿射到空集，因此用滿射改寫定義時須處理空集。

1. 三種等價判別及空集

對非空集合 $A$，以下等價：$A$ 可數；存在單射 $A\to\mathbb N$；存在滿射 $\mathbb N\to A$。

證明。 非空有限集可分配有限個不同自然數指標，可數無限集按定義有雙射，故得到單射。若給定滿射 $f:\mathbb N\to A$，將每個 $a$ 送到滿足 $f(n)=a$ 的最小指標 $n$。良序保證該指標存在；不同元素不能有同一指標，故得到單射。

反之設 $j:A\to\mathbb N$ 單射，像為 $S\subseteq\mathbb N$。若 $S$ 有限，$A$ 有限；若 $S$ 無限，反複選擇尚未使用的最小元素，得到永不停止的遞增列表。每個 $s\in S$ 之前只有有限個更小的自然數，所以它不可能被無限期跳過。對列表應用 $j$ 在 $S$ 上的逆映射，得到 $A$ 的枚舉。非空有限集在列完有限項後反複輸出某個固定項，便得從 $\mathbb N$ 出發的滿射。這樣各情況都已覆蓋，原列表不必無重複。

最小指標法可從任意列表去重，但不一定高效；可數性也不聲稱成员判定或列表可計算。數學枚舉存在與有效計算程序存在是不同陳述。

2. 枚舉不必按數值遞增

每個無限自然數子集都有上述遞增枚舉。對 $\mathbb Z$ 則不然：嚴格遞增序列有第一項，之後無法到達任何更小整數，故不能覆蓋全體整數。熟悉的 $0,1,-1,2,-2,\ldots$ 為了覆蓋全部整數放弃了遞增順序。

$\mathbb Q\cap[0,1]$ 也無法嚴格遞增地枚舉。若列表覆蓋全部元素，它須從零開始，否則零已被遺漏。設下一項為 $q_1>0$，則有理數 $q_1/2$ 嚴格介於前兩項，無法在遞增列表中稍後出現。這不是說有理數不可數，而是該排序要求不可實現。

定理

有理數是可數的

有理數集合 $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$。在這條對角線之前 只有有限條對角線，而它本身也只有有限個數對，所以 $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$ 包含無 限多個互不相同的整數。

另一種具體列舉。 按有限高度 $|a|+b$ 列舉整數分子、正分母對，並在同高度內按分子遞增排列。輸出 $a/b$；如有需要，可在首次出現後去掉重複值。每個有理數至少有一個有限高度的表示，之前僅有有限個數對，故一定到達。有理數稠密不妨礙非單調的枚舉。

3. 有限描述的族

用同時控制長度和元素大小的高度列舉所有有限整數串：先列空串；對每個正高度 $H$，列出長度至多 $H$、各項絕對值至多 $H$ 的串，只保留首次出現者。每一步的候選串有限；任意有限串的長度和最大絕對值均有限，故在某個高度前必出現。

因此可由系數字符串详細列舉整數系數多項式，而不是只說“列出所有公式”。末尾零會造成重複描述，可去重。用有限根數界時必須排除零多項式。

多項式作為有限形式和

定義

R 上的多項式

一個實係數多項式是一個形式和

$$p(x)=\sum_{i=0}^{\infty}a_ix^i$$

其中每個 $a_i\in R$，而且只有有限多個 $a_i$ 非零。所有實係數多項式的集合 記作 $R[x]$。

「形式」這個字很重要。多項式不是某個單一 $x$ 值下的函數值，而是一整列係數 資料；只要係數固定，整個多項式就固定。

概念視角結構

先看係數，再作代入

兩個形式多項式相等，正是指每個對應係數相同，包括省略的零係數。因此 $1+x$ 與 $1+x+0x^2$ 相等。代入實數 $t$ 後，才得到數值 $p(t)=\sum_i a_it^i$。雖然記號寫成無窮求和，卻沒有收斂問題： 只有有限多個非零加項。

單個函數值所含的資訊少於係數列表。例如 $x$ 與 $x^2$ 在 $t=0$ 都給出 $0$，係數卻不同。在 $\mathbb R$ 上，若每個實數輸入的值都相同，確實可以 推出多項式相等；本節稍後的根數上界會證明這個逆向結論。在此之前， 係數相等是定義，代入則是對已經定義的對象進行的操作。

若至少有一個係數非零，$p(x)$ 的次數是使 $a_i\ne0$ 的最大指標 $i$。若所有 係數都是零，我們稱它為零多項式，並約定

$$\deg(0)=-\infty.$$

這個約定可以令許多次數公式不用一直把零多項式分開處理。

非零常數的次數是 $0$，因為常數項是最高非零項。零多項式沒有這樣的項， 並不是零次多項式。比較次數時，$-\infty$ 小於每個非負整數；約定 $\max(-\infty,m)=m$、$(-\infty)+m=-\infty$，也包括 $m=-\infty$。 這些是處理次數的規則，並不是說多項式含有負整數指數。 零多項式沒有首項係數，也不是首一多項式。

若首項係數是 $1$，多項式稱為首一多項式（monic polynomial）。例如 $x^3-4x+7$ 是首一多項式，而 $2x^3-4x+7$ 不是。

常見錯誤

不要只看最後寫出的項就判斷次數

若寫成

$$p(x)=a_0+a_1x+\cdots+a_nx^n,$$

只有在 $a_n\ne0$ 時才可斷言 $\deg(p)=n$。符號本身不保證最後一個係數非零。

加法、乘法與次數

設

$$p(x)=\sum_{i=0}^{\infty}a_ix^i,\qquad q(x)=\sum_{i=0}^{\infty}b_ix^i.$$

加法是逐項相加：

$$p(x)+q(x)=\sum_{i=0}^{\infty}(a_i+b_i)x^i.$$

乘法則使用卷積公式：

$$p(x)q(x)=\sum_{i=0}^{\infty}d_ix^i,\qquad d_i=\sum_{k=0}^{i}a_kb_{i-k}.$$

因為非零係數只有有限多個，乘積仍然是多項式。

定理

次數規則

對 $p(x),q(x)\in R[x]$，

1. $\deg(p+q)\le \max\{\deg p,\deg q\}$；
2. $\deg(pq)=\deg p+\deg q$。

第二條使用了係數域沒有零因子的性質。

第一條可能是嚴格不等式，因為最高次項可以抵消。例如

$$(x^2+1)+(-x^2+x)=x+1.$$

乘法規則較強：若 $p$、$q$ 非零且首項係數分別為 $a_r$、$b_s$，則 $pq$ 中 $x^{r+s}$ 的係數是 $a_rb_s$，它不會是零。

進一步說明為何沒有更高次項。設 $\deg p=r$、$\deg q=s$。 若 $i>r+s$，每個貢獻 $a_kb_{i-k}$ 都滿足 $k>r$ 或 $i-k>s$， 所以至少一個係數為零。在指標 $r+s$ 處，只有 $k=r$、$i-k=s$ 可能貢獻； 係數來自域，故其乘積非零。因此兩個非零多項式的乘積不可能是零多項式。

對加法，超過 $\max(r,s)$ 的係數都是零。若兩者次數不同，較高的首項沒有 可抵消的對應項，所以達到上界。次數相同時，抵消卻可能一直進行到底： $p+(-p)=0$ 的次數為 $-\infty$。乘法中若一個因式為零，乘積也為零， 上述約定仍使次數公式成立。

定理

多項式除法算法

設 $f(x),g(x)\in R[x]$ 且 $g(x)\ne0$。則存在唯一 $q(x),r(x)\in R[x]$ 使得

$$f(x)=g(x)q(x)+r(x),\qquad \deg r\lt\deg g.$$

先證存在性。考慮非空集合

$$S=\{f-gs:s\in\mathbb R[x]\}.$$

取 $s=0$ 可知 $f\in S$。若 $0\in S$，選 $q$ 使 $f-gq=0$， 並取 $r=0$；由 $\deg0=-\infty$，餘式滿足條件。否則 $S$ 的每個成員 都有非負整數次數，因此良序原理保證存在次數最小的 $r_0=f-gq_0$。

假設 $\deg r_0=k\ge j=\deg g$，兩者首項係數分別為 $c_k,b_j$。 因為 $b_j\ne0$，在係數域中可以取 $c_k/b_j$。構造

$$r_1=r_0-g\left(\frac{c_k}{b_j}x^{k-j}\right) =f-g\left(q_0+\frac{c_k}{b_j}x^{k-j}\right).$$

指數 $k-j$ 非負，所以新增的式子仍是多項式，$r_1$ 仍在 $S$ 內。 兩個首項 $c_kx^k$ 抵消，剩餘項的次數都小於 $k$。若 $r_1=0$， 便與 $0\notin S$ 矛盾；若非零，則與最小次數矛盾。 因此 $\deg r_0\lt\deg g$，所求商式、餘式就是 $q_0,r_0$。

唯一性同樣重要。若

$$f=gq_1+r_1=gq_2+r_2$$

且兩個餘式的次數都小於 $\deg g$，則

$$g(q_1-q_2)=r_2-r_1.$$

左邊若非零，次數至少是 $\deg g$；右邊次數嚴格小於 $\deg g$。因此兩邊都必為 零，故 $q_1=q_2$ 且 $r_1=r_2$。

證明透視

唯一性的矛盾發生在哪裏

假設商式不同，其差就是非零多項式，次數至少為 $0$。乘以非零的 $g$， 左邊次數便至少為 $\deg g$。右邊相減時可以消項，但次數不可能高於兩個 餘式中較高者。因此兩邊不可能相等，商式必須相同；代回就迫使餘式也相同。 這個論證同時用到次數界限與除式非零的假設。

由代入取得餘式

當除式是一次式時，除法算法會變成非常實用的定理。

定理

餘式定理

設 $f(x)\in R[x]$ 且 $a\in R$。當 $f(x)$ 除以 $x-a$ 時，餘式等於 $f(a)$。

因為餘式次數小於 $1$，它只能是常數 $R$。寫成

$$f(x)=(x-a)q(x)+R$$

並代入 $x=a$，便得 $f(a)=R$。

此處 $R=f(a)$ 在除法恆等式中視為常數多項式，也可以是零。不能先把 恆等式除以 $x-a$ 再代入 $x=a$，因為這樣會除以零；直接在多項式 恆等式中代入才是合法操作。

多項式整除 $g\mid f$ 的意思是：同一係數域中存在多項式 $q$ 使 $f=gq$。若 $g$ 非零，這等價於餘式為零。特別地，每個多項式都整除 零多項式，但帶餘除法要求除式非零。

定理

因式定理

對 $f(x)\in R[x]$ 與 $a\in R$，

$$(x-a)\mid f(x)\quad\Longleftrightarrow\quad f(a)=0.$$

因式定理把代數因式與根連起來：一個根給出一個一次因式，而一個一次因式也給出 一個根。

非零多項式可以有多少個根？

因式定理給出根的數量上界。

定理

根的數量上界

一個 $R$ 或 $C$ 上的非零 $n$ 次多項式最多有 $n$ 個相異根。

歸納起點是次數 $0$：非零常數不可能取零值。假設結論對 $n$ 次多項式 成立，考慮 $n+1$ 次的 $f$。若它無根，結論已經成立；否則取一個根 $a$。 因式定理給出 $f(x)=(x-a)q(x)$，其中 $q$ 非零，由乘積次數規則可知 其次數為 $n$。

若 $b\ne a$ 是另一個根，代入得 $0=(b-a)q(b)$。純量 $b-a$ 在係數域中 非零，所以 $q(b)=0$。歸納假設保證這類相異根最多有 $n$ 個，再加上 $a$ 這個值，最多有 $n+1$ 個。論證不要求 $q(a)\ne0$；即使 $a$ 也是 $q$ 的根，在根的集合中仍只算一個值。

因此，若一個次數至多 $n$ 的多項式有 $n+1$ 個相異根，它必定是零多項式。

根數上界也需要精確的假設。零多項式在每個輸入處都為零，所以必須排除。 「相異」計算的是不同值，而不是某個因式出現的次數。把上界用於 $p-q$ 可知：若兩個次數至多 $n$ 的多項式在 $n+1$ 個相異輸入處相等，則它們 相等；否則非零的差會有過多的根。在每個實數輸入處都相等是其特例， 這便補全了形式多項式與代入所得函數之間的聯繫。

已給枚舉的可數乘積與並

設 $I\subseteq\mathbb N$。對每個 $i\in I$，假設定義域 $D_i\subseteq\mathbb N$ 和滿射 $e_i:D_i\to A_i$ 已作為一族數據同時給定。空集合使用 $D_i=\varnothing$；有限列表可使用有限的 $D_i$。在這些假設下，$\bigcup_{i\in I}A_i$ 可數。同樣，兩個已給枚舉的集合的乘積也可數。

證明。 固定雙射 $\pi:\mathbb N^2\to\mathbb N$：

$$\pi(i,k)=\frac{(i+k)(i+k+1)}2+k.$$

它依次掃描有限對角線。對於並集，只保留滿足 $i\in I$ 且 $k\in D_i$ 的數對，按其 $\pi$ 指標次序輸出 $e_i(k)$。由於給定映射是滿射，並集的每個元素都會出現。對每個輸出 $x$，$x$ 出現的指標構成 $\mathbb N$ 的非空子集，故有唯一最小元。把 $x$ 對應到這個最小指標得到單射：一個指標只對應一個數對，因而只有一個輸出。因此並集可數；空並的情形顯然。這個構造直接使用題設給定的各集合枚舉。

對於乘積 $A\times B$，使用給定的映射 $a:D\to A$ 與 $b:E\to B$，只保留 $(j,k)\in D\times E$。輸出 $(a(j),b(k))$ 覆蓋乘積的每個元素；同樣將每個輸出對應到其有效 $\pi$ 指標的最小值，即可證明可數。若任一因子為空，乘積為空。

統一構造有理數列表。 固定 $\mathbb Q$ 的一個枚舉 $q_0,q_1,\ldots$。對每個固定的 $n\ge1$，按坐標和遞增、同和時按字典序列出 $\mathbb N^n$ 的指標元組，並將 $(i_1,\ldots,i_n)$ 送到 $(q_{i_1},\ldots,q_{i_n})$。每個元組都會出現，且每條對角線有限。$n=0$ 時使用唯一的空元組。這些規則同時給出所有 $n$ 的列表，因此有限有理字符串的並可數，無須選擇未指定的列表。

非零有理係數多項式只有有限個實根。對給定可數列表中的每個非零多項式，將其實根按從小到大排列；沒有實根時使用空列表。實數集合 $\mathbb R$ 的每個有限子集都有唯一的遞增列表，故此規則給出整族根的列表，無須任意選擇枚舉。它們的並就是代數實數的集合，所以該集合可數。

可由某類有限字符串描述的實數至多可數，但這不能證明每個實數都有這種描述。不可數性說明後者不能未經證明地假設。

4. 有限樹節點與無限分支

令 $W_n$ 為長度為 $n$ 的二進制串集合，含 $2^n$ 個元素。按長度再按字典序列舉，$W=\bigcup_{n\ge0}W_n$ 可數；空串是長度為零的唯一節點。

無限二進制序列不是這些有限節點之一，它是在每一層選取互相相容的節點而成的無限分支。若分支被列為 $b^{(0)},b^{(1)},\ldots$，定義新分支 $d$，使 $d_n=1-b^{(n)}_n$。它在第 $n$ 個坐標不同於第 $n$ 個分支，故不等於列表中任何一項。因此儘管有限節點集合可數，無限分支仍不可數。

錯誤推理。 “每個無限序列由可數個有限前綴組成，所有有限前綴組成可數集，因此所有無限序列組成可數集。”前提說前綴屬於 $W$，結論卻把 $W$ 的子集族當作 $W$ 的子集。分支是一整個相容節點子集，而非單個節點；可數集的冪集可以不可數。可數並定理需要事先有可數的分支指標集，而這正是待證明的結論。

5. 可數基不意味著只有可數個開集

有理端點開區間組成可數族。每個開集 $U\subseteq\mathbb R$ 都是該族中一些成员的並：對每個 $x\in U$，先取包含 $x$ 且含於 $U$ 的小區間，再用有理數稠密性在 $x$ 兩側選取區間內的有理端點。取所有含於 $U$ 的有理端點區間，恰好得到 $U$。

開集卻不可數：映射 $a\mapsto(a,\infty)$ 從 $\mathbb R$ 到開集族是單射。若 $a<b$，二者之間的點屬於第一個半直線而不屬於第二個。這不矛盾：每個開集使用可數基的一個子族，但子族本身可以不可數多個。這與節點和分支的混淆相同。

6. 選讀：很短的覆蓋也可容納不可數集

對二進制序列 $b=(b_0,b_1,\ldots)$，令 $x_b=\sum_{n\ge0}2b_n/3^{n+1}$。等比級數保證它在 $[0,1]$ 中。令 $s_k=b_{k-1}$，並定義 $\Phi((s_k)_{k\ge1})=\sum_{k=1}^{\infty}2s_k/3^k$；此映射與 $b\mapsto x_b$ 僅差指標重命名。

為證明單射而不使用錯誤的 “端點展開唯一”說法，設兩序列第一次在第 $m$ 位不同。首項差的絕對值 是 $2/3^m$，而全部尾項的最大絕對值不超過

$$\sum_{k=m+1}^{\infty}\frac2{3^k}=\frac1{3^m}.$$

首項差嚴格更大，不可能被尾項抵銷，所以 $\Phi$ 是單射。

因此所有這些值組成的集合 $K$ 不可數。固定前 $n$ 位後，每個值落在 $2^n$ 個閉區間之一中；餘項從零到 $3^{-n}$，所以每個區間長度為 $3^{-n}$。故 $K$ 有總區間長度為 $(2/3)^n$ 的有限覆蓋，且該長度趨於零。這只是有關明確有限覆蓋長度的陳述，不需要測度論術語；基數不能直接等同於幾何長度。

構造與驗證練習

1. 定義邊界。 解釋為何“可數當且僅當存在從 $\mathbb N$ 出發的滿射”須加非空條件，並給出適用於所有集合的版本。
2. 次序。 不借助最小元零，證明 $\mathbb Q\cap(0,1)$ 沒有嚴格遞增的枚舉。
3. 覆蓋。 用有限串給出所有有理系數多項式的窮儘列舉，指出兩種重複描述的來源。
4. 樹的區別。 證明最終等於零的二進制序列構成可數集，而所有無限二進制序列不構成可數集。說明“最終”允許依賴甚麼。
5. 開集診斷。 學生說可數基成员的並只有可數種可能。指出混淆的對象，並給出單射反例族。
6. 幾何界。 在選讀的 $K$ 構造中，證明每個 $\varepsilon>0$ 都有總長度小於 $\varepsilon$ 的有限區間覆蓋。為何這不能枚舉 $K$？

完整解答

1. 空集有限，故可數；但從 $\mathbb N$ 出發的函數必須給零賦值，不可能以空集為目標。正確表述是：“$A$ 可數，當且僅當 $A$ 為空，或存在從 $\mathbb N$ 到 $A$ 的滿射。”對所有集合，也等價於存在單射 $A\to\mathbb N$，其中包含空函數。
2. 任何候選遞增枚舉的首項為 $q_0\in(0,1)$。有理數 $q_0/2$ 也在該集合，但小於首項，不能在嚴格遞增序列稍後出現，因此枚舉不完備。這裡使用首項，而不是假設集合有最小元。
3. 先用整數與正分母對枚舉有理數。對每個有限長度，用重複對角枚舉列出有理數指標的元組，再交錯各長度，輸出相應系數多項式。同一有理數的不同分式表示可產生重複系數，末尾零可產生長度不同但相同的多項式。可數性不要求必須去重；每個多項式有有限系數元組，因而被到達。
4. 對每個截斷位置 $N$，從第 $N$ 項起為零的序列由前 $N$ 位確定，只有 $2^N$ 種。按截斷位置及有限前綴列舉，得其並可數。截斷位置可以依賴序列，不要求統一的截斷值。對任意無限序列，上述對角構造击敗每個候選列表，故不可數；按截斷位置的可數並只覆蓋最終為零的分支。
5. 基是單個區間構成的可數集合，其子族形成的是冪集，不是基本身。不同子族可產生許多不同的並。實數 $a$ 對應的開半直線 $(a,\infty)$ 已按上述單射證明構成不可數族，因此原斷言錯誤。
6. 選 $n$ 使 $(2/3)^n<\varepsilon$。按前 $n$ 位把點分組，取對應的 $2^n$ 個閉區間，每個尾部寬度為 $3^{-n}$。它們給出所需總長度的有限覆蓋。每個區間仍可含不可數多個不同的後續分支，集合的覆蓋不是其元素的列表。二進制序列的單射構造獨立證明 $K$ 不可數。

總結與術語

窮儘列舉在有限位置到達每個元素，不一定按大小排列或可計算。有限描述是一條有限串，而無限相容描述的族可以不可數。基是生成開集的集合，而不是其所有子族的集合。應用可數並論證前，應證明列舉的覆蓋性並辨認被計數的對象。