规模计算 ·

|A|

\aleph_0

基数：有限、可数无限与不可数

集合的「大小」叫基数，记作 $|A|$ 。有限集的基数就是元素个数，一个自然数；无限集没有这样的自然数可数，「大小」必须换一种定义方式。可用的判据只有一条：两个集合之间若存在双射，就说它们等势（equinumerous），记 $A \sim B$ 。等势是一个等价关系，基数就是它的等价类。有限情形下这个定义与「数个数」一致——两个有限集等势当且仅当元素个数相同——所以它是旧定义的推广而非替换。

1 · 有限集的计数与容斥

finite ·

|A \cup B| = |A| + |B| - |A \cap B|

有限集的并集大小不是 $|A| + |B|$ ：落在 $A \cap B$ 里的元素在两个加数中各被数一次，共计两次。减掉多算的那一次，即得两个集合的容斥原理。

定理 1.1（两集合容斥）设 $A$ 、 $B$ 为有限集，则 $|A \cup B| = |A| + |B| - |A \cap B|$ 。

证明把 $A \cup B$ 拆成三块两两不交的部分： $A - B$ 、 $A \cap B$ 、 $B - A$ 。有限集在不交并上基数相加，故 $|A \cup B| = |A - B| + |A \cap B| + |B - A|$ 。又 $A$ 是 $A - B$ 与 $A \cap B$ 的不交并，得 $|A - B| = |A| - |A \cap B|$ ，同理 $|B - A| = |B| - |A \cap B|$ 。代回即得。∎

证明只用到「不交并上基数相加」这一条，推广到更多集合并无新障碍：三个集合要加回被减两次的三重交， $n$ 个集合的通式按交集的重数交替加减（见容斥原理）。

图 1-1 · 两集合的容斥关系，交集部分被重复计数一次。可改动

A

与

B

的成员，观察

|A \cup B|

的三项如何变化。

2 · 无限集与真子集的等势

infinite ·

\mathbb{N} \sim

偶数 · 可数

\aleph_0

自然数集 $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ 是无限集。取偶数集 $E = \{0, 2, 4, \dots\}$ ，它是 $\mathbb{N}$ 的真子集，少了全部奇数，按有限集的直觉应当「更小」。但 $n \mapsto 2n$ 是 $\mathbb{N}$ 到 $E$ 的双射：每个自然数恰有一个偶数与之配对，反之亦然。按等势的定义，二者基数相同。

警示 · 这条性质不能读成「无限集与它的任意真子集等势」。 $\mathbb{N}$ 的真子集 $\{0\}$ 只有一个元素，与 $\mathbb{N}$ 显然不等势。正确的表述是存在性的：一个集合若与它的某个真子集等势，则它是无限集，反之亦然（Dedekind 无限；「反之」一步用到可数选择公理，高中范围内不区分这一层）。

能与 $\mathbb{N}$ 建立双射的集合叫可数无限（countably infinite），基数记作 $\aleph_0$ 。这等于说它的元素可以排成一列 $a_0, a_1, a_2, \dots$ ，不重不漏——「可数」就是「可编号」。

图 2-1 · 自然数与偶数之间的一一对应。可推进映射，观察真子集如何与全集等势。

3 · 可数与不可数的分界

countable ·

\mathbb{Q} \sim \mathbb{N}

\mathbb{R} \not\sim \mathbb{N}

有理数集 $\mathbb{Q}$ 在数轴上处处稠密，任意两个有理数之间还有无穷多个，直觉上应当比 $\mathbb{N}$ 「密得多」。它仍是可数的：把正分数 $p/q$ 摆在格点 $(p, q)$ 上，按 $p + q$ 的值逐层沿对角线走，就把它们排成了一列。

$\mathbb{R}$ 则不然。Cantor 对角论证表明，任何一列实数都漏掉了某个实数，因此 $\mathbb{R}$ 与 $\mathbb{N}$ 之间不存在双射（论证见无理数与不可数性）。 $|\mathbb{R}|$ 是一个严格大于 $\aleph_0$ 的基数，无限因此不止一种大小。

这条对角线枚举给出的是满射，不是双射。实跑一遍即见：取 $p + q \le 200$ 的全部格点共 $19900$ 个，去重后只剩 $12231$ 个不同的有理数， $7669$ 个格点（ $38.5\%$ ）落在已经出现过的值上， $1/1$ 、 $2/2$ 、 $3/3$ 都是同一个数。 $p + q \le 10$ 这一段的比例更容易手验： $45$ 个格点给出 $31$ 个不同值，其中 $14$ 个重复。可数性只要求存在满射，从满射抽出子列即可做成双射，所以结论不受影响；但若要枚举本身就是双射，得跳过 $\gcd(p, q) \ne 1$ 的格点。

4 · 参考文献

Cardinality. Wikipedia. 等势的定义、基数的比较与 $\aleph_0$ 的记号。https://en.wikipedia.org/wiki/Cardinality
Dedekind-infinite set. Wikipedia. 「与某个真子集等势」这一刻画，及它与一般无限定义的等价性所需的选择公理强度。https://en.wikipedia.org/wiki/Dedekind-infinite_set
Countable set. Wikipedia. 可数的等价刻画与 $\mathbb{Q}$ 的对角线枚举。https://en.wikipedia.org/wiki/Countable_set
Cantor's diagonal argument. Wikipedia. $\mathbb{R}$ 不可数的对角论证。https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument