可数性深入：列举、树与错误的枚举

学习目标与准备

列出集合的元素需要说明顺序，证明每个元素在有限位置出现，并处理重复和空集。本章比较递增列举、对角列举与有限字符串树，检查有关无限对象的错误推理。预备知识包括函数、自然数良序、有限积、等比级数和对角线定理。

取 $\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$ 不可数。

总结与术语

穷尽列举在有限位置到达每个元素，不一定按大小排列或可计算。有限描述是一条有限串，而无限相容描述的族可以不可数。基是生成开集的集合，而不是其所有子族的集合。应用可数并论证前，应证明列举的覆盖性并辨认被计数的对象。