Lecture 2: Cantor’s Theory of Cardinality (Size)（康托尔的基数大小理论）

目录 · ← l1 · l3 →

Lecture 2: Cantor’s Theory of Cardinality (Size)（康托尔的基数大小理论）

概述

本讲回答一个问题：两个集合什么时候”一样大”？（源文件 Question 10）。对于像 $\{1,2,3\}$ 这样的小有限集，答案似乎不值一问——数一数就行。可一旦集合是无限的，”数一数”就失去了字面意义：$\mathbb{N}$ 里的数永远数不完。康托 (Georg Cantor) 在 19 世纪给出了一个反直觉但极其坚固的回答：“一样大”不靠数数，而靠”配对”——如果两个集合的元素之间能建立一一配对，它们就一样大。这就是 Definition 11（Cardinality，基数）的内容。

为了把”配对”说精确，本讲先引入了三类函数（源文件 “Functions” 一节）：单射 (injective / one-to-one)、满射 (surjective / onto)、双射 (bijective)，并定义了像 $f(C)$ 与原像 $f^{-1}(D)$。随后给出基数的记号体系（$\vert A\vert =\vert B\vert $、$\vert A\vert =n$、$\vert A\vert \le\vert B\vert $、$\vert A\vert <\vert B\vert $）、Cantor–Schröder–Bernstein 定理（Theorem 12）的陈述、可数 (countable) / 不可数 (uncountable) 的定义，以及 Example 13 中三个”反直觉等式”：偶数集与 $\mathbb{N}$ 一样大、奇数集与 $\mathbb{N}$ 一样大、正有理数集与 $\mathbb{N}$ 一样大。

本讲在整个课程中的位置：它是整门课唯一的”纯集合论”讲次，也是后面所有”存在性”论证的语法基础。第 6 讲证明 $(0,1]$ 与 $\mathbb{R}$ 不可数，用的正是”若可数则存在双射 $x:\mathbb{N}\to(0,1]$”这一表述；第 3 讲的 Cantor 定理 $\vert A\vert <\vert \wp(A)\vert $ 则完全建立在本讲的 $\vert \cdot\vert \le\vert \cdot\vert $ 与 $\vert \cdot\vert <\vert \cdot\vert $ 记号之上。可以说，本讲是”把大小变成语言”的一讲。

一句话概括本讲要回答的问题：当”数不完”的时候，我们凭什么说两个无限集”一样多”、”一个比另一个多”？

核心定义与直观解释

函数与像/原像（源文件 “Functions” 一节）

• 严格定义：设 $A,B$ 是集合。一个函数 (function) $f:A\to B$ 是一种对应关系，它把每个 $x\in A$ 指派到 $B$ 中唯一的一个元素，记作 $f(x)$。在此基础上：
  1. 若 $C\subset A$，定义 $f$ 在 $C$ 上的像 (image) 为 \(f(C):=\{y\in B\mid y=f(x)\ \text{对某个}\ x\in C\}.\)
  2. 若 $D\subset B$，定义 $D$ 的原像 (inverse image / preimage) 为 \(f^{-1}(D):=\{x\in A\mid f(x)\in D\}.\)

• 直观解释（”它到底在说什么？”）：把 $f$ 想成一台自动售货机：投进一个 $x\in A$（域中的元素），它吐出唯一的 $f(x)\in B$。函数的第一要求是“确定性”——同一个输入必须给同一个输出，绝不允许”今天投 1 块钱出可乐、明天出雪碧”。第二要求是“域内处处有定义”——$A$ 里的每一个元素都必须能被投进去；$B$ 里有没有剩货则无所谓。

• 为什么需要”唯一”这个条件？：如果没有唯一性，$f(x)$ 就不是一个确定的元素，”$f(x)=f(y)$”这种句子就没有意义，后面所有关于单射、双射的定义全都崩塌。反过来，”$A$ 中每个元素都有像”这一条也不能省：若 $A=\{1,2,3\}$，只规定 $f(1)=f(2)=0$，那这不是一个定义在 $\{1,2,3\}$ 上的函数，只能说它定义在 $\{1,2\}\subset A$ 上（此时 $\{1,2\}$ 才是真正的定义域）。

• 定义域、陪域、值域三兄弟：
  • 定义域 (domain)：$A$，输入的全集，必须被”喂满”。
  • 陪域 (codomain)：$B$，输出所在的目标集合，是”允许落在哪里”的容器。
  • 值域 (range / image)：$f(A)=\{f(x)\mid x\in A\}$，是”实际落到了哪里”的集合。恒有 $f(A)\subset B$，而且可以真包含于 $B$。

  这是本讲最容易被忽视、但后面判别满射时最关键的三分：陪域是承诺，值域是事实。承诺可以大于事实（有剩余的输出没被用到），也可以在换掉定义域/陪域后从”大”变”刚好”。

• 具体示例：设 $A=\{1,2,3,4\}$，$B=\{a,b\}$（这正是源文件里那个映射 $f:\{1,2,3,4\}\to\{a,b\}$ 的规模）。令 \(f(1)=a,\quad f(2)=b,\quad f(3)=a,\quad f(4)=b.\) 那么：定义域 $A=\{1,2,3,4\}$；陪域 $B=\{a,b\}$；值域 $f(A)=\{a,b\}=B$。 取 $C=\{1,2\}\subset A$，则 $f(C)=\{a,b\}$；取 $D=\{a\}\subset B$，则 $f^{-1}(D)=\{1,3\}$。 注意 $f^{-1}(D)$ 是一个集合，不是”把一个元素映回去”；这里原像有 2 个元素，正说明 $f$ 不是单射（见下面反例）。

• 反例（$f^{-1}$ 一般不是函数）：在上面这个例子里，”$f^{-1}(a)$”到底是什么？它既可以指 $f^{-1}(\{a\})=\{1,3\}$，也无法给出唯一的一个数。所以对非单射的 $f$，$f^{-1}$ 只能作为”集合到集合”的算子存在，不能当函数用。只有当 $f$ 是双射时，$f^{-1}$ 才升级为一个真正的函数 $B\to A$（源文件明确写了这一点）。这是初学者最常见的越界操作之一。

• 补充示例（用于看清”原像比像更好”）：$f:\mathbb{R}\to\mathbb{R}$，$f(x)=x^2$。则 $f([-1,1])=[0,1]$（像把两个点压成一个点，区间变短），而 $f^{-1}([0,1])=[-1,1]$；$f^{-1}(\{-1\})=\varnothing$（空集！原像可以空，像却永远不空——只要 $C\neq\varnothing$）。另外 $f^{-1}(\{4\})=\{-2,2\}$ 有两个元素，再次说明 $f$ 不是单射。

        f : A → B            （箭头图：定义域 A 在左，陪域 B 在右）

   A = {1,2,3,4}                 B = {a,b}
       1  ────────────────────────▶ a      值域 f(A) = {a,b}
       2  ────────────────────────▶ b      ← 恰好等于陪域 B
       3  ────────────────────────▶ a
       4  ────────────────────────▶ b
                                      这个 f 是满射；不是单射
                                      f⁻¹({a}) = {1,3} 有两个元素

定义 1：单射 (injective / one-to-one, 1-1)——源文件第 1 条

• 严格定义：设 $f:A\to B$。称 $f$ 是单射 (injective / one-to-one)，当且仅当 \(f(x_1)=f(x_2)\ \Longrightarrow\ x_1=x_2 .\) 等价地（取逆否命题）， \(x_1\neq x_2\ \Longrightarrow\ f(x_1)\neq f(x_2).\) 源文件写的就是”$f(x_1)=f(x_2)\Rightarrow x_1=x_2$”这个形式，并给它取别名 1-1。

• 直观解释（”它到底在说什么？”）：单射拒绝”撞车”。不同的输入必须去往不同的目的地。想象一场考试，每位学生（$A$ 的元素）被分配到一间教室（$B$ 的元素）：单射就是说没有两位学生被分到同一间教室。换句话说，每个教室最多只坐一个人。所以单射是”不浪费”的方向：$B$ 至少要跟 $A$ 一样大才装得下这种诚实的分法。

• 为什么需要这个条件？：只有当单射成立时，每个输出才唯一地指向一个输入，”反向追踪”才有意义。没有单射，”$\vert A\vert \le\vert B\vert $”就无法被定义成”存在单射”（见下面的基数记号），$f^{-1}$ 也无法成为函数。反过来，单射是可以被验证的：只需做代数化简 $f(x_1)=f(x_2)\Rightarrow\cdots\Rightarrow x_1=x_2$，不需要去枚举集合。

• 具体示例（含逐一验证）：

  (a) $f:\mathbb{R}\to\mathbb{R}$，$f(x)=2x$。 设 $f(x_1)=f(x_2)$，即 $2x_1=2x_2$。两边同除以 $2$（在 $\mathbb{R}$ 中 $2\neq 0$，除法合法）得 $x_1=x_2$。故 $f$ 单射。（依据：单射定义 + 实数乘法消去律。）

  (b) $f:\mathbb{R}\to\mathbb{R}$，$f(x)=x^2$。 取 $x_1=1$，$x_2=-1$。则 $x_1\neq x_2$ 但 $f(x_1)=1=f(x_2)$。故 $f$ 不是单射。反例一个就够。

  (c) $f:[0,\infty)\to[0,\infty)$，$f(x)=x^2$。 设 $x_1^2=x_2^2$ 且 $x_1,x_2\ge 0$。则 $(x_1-x_2)(x_1+x_2)=0$。由于 $x_1,x_2\ge0$，有 $x_1+x_2\ge0$；若 $x_1+x_2=0$ 则 $x_1=x_2=0$，结论已经成立；否则 $x_1+x_2>0$，由乘积为零得 $x_1-x_2=0$，即 $x_1=x_2$。故 $f$ 单射。（依据：因式分解 + 无零因子。） → 教学点：同一个”公式” $x^2$，定义在 $\mathbb{R}$ 上不是单射，限制在 $[0,\infty)$ 上却是单射。单射性依赖定义域，不是公式自带的属性。

  (d) 源文件 Example 13 第 1 条：$f:\mathbb{N}\to\{2n\mid n\in\mathbb{N}\}$，$f(n)=2n$。 设 $f(n)=f(m)$，即 $2n=2m$，两边除以 $2$ 得 $n=m$。故单射。

• 反例（展示条件不可省）：$f:\mathbb{R}\to\mathbb{R}$，$f(x)=\vert x\vert $。$f(-3)=3=f(3)$ 而 $-3\neq3$，不是单射。又 $f:\mathbb{Z}\to\mathbb{Z}$，$f(n)=n^2$：$f(-2)=4=f(2)$，不是单射。（注意：如果把陪域也换成 $\{n^2\mid n\in\mathbb{Z}\}$，公式不变，但集合之间的”指向”关系变了——这仍不改变 $f(-2)=f(2)$ 这一事实，所以仍不是单射。单射只跟定义域有关，与陪域无关，这是与满射最鲜明的对比。）

定义 2：满射 (surjective / onto)——源文件第 2 条

• 严格定义：设 $f:A\to B$。称 $f$ 是满射 (surjective / onto)，当且仅当 \(f(A)=B,\) 也就是（把”像等于陪域”展开成量化形式） \(\forall y\in B\ \ \exists x\in A\ \ \text{使得}\ f(x)=y .\) 源文件用的就是 $f(A)=B$ 这个写法。

• 直观解释（”它到底在说什么？”）：满射是说”$B$ 里没有一个元素被冷落”。回到教室类比：$B$ 中每一间教室都至少要坐进一位学生。所以满射是”不剩余”的方向：$B$ 不能比 $A$ 还大，否则总有教室空着。用射箭打比方：$B$ 中每个靶子都被至少一支箭射中，靶场上不存在从未中过的靶心。

• 为什么需要这个条件？：满射保证”输出侧被完全覆盖”，这是”配对”的另一半。只有单射，”配对”会缺人（$A$ 太小，很多 $y$ 找不到对应）；只有满射，会撞车（多个 $x$ 抢一个 $y$）。两者同时成立，才是无遗漏、无重叠的完美配对。

• 具体示例（含逐一验证）：

  (a) $f:\mathbb{R}\to\mathbb{R}$，$f(x)=2x$。 任取 $y\in\mathbb{R}$，需要找 $x$ 使 $2x=y$。取 $x=y/2\in\mathbb{R}$（$\mathbb{R}$ 对除法封闭），则 $f(x)=2\cdot(y/2)=y$。故 $f$ 满射。注意：这里我们从 $y$ 反解出 $x$，这是验证满射的标准动作。

  (b) $f:\mathbb{R}\to\mathbb{R}$，$f(x)=x^2$。 取 $y=-1\in\mathbb{R}$，则方程 $x^2=-1$ 在 $\mathbb{R}$ 中无解（实数的平方非负）。故 $f$ 不是满射。

  (c) $f:\mathbb{R}\to[0,\infty)$，$f(x)=x^2$。 任取 $y\in[0,\infty)$，由 $y\ge0$ 知 $\sqrt y$ 是实数，取 $x=\sqrt y$，则 $f(x)=y$。故 $f$ 满射。（依据：非负实数有平方根——这是实数的完备性/上确界性质的下游推论，本课程第 4 讲才正式建立；此处作为分析前的直观素材使用。）

  (d) 源文件 Example 13 第 1 条（续）：$f:\mathbb{N}\to\{2n\mid n\in\mathbb{N}\}$，$f(n)=2n$ 是满射。 证：任取 $m\in\{2n\mid n\in\mathbb{N}\}$。按这个集合的定义，”$m\in\{2n\mid n\in\mathbb{N}\}$”本身就意味着存在 $n\in\mathbb{N}$ 使 $m=2n=f(n)$。故满射。（依据：集合的构造式定义。）源文件用的正是这句话，注意这里不是”整数除以 2 得整数”——用集合的定义一句话解决，比反解更干净。

• 反例（展示条件不可省）：$f:\mathbb{Z}\to\mathbb{Z}$，$f(n)=2n$。它仍是单射，但不是满射：取 $y=1\in\mathbb{Z}$，方程 $2n=1$ 在整数中无解。这说明”$2$ 倍映射”的单射性在 $\mathbb{R}$、$\mathbb{N}$、$\mathbb{Z}$ 上都成立，而满射性却高度依赖陪域：陪域换成 $2\mathbb{Z}$ 或 $\mathbb{R}$ 就满，留在 $\mathbb{Z}$ 就不满。

• 教学点：定义域/陪域改变会改变满射性。 这是本讲最值得反复咀嚼的一点。

  • $f(x)=x^2$：$\mathbb{R}\to\mathbb{R}$ 不满；$\mathbb{R}\to[0,\infty)$ 满；$[0,\infty)\to\mathbb{R}$ 不满（值域 $=[0,\infty)\subsetneq\mathbb{R}$）。
  • $f(x)=2x$：$\mathbb{Z}\to\mathbb{Z}$ 不满；$\mathbb{Z}\to 2\mathbb{Z}$ 满（且单，是双射）；$\mathbb{R}\to\mathbb{R}$ 满。
  • 结论：“$f$ 是不是满射”是一个关于三元组 $(f,A,B)$ 的问题，不是关于公式的问题。 而单射只跟 $(f,A)$ 有关。

定义 3：双射 (bijective)——源文件第 3 条与逆函数

• 严格定义：$f:A\to B$ 是双射 (bijective)，当且仅当它既是单射又是满射。若 $f:A\to B$ 是双射，则存在逆函数 (inverse function) $f^{-1}:B\to A$，它把每个 $y\in B$ 指派到那个唯一的 $x\in A$ 使 $f(x)=y$。（源文件原话：assigns each $y\in B$ to the unique $x\in A$ such that $f(x)=y$。）此时 \(f\bigl(f^{-1}(x)\bigr)=x .\) （源文件写的是 $f(f^{-1}(x))=x$；这句话要在 $x\in B$ 的前提下读，即 $f\circ f^{-1}=\mathrm{id}_B$。对称地还有 $f^{-1}(f(x))=x$ 对 $x\in A$，即 $f^{-1}\circ f=\mathrm{id}_A$。）

• 直观解释（”它到底在说什么？”）：双射是”完美的舞伴配对”。每一个人恰好有一个舞伴，每一个舞伴也恰好被一个人牵着。因此配对表可以左右翻转阅读：$f$ 说”你该去找谁”，$f^{-1}$ 说”你是谁找来的”。这种成对关系是对称的——如果 $A$ 能和 $B$ 配对，$B$ 当然也能和 $A$ 配对（用 $f^{-1}$）。这就是”基数”能成为一个良定义概念的全部秘密。

• 为什么需要”既单又满”？：只有单射时，$B$ 里可能有没人对应的元素，$f^{-1}(y)$ 对那个 $y$ 无定义，逆函数造不出来；只有满射时，某个 $y$ 可能对应多个 $x$，”唯一”二字失效，$f^{-1}(y)$ 不是一个元素。两个条件缺一个，$f^{-1}$ 作为函数就不存在。

• 具体示例：
  • $f:\mathbb{R}\to\mathbb{R}$，$f(x)=2x$：既单又满，是双射，$f^{-1}(y)=y/2$。验算：$f(f^{-1}(y))=2\cdot(y/2)=y$ ✓，$f^{-1}(f(x))=(2x)/2=x$ ✓。
  • 源文件 Example 13：$f:\mathbb{N}\to\{2n\mid n\in\mathbb{N}\}$，$f(n)=2n$ 是双射（前两小节各证了一半）。它的逆是”把一个偶数除以 2”，$f^{-1}(m)=m/2$，结果一定是自然数。
  • 源文件给的”两个集合元素一样多”的最小例子：$A=\{1,2,3,4\}$ 与 $B=\{a,b\}$ 不可能有双射（因为 $4>2$，鸽笼原理：4 个输入挤进 2 个输出必有撞车）；而 $A=\{1,2\}$ 与 $B=\{a,b\}$ 之间可以配对 $1\mapsto a$，$2\mapsto b$，是双射。
• 反例：$f:\mathbb{R}\to\mathbb{R}$，$f(x)=x^3-x$。它是满射（三次多项式值域为 $\mathbb{R}$）但不是单射（$f(-1)=0=f(0)=f(1)$），所以不是双射，$f^{-1}$ 不是函数：$f^{-1}(0)$ 应当是谁？$-1$、$0$、$1$ 三个候选，无法”唯一”。补一句警惕：$f$ 不是双射并不等于“$f^{-1}$ 不存在”——作为”集合的原像算子” $f^{-1}(\{0\})=\{-1,0,1\}$ 永远是合法的。不存在的只是”把单个元素映回单个元素的函数”。

定义 4（本讲最重要的定义）：基数 (Cardinality)——源文件 Question 10 与 Definition 11

• 严格定义（Definition 11 (Cardinality)）：设 $A,B$ 是集合。我们说 $A$ 与 $B$ 有相同的基数 (same cardinality)，当且仅当存在一个双射 $f:A\to B$。源文件紧接着给出记号体系：
  1. $\vert A\vert =\vert B\vert $，若 $A$ 与 $B$ 有相同的基数。
  2. $\vert A\vert =n$，若 $\vert A\vert =\vert \{1,\dots,n\}\vert $；此时称 $A$ 是有限的 (finite)。
  3. $\vert A\vert \le\vert B\vert $，若存在一个单射 $f:A\to B$。
  4. $\vert A\vert <\vert B\vert $，若 $\vert A\vert \le\vert B\vert $ 但 $\vert A\vert \neq\vert B\vert $。
• 直观解释（”它到底在说什么？”）：这是整讲的灵魂，值得用最大的篇幅讲清楚。康托的天才之处在于：他把”一样多”从一个”计数结果”改造成了一个”配对能力”。
  • 对有限集，”数元素个数”之所以可行，本质上就是因为在数到 $n$ 的时候，你其实悄悄建立了一个双射：第一根手指对应第一个元素，第二根手指对应第二个……数到”没得数了”，你就得到了 $\vert \{1,\dots,n\}\vert =\vert A\vert $。所以”数数”只是”建立双射”的一个特例——基数定义不是放弃计数，而是把计数的内核抽出来。
  • 对无限集，”数元素个数”立刻失效：你不能说”数完了，一共 $\infty$ 个”，因为 $\infty$ 不是一个数，而且不同无限集之间那种”多少”的差别会被 $\infty$ 这个符号全部抹平。更糟的是”个数”本身在无限情形下没有操作意义——你永远停不下来。
  • 于是康托说：别数了，配对。”配对成功”这件事是可以在有限步骤内被证明的（写下一个公式、验证单射与满射），它不依赖任何”无穷次操作”。这就是为什么”大小”必须用双射来定义，而不能用数数来定义。

• 为什么需要这个定义？它解决什么问题？：它把”大小比较”变成了一个存在性问题：$\vert A\vert =\vert B\vert $ 等价于”$\exists f$，$f$ 是双射”。数学上，”存在某个对象”比”执行某个无穷过程”可靠得多。这也解释了为什么本讲前面三分之一的篇幅都在讲函数——函数语言就是为基数准备的工具箱。

• Hilbert 旅馆式的直观类比（补充/直观理解，非源文件内容）：设想一家旅馆有可数无穷多个房间，编号 $1,2,3,\dots$，且已经客满。此时来了一位新客人。前台说：”请 1 号房的客人搬到 2 号，2 号搬到 3 号，……，$n$ 号搬到 $n+1$ 号。”于是所有老客人都还有房间，1 号房空出来给新客人。“客满”的旅馆居然还能再住人，这在有限世界里是荒谬的，在无限世界里恰恰是”$\mathbb{N}$ 与 $\mathbb{N}\cup\{\text{新客人}\}$ 等势”的物理版：映射 $n\mapsto n+1$ 是 $\mathbb{N}\to\{2,3,4,\dots\}$ 的双射，把新客人放进 1 号房就补全了双射。更进一步：如果来了无穷多位新客人（编号 $k=1,2,3,\dots$），就让老客人 $n$ 搬到 $2n$ 号房，新客人 $k$ 住 $2k-1$ 号房——这正是本讲下面 Example 13 的奇数/偶数分解。“无限集可以和自己的真子集一样大” 是理解本讲的钥匙。

• 具体示例（源文件 Example 13 的三条结论，逐条走一遍）：

  例 1：$\vert \{2n\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $（偶数与自然数一样多）。 证：定义 $f:\mathbb{N}\to\{2n\mid n\in\mathbb{N}\}$ 为 $f(n)=2n$。

  • 单射：设 $f(n)=f(m)$，即 $2n=2m$，两边除以 $2$ 得 $n=m$。（依据：实数乘法消去律。）
  • 满射：任取 $m\in\{2n\mid n\in\mathbb{N}\}$，由该集合的定义，存在 $n\in\mathbb{N}$ 使 $m=2n=f(n)$。（依据：集合构造式定义。） 既单又满，故 $f$ 是双射，从而 $\vert \{2n\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $。∎

  例 2：$\vert \{2n-1\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $（奇数与自然数一样多）。 源文件说”The second statement can be proven similarly”（第二条可类似证明），我们把它完整写出来，不省步骤。 证：定义 $g:\mathbb{N}\to\{2n-1\mid n\in\mathbb{N}\}$ 为 $g(n)=2n-1$。

  • 单射：设 $g(n)=g(m)$，即 $2n-1=2m-1$。两边加 $1$ 得 $2n=2m$，再除以 $2$ 得 $n=m$。（依据：实数加法消去律与乘法消去律。）
  • 满射：任取 $k\in\{2n-1\mid n\in\mathbb{N}\}$。由该集合的定义，存在 $n\in\mathbb{N}$ 使 $k=2n-1=g(n)$。（依据：集合构造式定义。） 故 $g$ 是双射，$\vert \{2n-1\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $。∎

  例 3：$\vert \{x\in\mathbb{Q}\mid x>0\}\vert =\vert \mathbb{N}\vert $（正有理数与自然数一样多）。 源文件把这条留作习题（”This is left as an exercise to the reader in Assignment 1”），并在 Remark 里用费曼的俏皮话总结前两条：”There are twice as many numbers as numbers.”（”数的个数是数的个数的两倍。”）——一句在有限世界自相矛盾、在无限世界字字属实的话。

  这条我们给出完整的证明思路（源文件未给证明，此处标注为补充/完整化）：

  (i) 思路 A：蛇形枚举（对角线枚举，diagonal / snake enumeration）。 正有理数都可以写成 $m/n$（$m,n\in\mathbb{N}$），所以 $\{x\in\mathbb{Q}:x>0\}$ 的每个元素都至少对应一对 $(m,n)\in\mathbb{N}\times\mathbb{N}$；而 $\mathbb{N}\times\mathbb{N}$ 可以被”按 $m+n$ 分组”排成一列： \((1,1);\ (1,2),(2,1);\ (1,3),(2,2),(3,1);\ (1,4),(2,3),(3,2),(4,1);\ \dots\) 每一组 $m+n=k$ 里有 $k-1$ 个元素，组与组之间前后衔接，于是 $\mathbb{N}\times\mathbb{N}$ 被排成一个无穷序列，从而与 $\mathbb{N}$ 建立双射（这就是教材 Example 0.3.31 的做法）。再把这个序列里对应同一个有理数的重复项（如 $2/2=1/1$）跳过不列，就得到正有理数的一个无穷序列。因此正有理数可以”排成一列”，即 $\vert \{x\in\mathbb{Q}:x>0\}\vert =\vert \mathbb{N}\vert $。

  (ii) 唯一素因子分解法（Assignment 1 第 6 题的方法）。 作业给的是更强、更技术的版本：用算术基本定理 (fundamental theorem of arithmetic, 唯一素因子分解) 构造一个 $f:\{q\in\mathbb{Q}:q>0\}\to\mathbb{N}$ 的显式双射。设 $q>0$，$q\neq1$：

  • 若 $q\in\mathbb{N}\setminus\{1\}$，写成 $q=p_1^{r_1}p_2^{r_2}\cdots p_N^{r_N}$（$p_1<p_2<\dots<p_N$ 为素数），定义 \(f(q)=p_1^{2r_1}p_2^{2r_2}\cdots p_N^{2r_N};\)
  • 若 $q\notin\mathbb{N}$，写成 $q=\dfrac{p_1^{r_1}\cdots p_N^{r_N}}{q_1^{s_1}\cdots q_M^{s_M}}$（分子分母的素因子互不相同，且都已约分），定义 \(f(q)=p_1^{2r_1}\cdots p_N^{2r_N}\cdot q_1^{2s_1-1}\cdots q_M^{2s_M-1};\)
  • 另规定 $f(1)=1$。 这个构造把”分子上的素因子配偶数指数、分母上的素因子配奇数指数”分开编码，于是 $f$ 是双射（单射靠唯一分解；满射靠对任一 $n$ 的素因子分解按指数奇偶回读）。我们用它算两个具体值作为验算：
  • $q=\dfrac{4}{15}=\dfrac{2^2}{3^1\cdot5^1}$，属于 $q\notin\mathbb{N}$ 的情形。$p_1=2,r_1=2$；$q_1=3,s_1=1$；$q_2=5,s_2=1$。于是 \(f\!\left(\frac{4}{15}\right)=2^{2\cdot2}\cdot 3^{2\cdot1-1}\cdot 5^{2\cdot1-1}=2^4\cdot 3^1\cdot 5^1=16\cdot 15=240 .\)
  • 反过来，求 $q$ 使 $f(q)=108$。分解 $108=2^2\cdot 3^3$。偶数指数 $2=2\cdot1$ 说明素因子 $2$ 在分子上，指数 $1$；奇数指数 $3=2\cdot2-1$ 说明素因子 $3$ 在分母上，指数 $2$。于是 \(q=\frac{2^1}{3^2}=\frac{2}{9},\qquad\text{验算：} f\!\left(\frac29\right)=2^{2\cdot1}\cdot 3^{2\cdot2-1}=2^2\cdot 3^3=108\ \checkmark\) （这两个数值已用脚本按上述公式独立核算，与作业要求的一致。）

• 反例（”一样多”并不意味着”包含”）：$2\mathbb{N}=\{2,4,6,\dots\}\subsetneq\mathbb{N}$，但 $\vert 2\mathbb{N}\vert =\vert \mathbb{N}\vert $。也就是说，真子集可以和外层集合同样大。这在有限世界里绝无可能（有限集的真子集一定更小），因此任何”因为 $A\subsetneq B$ 所以 $\vert A\vert <\vert B\vert $”的推理在无限情形下都是错误的。这个反例是理解本讲的试金石；MIT 讲义在 §0.3 里也特别点出：”一个集合是无限的，当且仅当它与自己的某个真子集一一对应”（教材 Remark，本课程第 6 讲会进一步展开）。

• 具体示例（$\mathbb{Z}$ 与 $\mathbb{N}$ 一样多，补充）：$\mathbb{Z}$ 在数轴上向两端无限延伸，看起来”比 $\mathbb{N}$ 多一倍”，但 \(f(n)=\begin{cases}-\dfrac{n-1}{2}, & n\ \text{为奇数},\\[2mm] \dfrac{n}{2}, & n\ \text{为偶数}\end{cases}\) 是 $\mathbb{N}\to\mathbb{Z}$ 的双射：它在 $\mathbb{N}=1,2,3,4,5,6,7,\dots$ 上依次取值 \(0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ \dots\) 恰好是 $\mathbb{Z}$ 的一个不重不漏的列举。于是 $\vert \mathbb{Z}\vert =\vert \mathbb{N}\vert $。（这条结论源文件没有，属于补充；完整验证见本讲 Q1。）同样的手法立刻推广到 $\mathbb{Q}$：把有理数”排成一列”而不是”画在数轴上”，就得到 $\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $。

   N 与偶数集 2N 的一一对应表（双射 n ↦ 2n）

   N  :  1   2   3   4   5   6   7   8  ...
         │   │   │   │   │   │   │   │
         ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼
   2N :  2   4   6   8  10  12  14  16  ...

   左边没有剩余（单射），右边没有剩余（满射）
   ⇒ |2N| = |N|，尽管 2N ⊊ N  （"数的个数是数的个数的两倍"）

定义 4 的补充：”等势”是一个等价关系（为什么”基数”可以被当作一个对象来谈论）

• 补充陈述：把 “$A\sim B\iff\vert A\vert =\vert B\vert $” 看成集合之间的关系。它是一个等价关系 (equivalence relation)，即满足：
  1. 自反性 (reflexivity)：$\vert A\vert =\vert A\vert $；
  2. 对称性 (symmetry)：$\vert A\vert =\vert B\vert \Rightarrow\vert B\vert =\vert A\vert $；
  3. 传递性 (transitivity)：$\vert A\vert =\vert B\vert $ 且 $\vert B\vert =\vert C\vert $ $\Rightarrow$ $\vert A\vert =\vert C\vert $。
• 证明（补充；教材中这一段紧随 same cardinality 的定义）：
  1. 取恒等映射 $\mathrm{id}_A:A\to A$，$x\mapsto x$。它对每个 $x$ 送出唯一的值（良定义）；单射：设 $x_1=x_2$，这已经就是结论 $x_1=x_2$（这里不需要任何推理，因为假设与结论是同一个命题）；满射：任取 $y\in A$，取 $x=y\in A$，则 $\mathrm{id}_A(x)=y$。故 $\mathrm{id}_A$ 是双射，$\vert A\vert =\vert A\vert $。
  2. 设 $f:A\to B$ 是双射，即逆函数 $f^{-1}:B\to A$ 存在。由 Definition 11 前的讨论（源文件：”$f^{-1}:B\to A$ assigns each $y\in B$ to the unique $x\in A$ with $f(x)=y$”），$f^{-1}$ 也是双射：单射是因为 $f^{-1}(y_1)=f^{-1}(y_2)=:x$ 时对两边施加 $f$ 得 $y_1=y_2$；满射是因为对任意 $x\in A$，取 $y=f(x)$ 就有 $f^{-1}(y)=x$。于是 $\vert B\vert =\vert A\vert $。
  3. 设 $f:A\to B$、$g:B\to C$ 是双射。定义复合 (composition) $(g\circ f)(x):=g(f(x))$（教材 Definition 0.3.18）。$g\circ f$ 是单射：若 $g(f(x_1))=g(f(x_2))$，由 $g$ 单射得 $f(x_1)=f(x_2)$，再由 $f$ 单射得 $x_1=x_2$。$g\circ f$ 是满射：任取 $z\in C$，由 $g$ 满射存在 $y\in B$ 使 $g(y)=z$，再由 $f$ 满射存在 $x\in A$ 使 $f(x)=y$，于是 $(g\circ f)(x)=g(y)=z$。故 $g\circ f$ 是双射，$\vert A\vert =\vert C\vert $。
• 为什么这件事重要：正因为等势是等价关系，”$\vert A\vert $”才能被理解成”$A$ 所属的那个等价类”，才能写出 $\vert A\vert =\vert B\vert $、$\vert A\vert <\vert B\vert $ 而不产生歧义；也正因为对称性成立，Hilbert 旅馆式的配对才可以双向阅读。反过来，如果 $\vert A\vert =\vert B\vert $ 的定义修改成”存在满射”（而不是双射），自反性与传递性还在，但对称性会崩掉（$\mathbb{N}\to\{0\}$ 有满射而反向没有），”大小”立刻不再是等价关系。
• 反例（错误定义会怎样）：若把”$\vert A\vert \le\vert B\vert $”错定义成”存在满射 $f:A\to B$”，大小比较就会整体颠倒。例如 $x\mapsto\lfloor \vert x\vert \rfloor$ 是 $\mathbb{R}\to\mathbb{N}$ 的满射（每个自然数 $n$ 都被 $x=n$ 取到），按这个错误定义就会得出 $\vert \mathbb{R}\vert \le\vert \mathbb{N}\vert $——与我们马上要证的事实完全相反。“用单射定义 $\le$、用双射定义 $=$”这一组选择不是随意的，它是让整个理论自洽的唯一自然选择：单射说的是”$A$ 塞得进 $B$”，满射说的是”$A$ 能盖住 $B$”，只有前者才配称”$A$ 不大于 $B$”。

定义 5：可数 (countable)、可数无限 (countably infinite)、不可数 (uncountable)

• 严格定义（源文件紧接 Theorem 12 的文字，教材中为 Definition 0.3.29）：
  1. 若 $\vert A\vert =\vert \mathbb{N}\vert $，称 $A$ 是可数无限的 (countably infinite)。
  2. 若 $A$ 是有限的或可数无限的，称 $A$ 是可数的 (countable)。
  3. 否则（即 $A$ 既不是有限集，也不与 $\mathbb{N}$ 等势），称 $A$ 是不可数的 (uncountable)。
• 直观解释（”它到底在说什么？”）：可数 = “能够排成一列”。想象一个无穷长的书架，第一格、第二格、第三格……。如果 $A$ 的元素可以被不重不漏地放进这些格子里，$A$ 就是可数的（放进 $n$ 格就是”该元素对应自然数 $n$”）。有限集可以硬塞进前 $n$ 格；可数无限集则把格子用满。所以：
  • 可数 = 能列出清单（listable）；
  • 不可数 = 无论怎么列都会漏掉一些（unlistable）。 这个”清单”直觉极其有用：考试里要证某集合可数，几乎总是”把它排成一列”或”给出到 $\mathbb{N}$ 的双射/单射”。

• 为什么把有限集也算作可数？：因为”无限”和”可数”是两个独立的维度；把有限集并进来，使得”可数”在取子集、取并集、取笛卡尔积等操作下封闭、叙述简洁（否则每一条定理都要写”有限或可数无限”，非常啰嗦）。教材特意提醒：”$A$ 与 $\varnothing$ 等势当且仅当 $A=\varnothing$”，所以 $\vert \varnothing\vert =0$、$\varnothing$ 也是有限集，也是可数的。

• 具体示例：
  • $\mathbb{N}$ 本身：$\vert A\vert =\vert \mathbb{N}\vert $ 取 $A=\mathbb{N}$，恒等映射 $\mathrm{id}$ 是双射，所以 $\mathbb{N}$ 可数无限。
  • $\{1,\dots,2026\}$：有限，可数。
  • $2\mathbb{N}$、$2\mathbb{N}-1$：由 Example 13 与 $\mathbb{N}$ 等势，可数无限。
  • $\mathbb{Z}$：补充结论，$\vert \mathbb{Z}\vert =\vert \mathbb{N}\vert $。显式双射为 \(f(n)=\begin{cases}\dfrac{n}{2}, & n\ \text{为偶数},\\[2mm] -\dfrac{n-1}{2}, & n\ \text{为奇数}.\end{cases}\) 即 $f(1)=0,\ f(2)=1,\ f(3)=-1,\ f(4)=2,\ f(5)=-2,\ f(6)=3,\ f(7)=-3,\dots$，正是”$0,1,-1,2,-2,3,-3,\dots$”的蛇形列表。（已用脚本逐项核算前 10 项。）所以 $\mathbb{Z}$ 可数无限。
  • $\mathbb{Q}$：补充结论（源文件 Example 13 只对正有理数断言，Assignment 1 要求证明；教材 Example 0.3.32 给出”$\mathbb{Q}$ 可数”）：把 $\mathbb{Q}$ 排成 $0,\ \frac11,\ -\frac11,\ \frac12,\ -\frac12,\ \frac13,\ -\frac13,\dots$ 并跳过重复项，即可数。
  • $\mathbb{R}$：不可数（本讲不证；第 6 讲用区间套 + 十进制展开证明 $(0,1]$ 不可数，进而 $\mathbb{R}$ 不可数）。$\wp(\mathbb{N})$：不可数（第 3 讲 Cantor 定理）。

• 反例（”可数”不等于”有限”）：$\mathbb{N}$ 可数但无限；”$\mathbb{Q}$ 可数”也常被误读成”$\mathbb{Q}$ 很小”。可数只说明”能列表”，与”在数轴上的密度”无关——$\mathbb{Q}$ 在 $\mathbb{R}$ 中稠密（第 5 讲），却仍可数。稠密 ≠ 不可数，这是后面 Midterm 与 Assignment 3 要反复澄清的点。

• $\mathbb{Q}$ 的蛇形枚举表（ASCII，补充示意）：下面这张表把 $\mathbb{N}\times\mathbb{N}$ 按 $m+n=k$ 逐条对角线排列。沿箭头读就是”列表顺序”；把每条对角线上编码相同有理数的格子划掉，就得到正有理数的列表。

   m\n    1     2     3     4     5   ...      （格中写的是 m/n 的"坐标"，即 (m,n)）
    1 │  (1,1) (1,2) (1,3) (1,4) (1,5)
      │    ↙     ↙     ↙     ↙
    2 │  (2,1) (2,2) (2,3) (2,4) (2,5)
      │    ↙     ↙     ↙
    3 │  (3,1) (3,2) (3,3) (3,4) (3,5)
      │    ↙     ↙
    4 │  (4,1) (4,2) (4,3) (4,4) (4,5)
      │    ↙
    5 │  (5,1) (5,2) (5,3) (5,4) (5,5)
    ...

   按对角线（m+n = k）读出的顺序：
     k=2: (1,1)                              共 1 个   → 编号 1
     k=3: (1,2) (2,1)                        共 2 个   → 编号 2,3
     k=4: (1,3) (2,2) (3,1)                  共 3 个   → 编号 4,5,6
     k=5: (1,4) (2,3) (3,2) (4,1)            共 4 个   → 编号 7,8,9,10
     k=6: (1,5) (2,4) (3,3) (4,2) (5,1)      共 5 个   → 编号 11..15
    ...
   第 k 条对角线上有 k-1 个格子；数完前 j 条对角线共 1+2+...+j = j(j+1)/2 个格子。
   ⇒ 每个 (m,n) 都在有限步内被读到：没有格子被漏掉。
   ⇒ 去掉重复编码（如 (2,2) 与 (1,1) 都是有理数 1）后，正有理数排成一列。

这张表对应的显式配对函数（补充）是 \(\varphi(m,n)=\frac{(m+n-2)(m+n-1)}{2}+m,\) 它给出 $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 的双射。逐项验算：$\varphi(1,1)=1$，$\varphi(1,2)=2$，$\varphi(2,1)=3$，$\varphi(1,3)=4$，$\varphi(2,2)=5$，$\varphi(3,1)=6$，$\varphi(1,4)=7$，$\varphi(3,5)=24$，与上表编号完全一致（已用脚本在 $7\times7$ 的方格上验证：49 个格子的 $\varphi$ 值互不相同）。

定义 6（比较记号的严谨性）：$\vert A\vert \le\vert B\vert $ 与 $\vert A\vert <\vert B\vert $；Cantor–Schröder–Bernstein 定理

• 严格定义（源文件 Definition 11 第 3、4 条）： \(\vert A\vert \le\vert B\vert \ \iff\ \text{存在单射}\ f:A\to B .\) \(\vert A\vert <\vert B\vert \ \iff\ \vert A\vert \le\vert B\vert \ \text{且}\ \vert A\vert \neq\vert B\vert .\) Theorem 12 (Cantor–Schröder–Bernstein)（源文件给出了这条定理，编号为 12）： \(\text{若}\ \vert A\vert \le\vert B\vert \ \text{且}\ \vert B\vert \le\vert A\vert ,\ \text{则}\ \vert A\vert =\vert B\vert .\)

• 直观解释（”它到底在说什么？”）：Theorem 12 说的是”大小比较满足反对称性”。注意它的非平凡性：假设只给了两个单射 $f:A\to B$ 与 $g:B\to A$，我们并没有拿到一个双射！定理断言：双射一定存在（哪怕它和 $f,g$ 毫无关系，哪怕要费很大力气才能构造出来）。这就是所谓的”两个无限集互相塞得进对方，就能完美配对”。
  • 用 Hilbert 旅馆的画面：如果旅馆 $B$ 的房间能把我 $A$ 的客人全安排下（单射 $A\to B$），同时我的旅馆 $A$ 也能把 $B$ 的客人全安排下（单射 $B\to A$），那么两边的客人数目（在无限的意义下）一样多——即使这两种安排各自都可能会空出一些房间。

• 为什么需要这个条件（这条定理为什么重要）？：因为它把”证明 $\vert A\vert =\vert B\vert $”的工作量减半并降级：原本要造一个双射（既单又满，两件事），现在只要造两个单射（只有一件事，做两遍）。实际上，$\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $ 的最省力证明就是：$\mathbb{N}\subset\mathbb{Q}$ 给出单射 $\mathbb{N}\to\mathbb{Q}$（恒等映射），蛇形枚举给出单射 $\mathbb{Q}\to\mathbb{N}$（把 $m/n$ 送到它的编号），两条一合，Theorem 12 直接给出 $\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $，不必再费力去掉重复项、证明满射。这是本定理最典型的用法。

• 【定理的证明】：注意，源文件只陈述了 Theorem 12，没有给出证明（教材 Lebl 也明确写”We state without proof”）。因此下面标注为补充（超出本讲范围，仅作参考）：
  • 思路（”来回追踪法”/back-and-forth，也叫 Cantor–Bernstein 的经典构造）：设 $f:A\to B$、$g:B\to A$ 都是单射。把 $A$ 中元素想象成”会被 $g$ 抢走”的对象。定义 \(A_0=A\setminus g(B),\qquad A_{n+1}=g\bigl(f(A_n)\bigr)\ (n\ge0),\) 令 $A_\infty=\displaystyle\bigcup_{n\ge0}A_n$。这些 $A_n$ 两两不交（可用归纳法验证）。现在定义 \(h(x)=\begin{cases}f(x), & x\in A_\infty,\\ g^{-1}(x), & x\in A\setminus A_\infty .\end{cases}\) 可以证明 $h:A\to B$ 是双射：对 $x\in A\setminus A_\infty$，必有 $x\in g(B)$（否则 $x\in A_0\subset A_\infty$，矛盾），所以 $g^{-1}(x)$ 合法；单射性来自 $f,g$ 各自单射且两段的像集恰好把 $B$ 分成互不相交的两块；满射性在于 $B\setminus f(A_\infty)=g^{-1}(A\setminus A_\infty)$。
  • 本讲的处理：记住 Theorem 12 的陈述与它的典型用法即可；它的证明（尤其上面这段”来回追踪”）属于进阶内容，本课程后续不再依赖其细节。
• 反例/注意事项（$\vert A\vert \le\vert B\vert $ 不能只用”看起来更小”来判定）：$2\mathbb{N}\subsetneq\mathbb{N}$，但 $\vert 2\mathbb{N}\vert \le\vert \mathbb{N}\vert $ 与 $\vert \mathbb{N}\vert \le\vert 2\mathbb{N}\vert $ 同时成立（后者由 $n\mapsto 2n$ 的单射给出），所以 $\vert 2\mathbb{N}\vert =\vert \mathbb{N}\vert $。若谁”凭直觉”写下 $\vert 2\mathbb{N}\vert <\vert \mathbb{N}\vert $，他就把有限世界的经验错误地搬到了无限世界——这正是本讲要根除的头号误区。

本讲定义速查卡（对照源文件编号，便于复习自测）

定理与完整证明（核心）

Theorem 12 (Cantor–Schröder–Bernstein)（源文件编号 Theorem 12）

• 定理陈述： \(\forall\ \text{集合}\ A,B:\quad \bigl(\vert A\vert \le\vert B\vert \ \wedge\ \vert B\vert \le\vert A\vert \bigr)\ \Longrightarrow\ \vert A\vert =\vert B\vert .\) 其中 $\vert A\vert \le\vert B\vert $ 按 Definition 11 第 3 条理解为”存在单射 $f:A\to B$”，$\vert A\vert =\vert B\vert $ 按 Definition 11 理解为”存在双射 $A\to B$”。量词顺序必须写对：是”$\exists$ 单射 $f$”与”$\exists$ 单射 $g$”两个假设，推出”$\exists$ 双射 $h$”。
• 证明策略：源文件未给证明（只陈述）。本节的证明标注为”补充”，目的是让你理解它为什么可信、以及它将如何被使用。策略是构造法 + 分块思想：把 $A$ 切成两块（”应该用 $f$ 处理的”与”应该用 $g^{-1}$ 处理的”），在每一块上定义 $h$ 的不同分支，再分别验证单射与满射。
• 逐步推导（补充，仅作参考）：设 $f:A\to B$、$g:B\to A$ 都是单射。
  1. 令 $A_0:=A\setminus g(B)$。（依据：定义。$A_0$ 是”$A$ 中不会被 $g$ 覆盖到”的元素。注意 $g(B)\subset A$。）
  2. 对 $n\ge0$ 归纳定义 $A_{n+1}:=g(f(A_n))$。（依据：定义；$f(A_n)\subset B$，故 $g(f(A_n))\subset A$，定义合法。）
  3. 断言：诸 $A_n$ 两两不交。 证明（归纳）：若 $x\in A_m\cap A_{m^{\prime}}$ 且 $m<m^{\prime}$，反复用 $g^{-1}$（注意 $g$ 单射，所以在像集上 $g^{-1}$ 合法）可得 $x\in A_{m^{\prime}-m}\cap A_0$ 的对应关系；而 $A_0\cap g(B)=\varnothing$ 与 $A_{m^{\prime}-m}\subset g(B)$（当 $m^{\prime}-m\ge1$ 时，因为 $A_{m^{\prime}-m}=g(f(A_{m^{\prime}-m-1}))\subset g(B)$）矛盾。（依据：$g$ 单射 + $A_0$ 的定义。）
  4. 令 $A_\infty:=\bigcup_{n\ge0}A_n$，并定义 \(h(x):=\begin{cases}f(x), & x\in A_\infty,\\ g^{-1}(x), & x\in A\setminus A_\infty.\end{cases}\) $h$ 定义合法性的依据：若 $x\notin A_\infty$，则特别地 $x\notin A_0=A\setminus g(B)$，即 $x\in g(B)$，故 $g^{-1}(x)$ 存在且唯一（唯一性来自 $g$ 单射）。
  5. $h$ 是单射：设 $h(x)=h(y)$。分情形。(a) $x,y\in A_\infty$：则 $f(x)=f(y)$，由 $f$ 单射得 $x=y$。(b) $x,y\notin A_\infty$：则 $g^{-1}(x)=g^{-1}(y)$，两边施加 $g$ 得 $x=y$。(c) $x\in A_\infty$，$y\notin A_\infty$：则 $f(x)=g^{-1}(y)$，两边施加 $g$ 得 $g(f(x))=y$；而 $x\in A_n$ 对某 $n$（由 $A_\infty$ 的定义），于是 $y=g(f(x))\in g(f(A_n))=A_{n+1}\subset A_\infty$，与 $y\notin A_\infty$ 矛盾。故 (c) 不可能发生。（依据：$A_\infty$ 的定义、各分支、$f,g$ 单射。）
  6. $h$ 是满射：任取 $y\in B$。若 $g(y)\in A_\infty$，则存在 $n$ 使 $g(y)\in A_n$，于是由 $A_{n+1}=g(f(A_n))$ 与 $g$ 单射得 $y=f(x)$ 对某个 $x\in A_n\subset A_\infty$，即 $y=h(x)$。若 $g(y)\notin A_\infty$，取 $x=g(y)\in A\setminus A_\infty$，则 $h(x)=g^{-1}(g(y))=y$。（依据：定义 + $g$ 单射。）
  7. 由 5、6，$h:A\to B$ 是双射，故 $\vert A\vert =\vert B\vert $。∎
• 【证明机制解说】：核心的”灵光一现”是认识到 $A$ 里有些元素是”被 $g$ 覆盖到的”，有些不是；而”被覆盖”这件事会像多米诺骨牌一样沿着 $f,g$ 来回传播（$a\mapsto f(a)\mapsto g(f(a))\mapsto\cdots$）。把这条链条的起点集合 $A\setminus g(B)$ 以及它反复推送出的所有元素收进 $A_\infty$，剩下的元素就恰好是”链条回不到起点”的那批。对前者用 $f$（因为链条的走向本来就是 $f$），对后者用 $g^{-1}$（因为它们都是某个 $g(y)$），两块拼起来就成了双射。如果你自己想发明这个证明，可以先试着问：”如果 $g$ 是满射我立刻就用 $g^{-1}$ 了；它不满，那些 $g$ 覆盖不到的 $A$ 元素怎么办？”——答案就是：把它们交给 $f$，再看看 $f$ 的像被 $g$ 推回 $A$ 时会不会又落进”覆盖不到”的区域，如此往复；最终你自然会切出 $A_\infty$。
• 【证明技巧总结】：
  1. 分块构造（piecewise construction）：把定义域切成两块，在每块上用不同的现成映射，最后验证拼接处不冲突。这是”有单射但缺满射”时的标准补救手法。
  2. 迭代像链（orbit / chain 技巧）：$A_{n+1}=g(f(A_n))$ 这种”来回推送”的模式在集合论、泛函分析（如 Schauder 不动点）中反复出现。
  3. 用单射做”半可逆”：单射 $g$ 在像集 $g(B)$ 上可以定义真的逆 $g^{-1}$；一旦发现自己需要逆，先检查”我是不是只在像集上用它”。

命题（Example 13 第 1 条）：$\vert \{2n\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $

• 定理陈述：$\bigl\vert \{2n\mid n\in\mathbb{N}\}\bigr\vert =\vert \mathbb{N}\vert $，即偶数自然数集与 $\mathbb{N}$ 之间存在双射。
• 证明策略：直接构造 $f(n)=2n$，然后分别验证单射与满射（这是证明”$\vert A\vert =\vert B\vert $”的标准模板：先造候选，再两两验证）。源文件的原证明就是这两步。
• 逐步推导（完全按源文件的论证展开，不省任何一步）：
  1. 定义 $f:\mathbb{N}\to\{2n\mid n\in\mathbb{N}\}$ 为 $f(n):=2n$。（依据：定义。注意陪域恰好取成值域，后面验证满射时会省力。）
  2. 验证 $f$ 良定义：对每个 $n\in\mathbb{N}$，$2n$ 是自然数（依据：$\mathbb{N}$ 对乘法封闭，$2,n\in\mathbb{N}$），且 $2n$ 是偶数，故按陪域的构造式定义 $2n\in\{2n\mid n\in\mathbb{N}\}$。✓
  3. 验证单射：设 $n,m\in\mathbb{N}$ 且 $f(n)=f(m)$，即 $2n=2m$。两边同时乘以 $1/2$（实数乘法消去律，$2\neq0$）得 $n=m$。（依据：单射定义 + 乘法消去律。）故 $f$ 是单射。
  4. 验证满射：任取 $m\in\{2n\mid n\in\mathbb{N}\}$。由集合构造式，存在 $n\in\mathbb{N}$ 使得 $m=2n$，于是 $m=f(n)$，其中 $n\in\mathbb{N}$ 正是定义域中的元素。（依据：满射定义 $f(\mathbb{N})=B$。）
  5. 由 3、4，$f$ 是双射；由 Definition 11，$\vert \{2n\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $。∎
• 【证明机制解说】：这里有两个”看起来什么都没做”却至关重要的细节。
  • 第一，陪域选得好：如果把陪域写成 $\mathbb{N}$ 而不是 $\{2n\mid n\in\mathbb{N}\}$，那么第 4 步就会失败——任取 $m\in\mathbb{N}$ 时，$m=3$ 就找不到 $n$。同一个公式，换个陪域，结论从”双射”变成”只有单射”。
  • 第二，满射的验证用了”集合的定义”而不是”算术”：源文件不写”因为偶数可以被 2 整除”，而写”若 $m\in\{2n\mid n\in\mathbb{N}\}$，则存在 $n$ 使 $m=2n$”。这两种说法等价，但后者的逻辑结构更清晰：$m$ 属于这个集合这件事本身就是“存在 $n$”的同义反复。把它写成量化语句，你就不会漏掉”$n$ 必须落在定义域 $\mathbb{N}$ 里”这一句。如果你自己想出这个证明：先问”我能把每个偶数唯一地写回一个自然数吗？”——能，除以 2——那就说明存在双射，公式立刻浮现。
• 【证明技巧总结】：
  1. 证明 $\vert A\vert =\vert B\vert $ 的三步模板：① 写下一个候选映射 $f$；② 验单射（假设 $f(x_1)=f(x_2)$，推到 $x_1=x_2$）；③ 验满射（任取 $y\in B$，构造/找到 $x\in A$）。
  2. 陪域取成值域可简化满射：当 $A\to f(A)$ 时满射是免费的；真正的负担全在单射。
  3. “反解 $x$”是验证满射的主力：从 $f(x)=y$ 解出 $x$ 的表达式，再检查它是否落在定义域里（例如 $m/2$ 是否落在 $\mathbb{N}$——这里恰恰不落，所以 $x^2$ 的例子要靠集合定义）。

命题（Example 13 第 2 条）：$\vert \{2n-1\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $

• 定理陈述：奇数自然数集与 $\mathbb{N}$ 等势。
• 证明策略：与第 1 条逐字平行（源文件：”can be proven similarly”）；我们完整写出，示范”类似”到底类似在哪里。
• 逐步推导：
  1. 定义 $g:\mathbb{N}\to\{2n-1\mid n\in\mathbb{N}\}$ 为 $g(n):=2n-1$。
  2. 良定义：对 $n\in\mathbb{N}$，$2n-1\in\mathbb{N}$ 且为奇数，故属于陪域。
  3. 单射：设 $g(n)=g(m)$，即 $2n-1=2m-1$。两边加 $1$：$2n=2m$；两边乘 $1/2$：$n=m$。（依据：加法消去律 + 乘法消去律。）
  4. 满射：任取 $k\in\{2n-1\mid n\in\mathbb{N}\}$，由集合构造式存在 $n\in\mathbb{N}$ 使 $k=2n-1=g(n)$。
  5. 故 $g$ 是双射，$\vert \{2n-1\mid n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $。∎
• 【证明机制解说】：与例 1 完全同构，唯一的新意是”要意识到 $\{2n-1\}$ 的构造式定义已经替你完成了满射“。初学者常在这里多余地论证”每个奇数都是某个整数的两倍减一”——虽然正确，但不如引用集合定义干净。请特别留意”类似证明”绝不等于”跳过”：在考试里，”similar to above”只允许你省略与前面逐句对应的部分，而不允许省略掉”映射定义、单射验证、满射验证”这三根骨架。
• 【证明技巧总结】：移位不变性——$n\mapsto 2n+c$（$c$ 固定整数）这类仿射映射，只要陪域恰好取成 $f(\mathbb{N})$，都是双射；单射的代数化简从不依赖 $c$。

补充命题（Example 13 第 3 条的完整化）：$\vert \{x\in\mathbb{Q}\mid x>0\}\vert =\vert \mathbb{N}\vert $

• 声明：源文件把这条留作习题（Assignment 1）；下面给出两种完整证法，属于对源文件内容的补充。
• 证法 A（蛇形枚举 + 去重，存在性证明）：
  1. 第一步：$\mathbb{N}\times\mathbb{N}$ 可数。 定义 $\varphi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 为 \(\varphi(m,n):=\frac{(m+n-2)(m+n-1)}{2}+m .\) 要证 $\varphi$ 是双射。单射：设 $\varphi(m,n)=\varphi(m^{\prime},n^{\prime})$。记 $s=m+n$，$s^{\prime}=m^{\prime}+n^{\prime}$。先看 $s$ 与 $s^{\prime}$。用反证法：若 $s<s^{\prime}$，则 \(\varphi(m,n)=\frac{(s-2)(s-1)}{2}+m\le \frac{(s-2)(s-1)}{2}+(s-1)=\frac{(s-1)s}{2},\) 而 $\varphi(m^{\prime},n^{\prime})\ge \dfrac{(s^{\prime}-2)(s^{\prime}-1)}{2}+1=\dfrac{(s^{\prime}-2)(s^{\prime}-1)+2}{2}$。当 $s^{\prime}\ge s+1$ 时，可算出 $\dfrac{(s^{\prime}-2)(s^{\prime}-1)+2}{2}>\dfrac{(s-1)s}{2}$，故 $\varphi(m^{\prime},n^{\prime})>\varphi(m,n)$，矛盾；$s>s^{\prime}$ 对称地矛盾。所以 $s=s^{\prime}$。既然 $s=s^{\prime}$，则 $\frac{(s-2)(s-1)}{2}=\frac{(s^{\prime}-2)(s^{\prime}-1)}{2}$，从等式中减去得 $m=m^{\prime}$，再由 $s=s^{\prime}$ 得 $n=n^{\prime}$。（依据：代数变形 + 反证法。）满射：对任一 $k\in\mathbb{N}$，存在唯一 $s$ 使 $\frac{(s-1)s}{2}<k\le\frac{s(s+1)}{2}$（这是”三角形数划分 $\mathbb{N}$”，可用良序性证明）；令 $m:=k-\frac{(s-1)s}{2}\in\{1,\dots,s\}$、$n:=s+1-m\in\mathbb{N}$，则 $\varphi(m,n)=k$。（依据：良序性 + 构造。）
  2. 第二步：正有理数是 $\mathbb{N}\times\mathbb{N}$ 的”商”。 定义 $\pi:\mathbb{N}\times\mathbb{N}\to\{x\in\mathbb{Q}:x>0\}$ 为 $\pi(m,n):=m/n$，则 $\pi$ 是满射（每个正有理数 $m/n$、$m,n\in\mathbb{N}$）。由选择公理一眼可知”满射 $+$ 良序 $\Rightarrow$ 存在单射反向”：对每个 $q\in\{x\in\mathbb{Q}:x>0\}$，令 $\psi(q)$ 为 $\varphi^{-1}$ 在集合 $\{(m,n):m/n=q\}$ 上的最小元素（$\mathbb{N}$ 良序，最小值存在），则 $\psi$ 是单射。于是有单射 $\mathbb{N}\to\{x\in\mathbb{Q}:x>0\}$（包含映射）与单射 $\{x\in\mathbb{Q}:x>0\}\to\mathbb{N}$（$\varphi\circ\psi$）。
  3. 第三步：用 Theorem 12 收口。 由 2 得 $\vert \mathbb{N}\vert \le\vert \{x\in\mathbb{Q}:x>0\}\vert $ 且反向也成立，Cantor–Schröder–Bernstein 给出 $\vert \{x\in\mathbb{Q}:x>0\}\vert =\vert \mathbb{N}\vert $。∎（注意：这一步是本讲 Theorem 12 最典型的应用——用一个单射”往回收”，避免直接构造双射。）
• 证法 B（唯一素因子分解的显式双射）：见前面”基数”小节里那个 $f$ 的定义；它把 $q$ 的分子素因子配偶指数、分母素因子配奇指数，从而直接给出双射，不需要 Theorem 12。两种证法一显式一存在，都合规。
• 【证明机制解说】：证法 A 的”灵光一现”是把二维表格压成一维序列。$\mathbb{N}\times\mathbb{N}$ 是”无穷行 × 无穷列”，直接按行读永远读不完第一行；按 $m+n=k$ 的对角线读，每条对角线有限，所有对角线编号递增，于是”每个格子都排在第 $k-1+\varphi(m,n)$ 位”——没有格子会被永远推迟。这正是”可数”的操作定义。证法 B 的”灵光一现”是用素因子分解这个免费的唯一性：唯一分解定理保证”一个整数只有一种分解方式”，于是”指数奇偶”就把编码变成了一一对应。
• 【证明技巧总结】：① 对角线/蛇形枚举：处理二维索引集合的标准武器。② 满射后取最小原像造单射：不需要写出双射公式，只要集合良序即可。③ Theorem 12 降低工作量：把”造双射”降级为”造两个单射”。④ 唯一分解定理当编码器：只要一个分解是唯一的，就能用它做双射的”单向可逆性”。

补充命题（可数集的子集可数）：若 $A\subset B$ 且 $B$ 可数，则 $A$ 可数

• 声明：这条对应教材 Exercise 0.3.24，源文件未列出，属于补充/参考；它是 Midterm 1(b)、Assignment 3 第 3(b) 题与思考题 Q3(b) 反复用到的工具，因此必须掌握。
• 证明：分情形（依据：可数的定义 = 有限或可数无限）。
  1. $B$ 有限：则 $B$ 与 $\{1,\dots,n\}$ 等势（某 $n\ge0$），存在双射 $h:B\to\{1,\dots,n\}$。$h$ 限制在 $A$ 上仍是单射 $h\vert _A:A\to\{1,\dots,n\}$，其像 $h(A)$ 是 $\{1,\dots,n\}$ 的有限子集，设其有 $m$ 个元素（$m\le n$）。把 $h(A)$ 从小到大排列为 $c_1<c_2<\dots<c_m$，定义 $A\to\{1,\dots,m\}$ 为”$a$ 是 $h(A)$ 中第 $i$ 小的元素的原像”即 $a\mapsto i$，它是双射（依据：构造 + 单射性）。于是 $A$ 有限，故可数。
  2. $B$ 可数无限：则存在双射 $g:B\to\mathbb{N}$。若 $A=\varnothing$，$A$ 有限，可数。若 $A\neq\varnothing$，考虑 $g(A)\subset\mathbb{N}$。由 $\mathbb{N}$ 的良序性 (well-ordering property)（Lecture 1 的 Axiom 5），$g(A)$ 有最小元 $k_1$；递归地，令 $k_{j+1}$ 为 $g(A)\setminus\{k_1,\dots,k_j\}$ 的最小元（只要该差集非空）。归纳可证：这些 $k_j$ 严格递增，且把 $g(A)$ 中的元素按从小到大全部列出，不重不漏。于是 $j\mapsto k_j$ 是 $\mathbb{N}\to g(A)$ 的双射（依据：良序性 + 归纳构造）；再由 $g^{-1}$ 把它拉回，得 $A$ 与 $\mathbb{N}$ 的双射。故 $A$ 可数无限，从而可数。
  3. 两种情形穷尽，结论成立。∎
• 直观解释：从一列里挑出一些元素，还是能排成一列——只要每次挑”剩下里面最靠前的那个”，就不会有元素被无限期推迟。这正是第 2 步里”取最小元”的作用。
• 推论（逆否命题，最常用）：若 $A$ 不可数且 $A\subset B$，则 $B$ 不可数。用法示范（Midterm 1(b)）：设 $E\subset\mathbb{R}$ 可数，取 $A=E$、$B=\mathbb{R}$ 不适合本推论（方向不对）；正确路线是用”可数并可数 = 可数”：$E$ 可数与 $\mathbb{R}\setminus E$ 可数合起来会推出 $\mathbb{R}$ 可数，与第 6 讲的 Corollary 58（$\mathbb{R}$ 不可数）矛盾。而本推论则用于反方向：$E\subset\mathbb{R}$ 不可数（如 $E=(0,1)$）时，任何 $B\supset E$（如 $\mathbb{R}$）也不可数。
• 【证明技巧总结】：① “良序性 ⇒ 能从小到大列举子集” 是把 $\mathbb{N}$ 的子集变成序列的万能钥匙（与可数定义配合，可省去写出显式公式）。② 限制一个单射仍得单射：这一条让”取子集”几乎永远是免费的。

补充命题（可数无限并集）：两两不交的可数无限集之并可数无限（Assignment 3 第 3(a) 题的推广）

• 声明：源文件与作业都用到它，这里给出补充证明，因为它同时是 Midterm 1(b) 与”$\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$”推理的支柱。
• 命题：设 $A,B$ 是可数无限且 $A\cap B=\varnothing$，则 $A\cup B$ 可数无限。
• 证明：由 $\vert A\vert =\vert B\vert =\vert \mathbb{N}\vert $，存在双射 $f:\mathbb{N}\to A$、$g:\mathbb{N}\to B$。定义 $h:\mathbb{N}\to A\cup B$ 为 \(h(n):=\begin{cases}f\!\left(\dfrac{n+1}{2}\right), & n\ \text{为奇数},\\[2mm] g\!\left(\dfrac n2\right), & n\ \text{为偶数}.\end{cases}\)
  1. $h$ 良定义：奇数 $n$ 时 $\frac{n+1}{2}\in\mathbb{N}$（$n=1\Rightarrow1$），偶数 $n$ 时 $\frac n2\in\mathbb{N}$；$f,g$ 都有定义，且值落在 $A\cup B$ 中。✓
  2. $h$ 是单射：设 $h(n)=h(m)$。若 $n,m$ 同为奇数，则 $f(\frac{n+1}{2})=f(\frac{m+1}{2})$，由 $f$ 单射得 $\frac{n+1}{2}=\frac{m+1}{2}$，故 $n=m$。同为偶数时同理得 $n=m$。若一奇一偶，则左边值属于 $A$、右边值属于 $B$（或反之），而 $A\cap B=\varnothing$，矛盾，故此情形不出现。（依据：$f,g$ 单射 + 不交假设。）✓
  3. $h$ 是满射：任取 $y\in A\cup B$。若 $y\in A$，由 $f$ 满射存在 $k\in\mathbb{N}$ 使 $y=f(k)$，取 $n=2k-1$（奇数），则 $h(n)=f(\frac{2k-1+1}{2})=f(k)=y$。若 $y\in B$，由 $g$ 满射存在 $k\in\mathbb{N}$ 使 $y=g(k)$，取 $n=2k$（偶数），则 $h(n)=g(k)=y$。✓
  4. 故 $h$ 是双射，$\vert A\cup B\vert =\vert \mathbb{N}\vert $，即 $A\cup B$ 可数无限。∎
• 【证明机制解说】：这就是”Hilbert 旅馆两列客人的交叉安排”——把 $A$ 的客人放在奇数号房、$B$ 的客人放在偶数号房。去掉”不交”假设是否还成立？ 仍成立（用 $A\cup B=A\cup(B\setminus A)$，再用上一命题把 $B\setminus A$ 降解为可数集）；去掉”可数无限”改为”可数”也成立（有限的情形更容易，可把有限集先塞进前几号房再顺延编号）。
• 【证明技巧总结】：奇偶分流是把两个序列合成一个序列的标准手法；而”两个分支的值域互不相交”正是我们要求 $A\cap B=\varnothing$ 的唯一原因——单射的验证只需要这一个不交假设。

补充：幂集与原集基数的比较（真正的证明在 Lecture 3）

• 声明：源文件 Lecture 2 没有出现幂集 $\wp(S)$，也没有出现 Cantor 定理。Lecture 3（源文件 Theorem 15 (Cantor)）才证明： \(\vert A\vert <\vert \wp(A)\vert \qquad\text{（其中 }\wp(A)=\{B\mid B\subset A\}\text{）}\) 并给出 Remark 16：$\vert \mathbb{N}\vert <\vert \wp(\mathbb{N})\vert <\vert \wp(\wp(\mathbb{N}))\vert <\cdots$。下面属于对下一讲的铺垫与直观理解，此处只做铺垫，不冒充本讲定理。
• 直观铺垫（”为什么会更大？”）：
  1. 有限情形先照镜子：$\vert A\vert =n$ 时 $\vert \wp(A)\vert =2^n$（教材 Exercise 0.3.12，也见本讲 Assignment 1 第 3 题），而 $n<2^n$ 对一切 $n\in\mathbb{N}$ 成立（教材 Exercise 0.3.11，Assignment 1 第 2 题）。所以有限集上”幂集更大”是可数出来的事实。
  2. $\vert A\vert \le\vert \wp(A)\vert $ 很容易：$x\mapsto\{x\}$ 是单射（若 $\{x\}=\{y\}$ 则 $x=y$）。难的是严格（$\vert A\vert \neq\vert \wp(A)\vert $），即”$\wp(A)$ 不可能被 $A$ 铺满”。
  3. $\wp(\mathbb{N})$ 与 $E\subset(0,1)$ 的关系：Assignment 3 第 2 题给出 $E:=\{x\in(0,1):\text{十进制数字只由 }1,2\text{ 组成}\}$，$f(x)=\{j\in\mathbb{N}:d_{-j}=2\}$ 给出 $E\to\wp(\mathbb{N})$ 的双射，于是 $\vert E\vert =\vert \wp(\mathbb{N})\vert $——这是”幂集基数”在 $\mathbb{R}$ 里的具体化身。
  4. 对角线思想的预告：Cantor 定理的证明用一个”自我指涉”的集合 $B:=\{x\in A:x\notin g(x)\}$：若 $g(b)=B$，则”$b\in B$”与”$b\notin B$”两种情形都导致矛盾。这种”让集合拒绝被赋值”的手法，与第 6 讲构造 $y=0.e_{-1}e_{-2}\dots$（每位都不同于第 $n$ 个展开的第 $n$ 位）是同一个思想的两次亮相。本讲先把”双射/单射”这套语言立起来，第 3 讲立刻用它撬动”无限有无数个层级”这一惊人结论。

   |A| < |P(A)| 的直观层级图（Lecture 3 的结论，本讲仅作预告）

   N            P(N)              P(P(N))                 ...
   ℵ₀     <     2^ℵ₀        <    2^(2^ℵ₀)          <      ...
   （可数）      （不可数）        （更不可数）

   每一个箭头都是"严格小于"：|A| ≤ |P(A)| 由 x ↦ {x} 给出；
   严格性由 Cantor 的对角线论证给出（Lecture 3 Theorem 15）。

与教材的对应

• 对应 [JL] §0.3（Lebl, Basic Analysis I，Introduction 第 0.3 节 “Basic set theory”）。本讲的函数与基数部分逐条对应如下（本节的核心命题就是”函数 = $A\times B$ 的特殊子集”以及”基数 = 双射意义下的大小”）：
  • §0.3.3 Functions：Definition 0.3.10（笛卡尔积 $A\times B$）、Definition 0.3.11（函数的严格定义：$f\subset A\times B$，对每个 $x\in A$ 存在唯一 $y$ 使 $(x,y)\in f$；同时给出 domain / range / codomain）、Definition 0.3.13（像 $f(C)$ 与原像 $f^{-1}(D)$，并指出 $R(f)=f(A)$）、Example 0.3.14（$f(x)=\sin(\pi x)$：$f([0,\tfrac12])=[0,1]$、$f^{-1}(\{0\})=\mathbb{Z}$）、Proposition 0.3.15（原像与并/交/补交换）、Proposition 0.3.16（像只对并有等式、对交只有 $\subset$）、Definition 0.3.17（injective / surjective / bijective 与逆函数 $f^{-1}:B\to A$）、Definition 0.3.18（复合 $g\circ f$）。源文件的 “Functions” 一节正是 Definition 0.3.11/0.3.13/0.3.17 的浓缩。
  • §0.3.5 Cardinality：Definition 0.3.26（same cardinality 的定义）、Definition 0.3.27（有限/finite 与 $\vert A\vert =n$）、Definition 0.3.28（$\vert A\vert \le\vert B\vert $、$\vert A\vert <\vert B\vert $，并陈述 Cantor–Bernstein–Schröder 定理”without proof”）、Definition 0.3.29（countably infinite / countable / uncountable）、Example 0.3.30（偶数与 $\mathbb{N}$ 等势，即源文件 Example 13 第 1 条）、Example 0.3.31（$\mathbb{N}\times\mathbb{N}$ 可数，蛇形排列）、Example 0.3.32（$\mathbb{Q}$ 可数）、Definition 0.3.33（幂集 $\wp(A)$）、Theorem 0.3.34 (Cantor)（$\vert A\vert <\vert \wp(A)\vert $，含对角线证明）。
  • 注意教材与本讲的编号差异：本讲源文件用的是 OCW 讲义的编号（Question 10、Definition 11、Theorem 12、Example 13），教材用的是 §0.3.x 编号；两者内容一一对应，但数字不能混用。本笔记在需要对照处都同时标出，正文定理编号一律以源文件（本讲）为准。
• 对应 OCW Assignment 1（Reading Section 0.3；这些题正好覆盖本讲的定义与 Example 13 的第三条）：
  • Exercise 0.3.6：证明分配律 $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ 与 $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$。练什么：集合相等必须双向包含，为后面”证明两个集合相等”（如 $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$）打基础。
  • Exercise 0.3.11：用归纳法证明 $n<2^n$（$n\in\mathbb{N}$）。练什么：归纳法骨架；这条结论正是”有限集的幂集严格更大”的一半（另一半是 Exercise 0.3.12）。
  • Exercise 0.3.12：证明有限集 $A$（$\vert A\vert =n$）的幂集基数为 $2^n$。练什么：用双射数幂集（对每个子集配一个 0-1 序列），幂集基数的第一课。
  • Exercise 0.3.15：证明 $n^3+5n$ 被 $6$ 整除（$\forall n\in\mathbb{N}$）。练什么：归纳法 + 模算术的分类讨论（$n\bmod 6$ 六种情形），与本讲”分情形论证”的精神一致。
  • Exercise 0.3.19：给出”可数无穷多个有限集的并不是有限集”的例子。练什么：可数并集的大小，直接对应 Assignment 3 第 3(a) 题的雏形；标准答案是 $A_n=\{n\}$（则 $\bigcup_n A_n=\mathbb{N}$）或 $A_n=\{1,\dots,n\}$（并集仍是 $\mathbb{N}$）。
  • 第 6 题（习题原文中给定唯一素因子分解定理并要求使用）：证明 $\vert \{q\in\mathbb{Q}:q>0\}\vert =\vert \mathbb{N}\vert $。其中 (a) 要求算出 $f(4/15)$ 并求出使 $f(q)=108$ 的 $q$；(b) 要求用唯一分解定理证明 $f$ 是双射。练什么：把”存在双射”变成”写出显式双射”，并用算术基本定理处理单射与满射。本笔记已算出并验算：$f(4/15)=240$；使 $f(q)=108$ 的 $q=\dfrac29$（核验：$f(2/9)=2^2\cdot3^3=108$）。
• 对应 OCW Assignment 3 第 2、3 题（Reading Sections 1.2–1.5, 2.1；本讲内容是它们的前置工具）：
  • Assignment 3 第 2 题：$E\subset(0,1)$ 为十进制表示只用数字 $1,2$ 的实数集，证明 $\vert E\vert =\vert \wp(\mathbb{N})\vert $（提示：$f(x)=\{j\in\mathbb{N}:d_{-j}=2\}$）。练什么：构造双射到幂集，把”幂集基数”具体化；也顺带练”十进制展开的唯一性问题”（第 6 讲）。
  • Assignment 3 第 3(a) 题：$A,B$ 不交且可数无限，证明 $A\cup B$ 可数无限。练什么：用两次双射把并集排成一列（$a_n\mapsto$ 第 $2n-1$ 位，$b_n\mapsto$ 第 $2n$ 位），正是本讲 Example 13 奇偶分解的推广。
  • Assignment 3 第 3(b) 题：证明 $\mathbb{R}\setminus\mathbb{Q}$ 不可数（可用”$\mathbb{R}\setminus\mathbb{Q}$ 无限、$\mathbb{R}$ 不可数”）。练什么：不可数性 + 可数并集（若 $\mathbb{R}\setminus\mathbb{Q}$ 可数，则 $\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$ 可数，矛盾）。
• 对应 OCW Midterm 第 1 题（本讲定义的直接应用）：
  • Midterm 1(a)：设 $f:A\to B$，$C,D\subset B$，证明 $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$。练什么：原像与集合运算交换，即教材 Proposition 0.3.15 的一条（证明要用双向包含）。
  • Midterm 1(b)：$E\subset\mathbb{R}$ 可数时，$\mathbb{R}\setminus E$ 是否一定不可数？说明理由。练什么：可数并集 + 不可数性。正确回答：是（一定不可数）；证明思路是”若 $\mathbb{R}\setminus E$ 可数，则由 Assignment 3 第 3(a) 的推广 $\mathbb{R}=E\cup(\mathbb{R}\setminus E)$ 可数，与 $\mathbb{R}$ 不可数矛盾”。
  • Midterm 1(c)：$E\subset\mathbb{R}$ 不可数时，$\mathbb{R}\setminus E$ 是否一定可数？说明理由。练什么：反例思维。正确回答：不一定；最干净的反例是 $E=(0,1)\cup(2,3)$：它不可数（含 $(0,1)$），而补集 $(-\infty,0]\cup[1,2]\cup[3,\infty)$ 中包含 $[1,2]$，故补集仍不可数。另一个反例是 $E=(0,1)\cup\mathbb{Q}$：补集 $=\{x\notin(0,1):x\notin\mathbb{Q}\}=(-\infty,0]\setminus\mathbb{Q}\cup[1,\infty)\setminus\mathbb{Q}$，其中 $(-\infty,0]\setminus\mathbb{Q}$ 不可数（因为它与 $(0,1)$ 之间有双射 $x\mapsto(x-1)/2$ 之类，而 $(0,1)$ 不可数）。这类题的要点：“不可数”与”补集可数”之间没有逻辑蕴含，因为”不可数”离”占满全集”还很远（例如 $E=(0,1)$）。
• 对应 Midterm 第 4(b) 题（同一集合 $E$ 的后续应用）：与 Assignment 3 第 2 题同一个 $E$，要求证明 $0.1111\dots$ 是 $E$ 的聚点——它把本讲的”可数/不可数”话题推进到”聚点”，属于第 8–9 讲的范畴，此处仅记录关联。

与其他讲次的关联

• 依赖链的起点——Lecture 1（Sets, Set Operations, and Mathematical Induction）：本讲全部定义都建立在第 1 讲的集合语言上：$\subset$、$\in$、$:=$、$\{x\in A\mid P(x)\}$、$\varnothing$、$\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}$ 都来自 Lecture 1 的 Definition 2 与 Example。第 1 讲的良序性 (Well-ordering property, Axiom 5) 与归纳法 (Theorem 0.3.6) 在本讲被用来支撑”$\mathbb{N}$ 可数”、”三角形数划分 $\mathbb{N}$”以及 Exercise 0.3.11/0.3.15 的证明。
• 本讲是 Lecture 3（Cantor’s Remarkable Theorem and the Rationals’ Lack of the Least Upper Bound Property）的地基：Lecture 3 一开头就用本讲的记号定义幂集并陈述 Theorem 15 (Cantor) $\vert A\vert <\vert \wp(A)\vert $；若没有本讲 Definition 11 里 $\vert \cdot\vert \le\vert \cdot\vert $ 与 $\vert \cdot\vert <\vert \cdot\vert $ 的精确定义，Cantor 定理的陈述根本无法写出来。Lecture 3 证明该定理时用的 $B=\{x\in A:x\notin g(x)\}$ 与”反证 + 分情形”，也正是本讲 Theorem 12 证明（补充部分）所展示的构造/分类手法的延伸。
• 本讲是 Lecture 6（The Uncountability of the Real Numbers）的直接前提：Lecture 6 的 Recall 54 逐字复述本讲定义：”A is countable if A is either finite or $\vert A\vert =\vert \mathbb{N}\vert $”；Theorem 57 (Cantor) 证明 $(0,1]$ 不可数时，第一步就是”假设 $(0,1]$ 可数，则存在双射 $x:\mathbb{N}\to(0,1]$”——这正是本讲”$\vert (0,1]\vert =\vert \mathbb{N}\vert $ 意味着存在双射”的直接应用。Corollary 58（$\mathbb{R}$ 不可数）与 Midterm 1(b)、Assignment 3 第 3(b) 都靠它。
• Assignment 3 第 2 题（$\vert E\vert =\vert \wp(\mathbb{N})\vert $）把本讲与第 3 讲、第 6 讲缝在一起：本讲确立”$\wp$ 与 $\vert \cdot\vert $”，第 3 讲证明 $\vert \mathbb{N}\vert <\vert \wp(\mathbb{N})\vert $，Assignment 3 给出 $E$ 与 $\wp(\mathbb{N})$ 之间的显式双射，于是”$\vert E\vert $ 严格大于 $\vert \mathbb{N}\vert $”这一结论被具体化在 $\mathbb{R}$ 的子集上——为第 6 讲”$\mathbb{R}$ 不可数”提供了另一条可见的路径。
• 向前延伸到序列与极限的语言（Lecture 7 起）：Lecture 7 定义”序列是函数 $x:\mathbb{N}\to\mathbb{R}$”，本讲 §0.3 的”函数”概念在此变成分析的主角；而”可数”在 Lecture 6 之后成为”把集合看成序列、再对序列取极限”这一整套技巧的准入证——例如 $(0,1]$ 的”可数假设”直接翻译成序列 $\{x(n)\}$，才有了对角线构造。

关键要点

1. 基数（大小）的定义是”存在双射”，不是”数元素个数”。 \(\vert A\vert =\vert B\vert \ \stackrel{\text{def}}{\iff}\ \exists\ \text{双射}\ f:A\to B .\) 对无限集，任何”数一数”的说法都无效；”配对成功”才是可验证的判据。有限集的”数数”之所以可用，正是因为它背后藏着一个双射 $\{1,\dots,n\}\to A$。
2. 三类函数的判据与它们的”依赖对象”。
   • 单射：$f(x_1)=f(x_2)\Rightarrow x_1=x_2$；只依赖 $(f,\text{定义域})$。
   • 满射：$f(A)=B$，即 $\forall y\in B\ \exists x\in A,\ f(x)=y$；依赖 $(f,\text{定义域},\text{陪域})$。
   • 双射 = 单射 + 满射；此时才有逆函数 $f^{-1}:B\to A$，且 $f\circ f^{-1}=\mathrm{id}_B$、$f^{-1}\circ f=\mathrm{id}_A$。 同一公式换定义域/陪域，单射性可能变（$x^2$ 在 $\mathbb{R}$ 与 $[0,\infty)$ 上）、满射性几乎总要变（$2x$ 在 $\mathbb{Z}\to\mathbb{Z}$ 与 $\mathbb{Z}\to2\mathbb{Z}$ 上）。
3. 比较记号与 Cantor–Schröder–Bernstein（源文件 Theorem 12）。 \(\vert A\vert \le\vert B\vert \iff \exists\ \text{单射}\ A\to B,\qquad \vert A\vert <\vert B\vert \iff \vert A\vert \le\vert B\vert \ \wedge\ \vert A\vert \neq\vert B\vert .\) 若 $\vert A\vert \le\vert B\vert $ 且 $\vert B\vert \le\vert A\vert $，则 $\vert A\vert =\vert B\vert $。黄金用法：证明两集合等势时，分别造两个单射往往比造一个双射省力（$\mathbb{Q}$ 可数即典型）。
4. 可数 = 能排成一列。 \(A\ \text{可数无限}\iff \vert A\vert =\vert \mathbb{N}\vert ;\qquad A\ \text{可数}\iff A\ \text{有限或可数无限};\qquad \text{否则不可数}.\) 本讲的核心等式：$\vert \{2n:n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $、$\vert \{2n-1:n\in\mathbb{N}\}\vert =\vert \mathbb{N}\vert $、$\vert \{q\in\mathbb{Q}:q>0\}\vert =\vert \mathbb{N}\vert $（后者为 Assignment 1 习题，本笔记已给两种证法）；补充：$\vert \mathbb{Z}\vert =\vert \mathbb{N}\vert $、$\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $。
5. 无限集的”反常识”铁律：真子集可以和外层集合同样大。 \(2\mathbb{N}\subsetneq\mathbb{N}\quad\text{但}\quad \vert 2\mathbb{N}\vert =\vert \mathbb{N}\vert .\) 因此”$A\subsetneq B\Rightarrow\vert A\vert <\vert B\vert $”在无限情形下是错的；反过来，”与某个真子集等势”恰恰可以用来刻画无限集（教材 Remark）。并且 $\vert A\vert <\vert \wp(A)\vert $ 的预告说明：无限还有层级，$\mathbb{N},\wp(\mathbb{N}),\wp(\wp(\mathbb{N})),\dots$ 严格递增（真正的证明在第 3 讲）。

常见误区与注意事项

• 误区 1：把”$f:A\to B$ 是函数”与”$f$ 满射”混为一谈。
  • 错误做法：看到 $f:\mathbb{R}\to\mathbb{R}$，$f(x)=x^2$，就说”值域是 $\mathbb{R}$”。
  • 为什么错：陪域是 $\mathbb{R}$ 只是声明输出落在 $\mathbb{R}$ 里；实际值域是 $[0,\infty)\subsetneq\mathbb{R}$。值域 $=$ 像 $f(A)$，陪域只是容器。
  • 正确做法：凡涉及满射，先把 $f(A)$ 和 $B$ 分开写、分开比对。“陪域是承诺，值域是事实。”
• 误区 2：用”$A\subsetneq B$ 所以 $\vert A\vert <\vert B\vert $”下结论。
  • 错误做法：因为 $2\mathbb{N}\subsetneq\mathbb{N}$，就断言 $\vert 2\mathbb{N}\vert <\vert \mathbb{N}\vert $。
  • 为什么错：$n\mapsto2n$ 是双射，$\vert 2\mathbb{N}\vert =\vert \mathbb{N}\vert $。包含关系只给出 $\vert A\vert \le\vert B\vert $，永远给不出严格小于（严格性必须来自”不存在双射”的证明，如 Cantor 定理）。
  • 正确做法：要证 $\vert A\vert <\vert B\vert $，必须先证 $\le$、再证 $\neq$（后者通常要反证 + 对角线）。
• 误区 3：验证满射时只”看起来覆盖了”，不做全称论证。
  • 错误做法：说”$f(n)=2n$ 显然是满射，因为每个偶数都是某个数的两倍”——这句话没有指出那个数属于定义域。
  • 为什么错：如果定义域是 $\mathbb{Z}$、陪域是 $\mathbb{Z}$，同样的”每个偶数都是两倍”就不再成立（$y=1$ 没有原像）。
  • 正确做法：满射的验证格式固定为”任取 $y\in B$ →（构造或解出）$x\in A$ → 验证 $f(x)=y$“，中间必须显式声明 $x$ 落在定义域内。源文件对 $f(n)=2n$ 的满射验证用的就是”由集合定义存在 $n\in\mathbb{N}$”。
• 误区 4：把 $f^{-1}(D)$ 与 $f^{-1}(y)$ 混用，或在 $f$ 非双射时把 $f^{-1}$ 当函数。
  • 错误做法：对 $f(x)=x^2$ 写”$f^{-1}(4)=2$”。
  • 为什么错：$f^{-1}(\{4\})=\{-2,2\}$ 是集合，不是元素；$f$ 不单射，逆函数不存在。
  • 正确做法：原像符号 $f^{-1}$ 在任何函数上都合法，但它作用于集合（$D\subset B$，或写成 $f^{-1}(\{y\})$），结果是集合；只有当 $f$ 是双射时，才可把 $f^{-1}(\{y\})$ 这个单元素集简写成 $f^{-1}(y)$ 并视其为函数 $B\to A$。
• 误区 5：量词顺序与”依赖关系”写反。
  • 错误做法：把满射写成”$\exists x\in A\ \forall y\in B,\ f(x)=y$”。这说的是”存在一个 $x$，它同时映到所有 $y$”，除非 $B$ 只有一个元素，否则不可能。
  • 为什么错：满射正确的量化结构是 \(\forall y\in B\ \ \exists x\in A,\ \ f(x)=y,\) $x$ 是依赖于 $y$ 的（对不同的 $y$ 可以取不同的 $x$），正如 $\varepsilon$-$\delta$ 里 $\delta$ 依赖 $\varepsilon$。把 $\exists$ 提到 $\forall$ 前面就把”依赖”变成”统一”，语义完全反转。
  • 正确做法：写量词时心里默念”哪一个先被给定、哪一个后被告知”，并把依赖关系写在括号里（如”$\forall y\in B,\ \exists x=x(y)\in A$”）。
• 误区 6：把”可数”当成”小”、”不可数”当成”大得能装下一切”。
  • 错误做法：Midterm 1(c) 答”不可数集的补集一定可数”。
  • 为什么错：取 $E=(0,1)\subset\mathbb{R}$，它不可数，补集 $(-\infty,0]\cup[1,\infty)$ 也不可数。不可数只说明”排不成一列”，不说明”几乎占满全集”。
  • 正确做法：涉及补集的命题，一律先想极小（$E=\mathbb{Q}\cap(0,1)$，可数）与极大（$E=\mathbb{R}\setminus\{0\}$，补集只有一点）两个极端例子。Midterm 1(b) 的”可数集的补集必不可数”是对的（因为 $\mathbb{R}$ 不可数 + 可数并集可数），而 1(c) 的”不可数集的补集必可数”是错的——注意这一对问答并不对称。
• 误区 7：以”有限直觉”处理”$\mathbb{N}\times\mathbb{N}$ 按行/按列枚举”。
  • 错误做法：说”先列 $(1,1),(1,2),(1,3),\dots$ 把第一行列完，再列第二行”。
  • 为什么错：第一行永远列不完，第二行永远轮不到；这不是一个到 $\mathbb{N}$ 的枚举（$x\in A$ 必须对应到有限编号 $n\in\mathbb{N}$）。
  • 正确做法：改用对角线（按 $m+n$ 分组）枚举，保证每个格子都在有限步内被读到；这正是教材 Example 0.3.31 与质数编码法之所以能成功的原因。

思考题（带答案）

Q1.（构造显式双射） 证明 $\vert \mathbb{N}\vert =\vert \mathbb{Z}\vert $，要求写出一个显式的双射并完整验证单射与满射。

Q2.（不可数性的证明思路） 设 $E\subset(0,1)$ 是把 $x\in(0,1)$ 的十进制展开中只出现数字 $1$ 和 $2$ 的实数全体，即 \(E:=\{x\in(0,1):\forall j\in\mathbb{N},\ \exists d_{-j}\in\{1,2\},\ x=0.d_{-1}d_{-2}\dots\}.\) （1）证明 $E$ 与 $\wp(\mathbb{N})$ 之间存在双射（提示：$f(x)=\{j\in\mathbb{N}:d_{-j}=2\}$）；（2）说明为什么由此可断定 $E$ 不可数，并写清用到了哪一讲的哪条定理。

Q3.（概念理解 + 反面案例） 判断下列命题真假，真的给出证明，假的给出明确反例： (a) 若 $f:A\to B$ 是单射且 $A$ 无限，则 $B$ 无限； (b) 若 $A$ 可数、$B$ 不可数，且 $A\subset B$，则 $B\setminus A$ 不可数； (c) 设 $f:A\to B$ 是双射，$C\subset A$，则 $f(A\setminus C)=B\setminus f(C)$。