以下证明中，$R=\mathbb R$、$Q=\mathbb Q$、$C=\mathbb C$、$Z=\mathbb Z$，且 $N=\mathbb N=\{0,1,2,\ldots\}$。

用来比较集合的函数

设 $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$ 不是输出。这个小例子把两个条件分开：单射关注输出是否重复，满射关注陪域 元素是否遗漏。

相同基数与可数性

概念视角结构

把基数理解为数数与配对

对于有限集合，大小很容易让人联想到清点：把元素一个个数出来。对于任意集合，定义则把这种清点改成配对检验：能否把 $X$ 的每个元素与 $Y$ 的恰好一个元素配对，并且反向也能做到？这就是为什么 $N$ 与偶数自然数 $2N=\{0,2,4,\ldots\}$ 通过 $n\mapsto 2n$ 具有相同基数，尽管 $2N$ 是 $N$ 的真子集。双射记录了相同的大小；真包含本身并不意味着基数严格更小。

定义

相同基数

若存在双射 $f:X\to Y$，就称集合 $X$ 与 $Y$ 有相同基数，并写成

$$|X|=|Y|.$$

被配对的元素不必具有相同性质。把数与有序对配对，与把两列数字配对一样合 法。对有限集合，这个定义与普通数数一致。

定义

有限集合

若某个 $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$。在这条对角线之前 只有有限条对角线，而它本身也只有有限个数对，所以 $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$ 选择一个原像。下一篇笔记会讨论这个选择问题；本节直 接使用单射与双射，不额外假设选择函数。

可数个可数集合的并仍可数

定理

可数个可数集合的并仍可数

假设选择公理，若 ${A_n}_{n\in N}$ 是一个可数族，而每个 $A_n$ 都可数， 则

$$A=\bigcup_{n\in N} A_n$$

可数。

若 $A=\varnothing$，空函数立即给出到 $N$ 的单射。现在假设 $A$ 非空。 由于每个 $A_n$ 可数，对每个指标 $n$ 都存在单射

$$i_n:A_n\to N.$$

当 $A_n=\varnothing$ 时，唯一的空函数就是这样的单射。这里使用选择公理 同时选出整族单射 ${i_n}$，包括这些空成员的情况。这里需要选择的是整族 见证映射；这并不是说任意多个不可数集合的可数并会变成可数。

定义

$$h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)),$$

其中

$$n(x)=\min\{n\in N\mid x\in A_n\}.$$

因为 $x$ 属于并集，指标集非空；自然数的良序性保证最小指标存在。 这一归纳法推论的证明见 6.3 区间、Cantor 集、稠密性与良序。 映射 $h$ 是单射：若 $h(x)=h(x')$，第一坐标给出 $n(x)=n(x')=n$，第二坐标再给出 $i_n(x)=i_n(x')$，而 $i_n$ 的单射性推出 $x=x'$。

最后，$N\times N$ 的对角枚举给出单射 $N\times N\to N$，与 $h$ 合成便得 到单射 $A\to N$。先列 $(0,0)$，再列坐标和为 $1$、$2$ 等的点，每个点都 在有限阶段出现；空成员不贡献并集元素。指标集与每个成员都必须可数，否则 不可数的指标集单点族或一个不可数成员都可能使并集不可数。

常见错误

可数并不等于任意并

这个定理处理的是可数族 ${A_n}$。它不是说任意多个可数集合的并都必定可数。

定理

有理数稠密

设 $r\in R$ 且 $\epsilon\gt 0$。取 $n\in N$ 使 $n\gt 1/\epsilon$。整数集 $\{m\in Z\mid m\le nr\}$ 有最大元 $m_0$， 所以

$$m_0\le nr\lt m_0+1 \quad\Longrightarrow\quad 0\le r-\frac{m_0}{n}\lt\frac1n\lt\epsilon.$$

于是 $q=m_0/n\in Q$ 与 $r$ 的距离小于 $\epsilon$，证明 $Q$ 在 $R$ 中稠密。

多项式作为有限形式和

定义

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$ 的每个有限子集都有唯一的递增列表，故此规则给出整族根的列表，无须任意选择枚举。它们的并就是代数实数的集合，所以该集合可数。

稠密性、可数性与有理端点区间

集合 $D\subseteq\mathbb R$ 称为稠密的，如果每个非空开区间都含有 $D$ 的元素。有理数的稠密性推出无理数的稠密性：固定一个无理数 $\alpha$，取有理数 $q\in(a-\alpha,b-\alpha)$，则 $q+\alpha\in(a,b)$ 且它是无理数。因此，可数集合也可以稠密，两个不相交的稠密集合也可以共存。稠密性和基数回答的是不同问题。

例子

可数而稠密的有理点。 有理点可以编号，尽管每个区间都含有无穷多个有理数。按分母和分子列出它们，并不会使它们成为孤立点。

有限有理数据。 对每个固定的 $n$，有理数 $n$ 元组的集合由有限次乘积可知是可数的。对 $n$ 取并，得到所有有限有理字符串构成可数集合；特别地，有理系数多项式构成可数集合。每个非零多项式只有有限个根，所以代数实数构成可数集合。由于 $\mathbb R$ 不可数，超越数存在。

练习

P01. 设 $\mathbb N=\{0,1,2,\ldots\}$。明确列出所有整数，并给出从 $\mathbb N$ 到非负偶数集合的一个双射。

P02. 证明从不可数集合中去掉一个可数集合后，剩余集合仍不可数。

P03. 利用有理数的稠密性，证明每个满足 $a<b$ 的区间 $(a,b)$ 都含有无理数。

P04. 证明以有理数为端点的开区间全体构成可数集合，并证明 $\mathbb R$ 的每个开子集都是其中某些区间的并。

完整解答

P01. 将整数列为 $0,1,-1,2,-2,\ldots$。映射 $n\mapsto2n$ 是从 $\mathbb N$ 到非负偶数集合的双射。

P02. 如果去掉的集合和剩余集合都可数，则它们的并可数，与原集合不可数矛盾。若去掉的集合不是原集合的子集，就改用它与原集合的交集。

P03. 固定一个无理数 $\alpha$，例如 $\sqrt2$。由有理数的稠密性，存在 $q\in(a-\alpha,b-\alpha)\cap\mathbb Q$。于是 $q+\alpha\in(a,b)$。若它是有理数，减去 $q$ 就得到 $\alpha$ 是有理数，矛盾。

P04. 有理数对的集合可数，其中第一坐标小于第二坐标的子集也可数。若 $x$ 属于开集 $U$，取 $\varepsilon>0$ 使 $(x-\varepsilon,x+\varepsilon)\subseteq U$，再取有理数 $r\in(x-\varepsilon,x)$ 和 $s\in(x,x+\varepsilon)$。区间 $(r,s)$ 包含 $x$ 且包含于 $U$。所有这类区间的并恰为 $U$；当 $U=\varnothing$ 时，该并为空集。