知识焦点
先建立概念地图
- countability
- injective
- surjective
- Cantor diagonal argument
- Bernstein-Schroder theorem
- Cartesian product
- induction
CS70 · 讨论课 05b
围绕集合可数性的练习：判断可数/不可数命题的真伪、找出对角线论证中的错误、用定义验证单射与满射、应用 Bernstein-Schroder 定理比较势，以及通过之字形枚举与归纳法证明可数笛卡儿积的可数性。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis05b.pdf、solutions/discussion/dis05b-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 4 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis05b.pdf、solutions/discussion/dis05b-sol.pdf判断下列命题的真假。
（参见讲义 Note 11）
(a) 所有无理数构成的集合 \(\mathbb{R}\setminus\mathbb{Q}\)（即不是有理数的实数）是不可数的。
(b) 所有满足方程 \(3x \equiv 2 \pmod{10}\) 的整数 \(x\) 构成的集合是可数无穷的。
(c) 方程 \(x + y = 1\) 的所有实数解构成的集合是可数的。
对于任意两个函数 \(f : Y \to Z\) 与 \(g : X \to Y\)，定义它们的复合函数 \(f \circ g : X \to Z\) 为：对所有 \(x \in X\)，\((f \circ g)(x) = f(g(x))\)。判断下列命题的真假。
(d) 若 \(f\) 与 \(g\) 均为单射（injective，one-to-one），则 \(f \circ g\) 是单射。
(e) 若 \(f\) 是满射（surjective，onto），则 \(f \circ g\) 是满射。
可数性部分回顾基本事实：可数集的并仍是可数集，而 \(\mathbb{R}\) 不可数；解同余方程时先找出模 \(10\) 下 \(3\) 的乘法逆元；实数解集合可尝试建立与 \(\mathbb{R}\) 的双射。
复合函数部分从定义出发：单射要求不同的输入映到不同的输出；满射要求值域中每个元素都有原像，特别注意 \(g\) 的像集未必充满整个 \(Y\)，可构造有限集上的反例来检验。
(a) 真。用反证法。假设无理数集合是可数集。由讲义 Note 10 知有理数集 \(\mathbb{Q}\) 是可数集。因为两个可数集的并是可数集，这将推出实数集 \(\mathbb{R}\) 是可数集。但由 Note 10 知这是不成立的。矛盾！
(b) 真。将同余方程两边同乘以 \(7\)（即 \(3\) 关于模 \(10\) 的乘法逆元），得 \(x \equiv 4 \pmod{10}\)。所有满足该式的整数构成的集合为 \(S = \{10k + 4 : k \in \mathbb{Z}\}\)，显然映射 \(k \mapsto 10k + 4\) 是 \(\mathbb{Z}\) 到 \(S\) 的一个双射。因为 \(\mathbb{Z}\) 是可数无穷的，所以 \(S\) 也是可数无穷的。
(c) 假。设 \(S \subset \mathbb{R} \times \mathbb{R}\) 为给定方程的所有实数解构成的集合。对任意 \(x' \in \mathbb{R}\)，数对 \((x', y') \in S\) 当且仅当 \(y' = 1 - x'\)。因此 \(S = \{(x,\,1 - x) : x \in \mathbb{R}\}\)。此外，映射 \(x \mapsto (x,\,1 - x)\) 是 \(\mathbb{R}\) 到 \(S\) 的一个双射。因为 \(\mathbb{R}\) 是不可数的，所以 \(S\) 也是不可数的。
(d) 真。回顾函数 \(h : A \to B\) 是单射当且仅当对所有 \(a_1, a_2 \in A\)，\(a_1 \neq a_2 \Rightarrow h(a_1) \neq h(a_2)\)。任取 \(x_1, x_2 \in X\) 且 \(x_1 \neq x_2\)。因为 \(g\) 是单射，所以 \(g(x_1) \neq g(x_2)\)。又因为 \(f\) 是单射，所以 \(f(g(x_1)) \neq g(g(x_2))\)。因此 \(f \circ g\) 是单射。
(e) 假。回顾函数 \(h : A \to B\) 是满射当且仅当 \(\forall b \in B,\, \exists a \in A\) 使得 \(h(a) = b\)。令 \(g : \{0,1\} \to \{0,1\}\) 定义为 \(g(0) = g(1) = 0\)。令 \(f : \{0,1\} \to \{0,1\}\) 定义为 \(f(0) = 0\)，\(f(1) = 1\)。则复合函数 \(f \circ g : \{0,1\} \to \{0,1\}\) 满足 \((f \circ g)(0) = (f \circ g)(1) = 0\)。这里 \(f\) 是满射，但 \(f \circ g\) 不是满射。
解答来源：solutions/discussion/dis05b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis05b.pdf · 1 · confidence: high
找出下面证明中的精确错误。
错误命题：满足 \(0 \leq r \leq 1\) 的有理数 \(r\) 构成的集合是不可数的。
证明? 假设相反地存在一个双射 \(f : \mathbb{N} \to \mathbb{Q}_{[0,1]}\)，其中 \(\mathbb{Q}_{[0,1]}\) 表示 \([0,1]\) 中的有理数。这使我们能够列出 \(0\) 与 \(1\) 之间的所有有理数，其中列表的第 \(j\) 个元素为 \(f(j)\)。假设我们把每个有理数都写成其非终止小数展开（例如，写成 \(0.4999\ldots\) 而非 \(0.5\)）。
令 \(d_j\) 表示 \(f(j)\) 的第 \(j\) 位小数。我们定义一个新数 \(e\)，其第 \(j\) 位小数 \(e_j\) 等于 \((d_j + 2) \bmod 10\)。我们断言 \(e\) 不在我们列出的 \(0\) 与 \(1\) 之间的有理数之中。这是因为，\(e\) 不可能等于任何一个 \(f(j)\)，因为它在第 \(j\) 位小数上与 \(f(j)\) 相差超过 \(1\)。
这是一个矛盾，因此 \(0\) 与 \(1\) 之间的有理数集合是不可数的。
注意对角线构造法生成的数 \(e\) 的小数展开特征：题设要求把每个有理数写成非终止展开。思考 \(e\) 是否仍一定是有理数，以及它不在列表中是否真的构成矛盾。
证明中构造出的数 \(e\) 可能是无理数（事实上，它必然是无理数）。因此 \(e\) 与所有 \(f(j)\) 都不同并不能导出矛盾。
解答来源：solutions/discussion/dis05b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis05b.pdf · 1 · confidence: high
（参见讲义 Note 11）
(a) 函数 \(f : \mathbb{N} \to \mathbb{N}\) 定义为 \(f(n) = n^2\)，它是否是单射（one-to-one）？简要说明。
(b) 函数 \(f : \mathbb{R} \to \mathbb{R}\) 定义为 \(f(x) = x^3 + 1\)，它是否是满射（onto）？简要说明。
(c) Bernstein-Schroder 定理指出：若集合 \(A\) 与 \(B\) 之间存在单射 \(f : A \to B\) 与 \(g : B \to A\)，则 \(A\) 与 \(B\) 之间存在双射。请通过构造适当的单射，证明开区间 \((0,1)\) 与 \(\mathbb{R}_+ = (0, \infty)\) 具有相同的势。
(a)(b) 直接用定义验证：单射检查不同的输入是否映到不同的输出；满射检查对每个目标值是否都能解出对应的自变量。
(c) 一个方向可用恒等或单调嵌入把 \((0,1)\) 映到 \((0,\infty)\)；另一个方向找一个把无穷区间压缩进单位区间的单射，例如形如 \(\frac{1}{x+1}\) 的分式。
(a) 是。一种直观方式是画出 \(n\) 到 \(n^2\) 的一一对应。更形式地，可通过说明原像唯一来证明，即证 \(m \neq n \Rightarrow f(m) \neq f(n)\)。
证法一：设 \(m \neq n\)，不妨设 \(m > n\)，则 \(f(m) = m^2 > n^2 = f(n)\)，故 \(f(m) \neq f(n)\)。
证法二：用反证法（逆否命题），\(f(m) = f(n) \Rightarrow m = n\)。 \[ f(m) = f(n) \;\Rightarrow\; m^2 = n^2 \;\Rightarrow\; m^2 - n^2 = 0 \;\Rightarrow\; (m-n)(m+n) = 0 \;\Rightarrow\; m = \pm n . \] 由于 \(n\) 不可能为负，故 \(m = n\)，因此 \(f\) 是单射。
(b) 是。对任意 \(y \in \mathbb{R}\)，都存在对应的 \(x \in \mathbb{R}\) 使得 \(y = f(x)\)。取 \(x = \sqrt[3]{y - 1}\) 即可。
(c) 从 \((0,1)\) 到 \((0, \infty)\) 的单射是显然的；考虑函数 \(f : (0,1) \to (0, \infty)\) 定义为 \(f(x) = x\)。易见 \(f\) 是单射。
对另一个方向，考虑函数 \(g : (0, \infty) \to (0,1)\) 定义为 \[ g(x) = \frac{1}{x + 1}. \] 为说明 \(g\) 是单射，设 \(g(x) = g(y)\)，则 \[ \frac{1}{x + 1} = \frac{1}{y + 1} \;\Rightarrow\; x = y . \] 因此 \(g\) 是单射。于是我们得到从 \((0,1)\) 到 \((0, \infty)\) 的单射，以及从 \((0, \infty)\) 到 \((0,1)\) 的单射。由 Bernstein-Schroder 定理，\((0,1)\) 与 \((0, \infty)\) 之间存在双射，从而它们具有相同的势。
解答来源：solutions/discussion/dis05b-sol.pdf · 2 · confidence: high
题面来源：discussion/dis05b.pdf · 2 · confidence: high
（参见讲义 Note 11）对集合 \(A\) 与 \(B\)，定义笛卡儿积为 \(A \times B = \{(a, b) : a \in A,\, b \in B\}\)。
(a) 给定两个可数集 \(A\) 与 \(B\)，证明 \(A \times B\) 是可数集。
(b) 给定有限个可数集 \(A_1, A_2, \ldots, A_n\)，证明 \[ A_1 \times A_2 \times \cdots \times A_n \] 是可数集。
(a) 回想课堂上通过构造"之字形"（zigzag）枚举来证明 \(\mathbb{N} \times \mathbb{N}\) 可数的方法；利用每个可数集与自然数某子集之间的双射，把该论证迁移到 \(A \times B\)。
(b) 对 \(n\) 进行数学归纳，并反复利用 (a) 的结论：把前 \(n\) 个集合的积视作一个可数集，再与第 \(n+1\) 个集合取积。
(a) 课堂已证明 \(\mathbb{N} \times \mathbb{N}\) 是可数集，方法是构造一个枚举所有数对的"之字形"映射： \[ (0,0),\;(1,0),\;(0,1),\;(2,0),\;(1,1),\;\ldots \] 由于 \(A\) 与 \(B\) 都是可数集，故每个集合与 \(\mathbb{N}\) 的某个子集之间存在双射。因此 \(A \times B\) 是可数集，因为 \(\mathbb{N} \times \mathbb{N}\) 的一个子集与 \(A \times B\) 之间存在双射：\(f(i, j) = (A_i, B_j)\)。我们可以类似地枚举所有数对 \((a, b)\)。
(b) 用数学归纳法。
基础情形：\(n = 2\)。由 (a) 知 \(A_1 \times A_2\) 是可数集，因为 \(A_1\) 与 \(A_2\) 都是可数集。
归纳假设：设对某个 \(n \in \mathbb{N}\)，\(A_1 \times A_2 \times \cdots \times A_n\) 是可数集。
归纳步骤：考虑 \(A_1 \times \cdots \times A_n \times A_{n+1}\)。由归纳假设，\(A_1 \times \cdots \times A_n\) 是可数集，记 \(C = A_1 \times \cdots \times A_n\)。由 (a) 知，由于 \(C\) 与 \(A_{n+1}\) 都是可数集，故 \(C \times A_{n+1}\) 是可数集，这就证明了结论。
解答来源：solutions/discussion/dis05b-sol.pdf · 3 · confidence: high
题面来源：discussion/dis05b.pdf · 2 · confidence: high
discussion/dis05b.pdfsolutions/discussion/dis05b-sol.pdf