Lecture 3: Cantor’s Remarkable Theorem and the Rationals’ Lack of the Least Upper Bound Property（康托尔定理与有理数缺乏最小上界性质）

目录 · ← l2 · l4 →

Lecture 3: Cantor’s Remarkable Theorem and the Rationals’ Lack of the Least Upper Bound Property（康托尔定理与有理数缺乏最小上界性质）

概述

本讲是全课程的转折点。前两讲一直在问”集合有多大”（基数理论：单射/满射/双射、可数集、Cantor–Schröder–Bernstein 定理），本讲前半段把它推到极致：没有任何集合能与自己的幂集一样大（Cantor 定理，源文件 Theorem 15）。于是 $\mathbb{N}$ 之外还有严格更大的无穷：

“无穷”本身有无穷多个层次（源文件 Remark 16）。这是本课程第一次证明”不可数集”的存在。

后半段转向”实数是什么“，引入四组工具：有序集（ordered set，Definition 23）、上界/下界/有界（bounded above / below，Definition 24）、上确界/下确界（supremum / infimum，记 $\sup/\inf$）与最小上界性质（least upper bound property，简称 LUB，Definition 26），并用它证明第二个高潮结论：有理数 $\mathbb{Q}$ 不具备 LUB 性质（Theorem 27、28），即

在 $\mathbb{Q}$ 中有上界（例如 $2$），却没有上确界。

所以本讲回答了两个问题：

1. 有没有比 $\mathbb{N}$ 更大的集合？ 有：$\wp(\mathbb{N})$ 就比 $\mathbb{N}$ 大，而且大得没完没了。证明工具是对角化论证（diagonal argument）。
2. 有序集中”最小的上界”一定存在吗？ 不一定：$\mathbb{Q}$ 会把它漏掉。漏掉的那个数就是 $\sqrt{2}$。

第二个问题的否定答案是全课程的第一块地基。源文件 Theorem 22 已宣告终局：存在唯一的、包含 $\mathbb{Q}$ 且具有 LUB 性质的有序域，记作 $\mathbb{R}$。下一讲（Lecture 4）给出”域”与”有序域”的精确定义并完成刻画；此后 Lecture 6 单调有界定理、Lecture 9 Bolzano–Weierstrass 定理、Lecture 10 Cauchy 完备性、Lecture 16 极值定理与介值定理、Lecture 21 连续函数可积性，全部要靠 LUB 性质。

用一张依赖图记住本讲的位置：

  Lecture 1–2           Lecture 3                    Lecture 4 及以后
  ┌─────────────┐   ┌───────────────────────┐   ┌────────────────────────┐
  │ 单射/满射/双射│──►│ Cantor 定理 |A|<|℘(A)|│──►│ ℝ = 唯一含 ℚ、具 LUB 的 │
  │ 基数、可数集  │   │ 有序集、sup / inf     │   │ 有序域；Archimedes、    │
  │ 良序原理、CSB │   │ LUB 性质；ℚ 不满足它   │   │ 序列极限、BW、IVT、积分… │
  └─────────────┘   └───────────────────────┘   └────────────────────────┘
     "集合有多大"          "实数是什么"（起点）

核心定义与直观解释

（幂集 power set，源文件 Question 14）

• 严格定义：对任意集合 $A$，定义 $A$ 的幂集为它的所有子集组成的集合：

注意 $\wp(A)$ 的元素本身是集合，故 $\wp(A)$ 是”集合的集合”。若 $\vert A\vert =n$（有限），则 $\vert \wp(A)\vert =2^n$——这正是”幂集”（power set）得名的原因。

• 直观解释（”它到底在说什么？”）：幂集就是把 $A$ 的每个元素都问一遍”你要不要？”。$A$ 的每个元素有两种选择（进或不进这个子集），$n$ 个元素独立选择，共 $2^n$ 种子集。所以 $\wp(A)$ 可以被理解成”$A$ 上的投票记录表“：每个子集就是一张投票结果。

• 为什么需要这个条件（为什么必须是”所有”子集）？ 如果只取一部分子集（比如只取有限子集），”$2^n$”这个计数就不成立，Cantor 定理也不成立。源文件 Theorem 15 的威力恰恰来自”全部子集”这个极端要求：集合越大，它给出的”选择”越多，而且是爆炸式地多。

• 具体示例（源文件 Question 14 的三个例子）：

注意 $A=\varnothing$ 时 $\wp(A)=\{\varnothing\}\neq\varnothing$：空集也有一个子集，就是它自己。这是”$\wp(A)$ 永远比 $A$ 多一层”的第一个迹象。再看 $A=\{1,2,3\}$：

数一数：$8=2^3$ 个。

• 反例（如果适用）：把”$\subset$”当成集合之间的序（见后文 Definition 23 的非例）：$\wp(\mathbb{N})$ 中 $\{1\}$ 与 $\{2\}$ 互不包含，所以 $(\wp(\mathbb{N}),\subset)$ 不是有序集；这提醒我们”幂集”本身只是个集合，它上面的 $\subset$ 并没有把元素排成一条线。

（回顾：基数的比较，Lecture 2 Definition 11）

本讲要反复用到 Lecture 2 的记号，先抄在这里：

• $\vert A\vert =\vert B\vert $：存在双射 $f:A\to B$（Cantor 的”大小相同”定义）。
• $\vert A\vert \le\vert B\vert $：存在单射 $f:A\to B$。
• $\vert A\vert <\vert B\vert $：$\vert A\vert \le\vert B\vert $ 且 $\vert A\vert \neq\vert B\vert $。

• $A$ 可数（countable）：$A$ 有限或 $\vert A\vert =\vert \mathbb{N}\vert $；否则称 $A$ 不可数（uncountable）。

• 直观解释：$\vert A\vert \le\vert B\vert $ 的含义是”$A$ 能被塞进 $B$ 而不打架”（单射）；$\vert A\vert <\vert B\vert $ 的含义是”塞得进，但塞不满”。
• 为什么需要这个定义？ 对有限集，”大小”可以数出来；对无限集，”数”失效了，只能靠配对（mapping）比较。Cantor 的全部理论建立在这条定义上。

（Definition 23 有序集 ordered set）

• 严格定义：一个有序集是一个集合 $S$ 连同它上面的一个关系 $<$（称作一个”次序”（ordering）），满足：

约定 $x\le y$ 表示”$x<y$ 或 $x=y$”；类似地定义 $>$ 与 $\ge$。

• 直观解释（”它到底在说什么？”）：条件 (1) 说任意两个元素都能比出个先后（”万能比较尺”）；条件 (2) 说比大小的结论可以接力使用：如果 $x$ 在 $y$ 前面、$y$ 在 $z$ 前面，那么 $x$ 一定在 $z$ 前面（”没有循环”）。有了这两条，集合的元素就能真的排成”一条线”，我们才可能谈论”某个东西的右边还有没有东西”——这正是上界、上确界概念的前提。

• 为什么需要这个条件？ 缺了 (1)，两个元素可能”互不可比”，这时”最小的上界”就不唯一甚至无法比较（见下文 Definition 23 的非例 $\wp(\mathbb{N})$）。缺了 (2)，比较关系会自相缠绕，$x<y<z$ 却 $z<x$，那么”上界”（要对所有 $x\in E$ 满足 $x\le b$）与”最小”（要能与所有上界比较）就会互相矛盾。

• 具体示例（源文件给出的三个例）：

把 $\mathbb{Q}$ 的定义走一遍：取 $p=\frac{3}{4}$，$q=\frac{1}{2}$。$p-q=\frac{1}{4}=\frac{1}{4}$，取 $m=1,n=4\in\mathbb{N}$，所以 $p>q$；反过来 $q-p=-\frac14\notin\{$正有理数$\}$，所以不能有 $q>p$。又 $p\neq q$，三歧性成立。

把字典序走一遍：$(1,5)$ 与 $(2,0)$：因为 $1<2$，所以 $(2,0)>(1,5)$（第二坐标 $0<5$ 完全不起作用！）。而 $(2,0)$ 与 $(2,1)$：第一坐标相等，比第二坐标 $0<1$，所以 $(2,1)>(2,0)$。这正是查词典的规则：先比第一个字母，相同再比第二个。

• 反例（源文件明确给出的非例）：$S=\wp(\mathbb{N})$，关系取真包含 $A\prec B\iff A\subset B$。取 $A=\{1\}$、$B=\{2\}$，则

三歧性 (1) 的两两可比性彻底失效。所以 $(\wp(\mathbb{N}),\subset)$ 不是有序集。（顺带一提：$A\subset A$ 也说明真包含不满足反身性；这种只满足传递性、不满足三歧性的关系叫偏序（partial order），它比有序集弱。）

（Definition 24 上界、下界、有界 bounded above / below）

• 严格定义：设 $S$ 是有序集，$E\subset S$。

(1) 若 $\exists b\in S$ 使 $\forall x\in E,\ x\le b$，则称 $E$ 有上界，$b$ 是 $E$ 的一个上界； (2) 若 $\exists c\in S$ 使 $\forall x\in E,\ x\ge c$，则称 $E$ 有下界，$c$ 是 $E$ 的一个下界。

若 $E$ 既有上界又有下界，就说 $E$ 有界（bounded）。

• 直观解释：上界是”天花板“（$E$ 中一切元素都不超过它），下界是”地板“（$E$ 中一切元素都不低于它）。天花板不必贴着 $E$——$E=\{0,1\}$ 的上界有 $1,2,3,100,\dots$，全都是天花板，$1$ 只是最低的那个。

• 为什么需要这个条件（为什么 $b$ 必须属于 $S$）？ 定义要求 $b\in S$，即上界必须住在同一个有序集里。这一点极其关键：$E=\{q\in\mathbb{Q}:q>0,\ q^2<2\}$ 在 $\mathbb{Q}$ 中有上界（$2$ 就是），但它的”真正天花板”$\sqrt{2}$ 不在 $\mathbb{Q}$ 里。若允许 $b$ 跑到 $S$ 外，$\mathbb{Q}$ 中任何有界集就都有上确界了，Theorem 28 无从谈起。LUB 性质的整个内容就是”上确界必须留在 $S$ 内部”。

• 具体示例：

把”$E=\mathbb{N}\subset\mathbb{Z}$ 无上界”算一遍：设 $b\in\mathbb{Z}$ 是上界，则需 $n\le b$ 对所有 $n\in\mathbb{N}$ 成立。取 $n=b+1\in\mathbb{N}$（因为 $b+1\ge 1$），得 $b+1\le b$，矛盾。所以不存在这样的整数 $b$。

• 反例（有界 vs 有最大元，两回事）：$(0,1)$ 有上界 $1$，但没有最大元——对任意 $x\in(0,1)$，$\frac{x+1}{2}$ 仍在 $(0,1)$ 中且更大。反过来 $\mathbb{N}\subset\mathbb{Z}$ 有最小元 $1$ 却没有上界。”有界”与”有最大元”是完全不同的两件事，$\sup$ 与 $\max$ 之辨由此而来。

（上确界 / 下确界 definition of supremum / infimum；源文件 Definition 24 之后的两组条件）

• 严格定义：设 $S$ 是有序集，$E\subset S$。我们说 $b_0\in S$ 是 $E$ 的最小上界（least upper bound），或称上确界（supremum），记作 $b_0=\sup E$，如果

类似地，$c_0\in S$ 是 $E$ 的最大下界（greatest lower bound），或称下确界（infimum），记作 $c_0=\inf E$，如果

勘误说明：源文件在这一处把下确界的条件 (B) 印成了”$c<c_0$”（应为 $c\le c_0$）。若真要求 $c<c_0$，则取 $E=\{0\}\subset\mathbb{Q}$：$E$ 的下界只有 $0$ 自己，条件 (B) 要求 $0<0$，失败，于是 $\inf\{0\}$ 竟然不存在——这与定义的本意相悖（$\inf\{0\}$ 理应等于 $0$）。正确形式是 $c\le c_0$，本文一律采用正确形式。

• 直观解释：如果你把 $E$ 的所有上界收集起来，得到”天花板集合” $U=\{b\in S: b \text{ 是 } E \text{ 的上界}\}$，那么 $\sup E$ 就是 $U$ 中的最小元：

上确界 = 最低的那块天花板。 它紧紧贴着 $E$ 的右端；只要不是 $\max E$（能取到的情况），它就在 $E$ 的右端点”外面一点点”的位置。同理，下确界是所有地板里最高的那块。

• 为什么需要这个条件？ 条件 (A) 保证 $\sup E$ 是”合格的天花板”，条件 (B) 保证它是”最低的”。两条缺一不可：
  • 只有 (A)：任何一个上界都能自称 $\sup$，$2$ 和 $100$ 都是 $E=\{q\in\mathbb{Q}:q^2<2\}$ 的上界，无法唯一化；
  • 只有 (B)：一个不在天花板集合里的数也可能”比所有天花板都小”（例如 $E=(0,1)$ 时 $-5$ 满足”$\le$ 一切上界”），那它就不是上确界。所以 (A) 是”合法”，(B) 是”最小”，合起来才是定义。

  【补充命题】上确界若存在则唯一。 设 $b,b^{\prime}$ 都是 $E$ 的上确界。由 (B) 用于 $b$（取上界 $b^{\prime}$）得 $b\le b^{\prime}$；由 (B) 用于 $b^{\prime}$（取上界 $b$）得 $b^{\prime}\le b$；由三歧性，$b\le b^{\prime}$ 且 $b^{\prime}\le b$ 只能有 $b=b^{\prime}$。（此结论见 [JL] §1.1 正文，源文件未单列编号。）正因唯一，记号 $\sup E$ 才有意义。

• 具体示例（源文件 Example 25 的三个例子，逐个走一遍）：

  例 1：$S=\mathbb{Z}$，$E=\{-2,-1,0,1,2\}$。上界集合是 $\{2,3,4,\dots\}$，最小元为 $2$，故 $\sup E=2$；下界集合是 $\{\dots,-4,-3,-2\}$，最大元为 $-2$，故 $\inf E=-2$。这里 $\sup E=2\in E$，$\inf E=-2\in E$，恰好也是 $\max E$ 与 $\min E$。

  例 2（关键：sup 可以不属于 $E$）：$S=\mathbb{Q}$，$E=\{q\in\mathbb{Q}:0\le q<1\}$。上界集合是 $\{b\in\mathbb{Q}:b\ge 1\}$，其最小元是 $1$，故 $\sup E=1$，而 $1\notin E$（因为 $1<1$ 为假）。下界集合是 $\{b\in\mathbb{Q}:b\le 0\}$，最大元 $0\in E$，故 $\inf E=0$。同一个集合，$\inf$ 取得到、$\sup$ 取不到。

  例 3（sup 可以不存在）：$S=\mathbb{Z}$，$E=\mathbb{N}$。下界集合是 $\{\dots,-1,0,1\}$，最大元 $1$，故 $\inf E=1$。但上界集合是空的（上面刚算过），空集没有最小元，故 $\sup E$ 不存在。

  补充一个最常用的 $\mathbb{R}$ 中的例子（标注为补充：源文件未列，但后续讲次天天用）：$E=\left\{\frac1n:n\in\mathbb{N}\right\}$。它的上界集合是 $[1,\infty)$，最小元 $1=\frac11\in E$，故 $\sup E=1=\max E$；下界集合是 $(-\infty,0]$，最大元 $0$，故 $\inf E=0$，而 $0\notin E$。这组集合 $\sup$ 取得到、$\inf$ 取不到，正好与例 2 互补，说明”$\sup$ 是否属于 $E$”与”$\inf$ 是否属于 $E$”完全独立。

• 反例（$\sup$ 与 $\max$ 的区别）：

黄金法则：$\max E$ 存在 $\Longrightarrow$ $\sup E=\max E$；反之不然。凡是把 $\sup E$ 当作”$E$ 中最大的那个元素”用，都是错的。

（Definition 26 最小上界性质 least upper bound property）

• 严格定义：有序集 $S$ 具有最小上界性质（least upper bound property，简称 LUB 性质），如果

用符号写：

• 直观解释（”它到底在说什么？”）：LUB 性质说：只要一个集合”往右有天花板”，那么”最低的那块天花板”就一定存在，而且就在这个集合所在的宇宙里。 换句话说，这个有序集在”取上确界”这个操作下是封闭的，而且不会有”漏风的缺口”：任何被挡住不往上走的集合，都在某个具体的元素处”撞到墙”。$\mathbb{R}$ 满足 LUB 性质，$\mathbb{Q}$ 不满足——这正是两者唯一的关键差别。

• 为什么需要这（两）个条件（非空 + 有上界）？ 两个条件都不可省：
  • 去掉”非空”：$E=\varnothing$。任何 $b\in S$ 都满足”$\forall x\in\varnothing,\ x\le b$”（空真命题），所以 $\varnothing$ 的上界集合是整个 $S$；若 $S$ 本身无最小元（如 $S=\mathbb{Q}$ 或 $S=\mathbb{R}$），则 $\sup\varnothing$ 不存在。所以必须排除空集（约定 $\sup\varnothing=-\infty$ 是后来扩张实数系的事）。
  • 去掉”有上界”：$E=\mathbb{N}\subset\mathbb{Z}$ 非空但无上界，上界集合为空，空集无最小元，$\sup$ 不存在。这也是应该排除的情形（约定 $\sup E=+\infty$ 不属于 LUB 性质的范围）。

  所以 LUB 性质精确地只说：”非空 + 有上界 $\Rightarrow$ 有 $\sup$“，一个字都不能多，一个字都不能少。

• 具体示例：
  • $\mathbb{R}$ 具有 LUB 性质（这是 $\mathbb{R}$ 的公理/定义性质，源文件 Theorem 22；Lecture 4 会说这是把 $\mathbb{R}$ 与 $\mathbb{Q}$ 区分开的那一条）。
  • $S=-\mathbb{N}=\{-1,-2,-3,\dots\}$（源文件给出的例子）具有 LUB 性质。理由（源文件）：若 $E\subset S$ 非空且有上界，则 $-E\subset\mathbb{N}$ 有下界；由良序原理，$-E$ 有最小元 $x$，于是 $-x=\sup E$（且 $-x\in E\subset S$，所以 $S$ 中这个上确界其实还是最大值）。这个小例子告诉我们：LUB 性质与”稠密”“像 $\mathbb{R}$”没有必然关系——$-\mathbb{N}$ 是离散的、有洞的，照样满足 LUB 性质。
  • 【补充】 $\mathbb{Z}$ 也具有 LUB 性质。设 $E\subset\mathbb{Z}$ 非空且有上界 $b\in\mathbb{Z}$。则集合 $\{b-x:x\in E\}\subset\mathbb{N}\cup\{0\}$ 非空；若其中含 $0$ 则 $b\in E$ 即 $\max E=b$；否则它是 $\mathbb{N}$ 的非空子集，由良序原理有最小元 $m$，令 $x_0=b-m\in E$，则 $\forall x\in E$，$b-x\ge m$ 即 $x\le x_0$，故 $x_0=\max E=\sup E$。所以”具有 LUB 性质”并不足以刻画 $\mathbb{R}$，还要加上”是有序域“、”包含 $\mathbb{Q}$”这两条——这正是 Theorem 22 的完整内容。

• 反例：$\mathbb{Q}$ 不具有 LUB 性质（本讲 Theorem 28 的结论）。具体地，$E=\{q\in\mathbb{Q}:q>0,\ q^2<2\}$ 非空（$1\in E$）、有上界（$2$ 是上界），但在 $\mathbb{Q}$ 中没有上确界。

  还有一个更”粗暴”的反例（补充）：$S=\mathbb{Q}\setminus\{0\}$ 配上通常的序。$E=\{q\in S:q>0\}$（即正有理数）有下界（比如 $1$ 是下界吗？不是——需要 $q\ge c$ 对所有 $q\in E$；取 $q=\frac12<1$，不成立。真正的下界是负有理数）……这个例子容易绕晕，所以我们还是用源文件的 $E=\{q\in\mathbb{Q}:q>0,q^2<2\}$ 作为标准反例。

（回顾与本讲目标：Definition 24 之前的 Remark 20 与 Theorem 22）

• 源文件 Remark 20（原文精神）：”某种意义上（需要精确化），实数集是唯一一个具有有理数的一切代数与序性质、但没有洞的集合。”

• 源文件 Theorem 22（实数 $\mathbb{R}$）：存在唯一的、包含 $\mathbb{Q}$、具有最小上界性质的有序域（ordered field），我们把这个域记作 $\mathbb{R}$。

  注意本讲还没定义”域”：源文件在本讲末尾说”$\mathbb{Q}$ 是一个域（field）的例子，我们下一讲开始讨论”（对应 Lecture 4 的 Definition 30 与 Definition 33）。所以本讲对 Theorem 22 只做”目标宣告”与”必要性论证”（$\mathbb{Q}$ 缺 LUB，所以需要一个更大的东西），精确定义与唯一性证明在 Lecture 4。

• 直观解释：”$\mathbb{Q}$ 完美地满足加减乘除的一切规则，也完美地满足比大小的规则，唯独在’取上确界’这件事上会掉链子。” 于是我们的策略是：保持 $\mathbb{Q}$ 的一切好性质，把洞补上。补洞的产物就是 $\mathbb{R}$（源文件 Remark 20 的”none of the holes”）。

定理与完整证明（核心）

定理 15（Cantor 定理）

• 定理陈述：设 $A$ 是任意集合，则

等价的说法：不存在从 $A$ 到 $\wp(A)$ 的满射；因此 $\wp(A)$ 严格地比 $A$ “大”。（源文件原文：”If $A$ is a set, then $\vert A\vert <\vert \wp(A)\vert $.”）

• 证明策略：要把 $\vert A\vert <\vert \wp(A)\vert $ 拆成两件事（依据 Lecture 2 的定义 $\vert A\vert <\vert B\vert $ 指 $\vert A\vert \le\vert B\vert $ 且 $\vert A\vert \neq\vert B\vert $）：

  第一步（$\le$）：构造一个明显的单射 $A\to\wp(A)$，即 $f(x)=\{x\}$（”把每个元素装进只含它自己的单元素集”）。这一步是直接证明。 第二步（$\neq$）：用反证法。假设 $\vert A\vert =\vert \wp(A)\vert $，则存在满射 $g:A\to\wp(A)$。然后构造一个 $g$ 永远打不中的子集 $B=\{x\in A:x\notin g(x)\}$，制造矛盾。这一步是对角化构造（diagonal argument）。

  为什么选这个策略？因为”两个集合不等势”是一个否定命题（不存在双射），对否定命题最自然的武器是反证；而反证需要从”存在双射”推出荒谬，最有效的推法就是造一个反例对象，让它自己否定自己（自指）。

• 逐步推导：

  第一部分：$\vert A\vert \le\vert \wp(A)\vert $。

  1. 定义 $f:A\to\wp(A)$ 为 $f(x)=\{x\}$。（依据：对每个 $x\in A$，$\{x\}\subset A$，所以 $\{x\}\in\wp(A)$，$f$ 良定义。）
  2. 证明 $f$ 是单射：设 $f(x)=f(y)$，即 $\{x\}=\{y\}$。两个集合相等意味着元素完全相同；$\{x\}$ 的唯一元素是 $x$，$\{y\}$ 的唯一元素是 $y$，故 $x=y$。（依据：集合的外延公理 + 单元素集的定义。）
  3. 因此存在单射 $A\to\wp(A)$。（依据：$\vert A\vert \le\vert B\vert $ 的定义，Lecture 2 Definition 11。）
  4. 事实上这个 $f$ 不是满射：$A\neq\varnothing$ 时 $\varnothing\in\wp(A)$ 但 $\varnothing\notin f(A)$（$f$ 的像全是非空单元素集）；$A=\varnothing$ 时 $f$ 是空映射，像集为空，而 $\wp(A)=\{\varnothing\}\neq\varnothing$。但这只是”这个特定的 $f$ 不满”，不能推出”不存在满射”。所以必须做第二部分。（依据：逻辑上”某个映射不满”$\neq$”所有映射都不满”。）

  第二部分：$\vert A\vert \neq\vert \wp(A)\vert $（反证 + 对角化）。

  1. 反设 $\vert A\vert =\vert \wp(A)\vert $。按定义（Lecture 2 Definition 11），存在双射 $g:A\to\wp(A)$；双射当然是满射，即 $g(A)=\wp(A)$。（依据：$\vert A\vert =\vert B\vert $ 的定义。）
  2. 构造

逐步核对这定义的合法性：$g(x)$ 是 $\wp(A)$ 的元素，也就是 $A$ 的子集，所以”$x\in g(x)$”是一个有真假的命题；用 $\notin$ 取反，再用分离公理把 $A$ 中满足它的元素收集起来，得到 $B\subset A$，即 $B\in\wp(A)$。（依据：幂集的定义 + 子集分离。）

1. 由第 5 步的满射性，存在 $b\in A$ 使 $g(b)=B$。（依据：满射的定义 $g(A)=\wp(A)$，而 $B\in\wp(A)$。）
2. 现在考察”$b\in B$ 吗？”。由三歧性（或经典逻辑的排中律），只有两种可能，逐一排除：
   • 情形 1：$b\in B$。 由 $B$ 的定义（$B$ 的元素 $x$ 必须满足 $x\notin g(x)$），得 $b\notin g(b)$；又 $g(b)=B$，所以 $b\notin B$。于是”$b\in B$ 且 $b\notin B$”，矛盾。
   • 情形 2：$b\notin B$。 由 $g(b)=B$ 得 $b\notin g(b)$；而 $B$ 的定义正是”所有满足 $x\notin g(x)$ 的 $x$”，所以 $b$ 满足条件，得 $b\in B$。于是”$b\notin B$ 且 $b\in B$”，矛盾。
3. 两种情形穷尽了全部可能，而每一种都引出矛盾。所以第 5 步的假设不成立：不存在双射 $A\to\wp(A)$。（依据：源文件 Remark 17 的分情形论证（casework）：若每种情形都导致结论/矛盾，则该结论必然成立。）
4. 等价地，任何 $g:A\to\wp(A)$ 都不是满射。（由第 5–9 步，反设”存在满射”（配合第 3 步的单射即可拼成双射）会导致矛盾。）
5. 结合第 3 步的 $\vert A\vert \le\vert \wp(A)\vert $ 与第 10 步的 $\vert A\vert \neq\vert \wp(A)\vert $，得到 $\vert A\vert <\vert \wp(A)\vert $。$\blacksquare$

把对角化写成一个表格（$A=\{1,2,3\}$ 的例子）：设 $g$ 由下表给出（$g(1)=\{1,2\}$，$g(2)=\varnothing$，$g(3)=\{1,2,3\}$）：

     对角化论证的"记账表"：行 = x ∈ A，列 = 问 "x ∈ g(x) 吗？"

    x  │  g(x)          │  x ∈ g(x) ?      │  x 要进 B 吗？
   ────┼────────────────┼──────────────────┼────────────────────
    1  │  {1, 2}        │   是（1 ∈ g(1)）  │   否
    2  │  ∅             │   否（2 ∉ g(2)）  │   是   ◄── 反对角线
    3  │  {1, 2, 3}     │   是（3 ∈ g(3)）  │   否
   ────┼────────────────┼──────────────────┼────────────────────
    ?  │  应当 = B      │    ？？？        │    ？？？
            （若 g 是满射，B 必须出现在这一列里，被某行 b 命中）

   由表算得 B = {2}，而 g 的像只有 {1,2}、∅、{1,2,3}，B 不在其中 ⟹ g 不是满射。
   若把某个 g'(b) 改成 {2} 来"打补丁"，B 会重新计算成别的集合，新表中又出现新的
   "未命中"——补丁永远打不完。

这里的关键是对角线：$B$ 的成员资格由”$x$ 与 $g(x)$ 的自身关系”决定——我们只查”$x$ 是否属于它自己的像”，其余行列的信息一概不看。这就是”对角化“这个名字的来源（把它想成一张无限大的表格，我们只看对角线上的格子，然后全部取反）。

【证明机制解说】

(1) 自指结构（罗素悖论的影子）。 命题”$x\notin g(x)$”里出现了两次 $x$：一次作为被检验的元素，一次作为问句的参数。这种”把自己套进自己”的结构就是自指。罗素（Bertrand Russell）当年问：集合 $R=\{x:x\notin x\}$ 是不是自己的元素？若 $R\in R$ 则 $R\notin R$；若 $R\notin R$ 则 $R\in R$——两头堵死，这就是罗素悖论。它说明”任意性质都能定义集合”（无限制概括）是不安全的。Cantor 定理的精妙之处在于：它把同一个自指结构限制在一个合法的集合 $A$ 内（$x$ 只在 $A$ 里取，$g(x)$ 也是 $A$ 的子集），所以 $B$ 是货真价实的集合，不会引发悖论；自指结构产生的矛盾被精确地转嫁给了“$g$ 是满射”这个假设。所以 Cantor 定理不是悖论，而是用悖论的火力去烧毁满射的存在性。

(2) 为什么 $B$ 依赖 $g$ 构造，所以 $g$ 不可能命中 $B$？ $B$ 的定义逐字逐句地使用了 $g$ 的取值：要知道 $x$ 是否属于 $B$，必须查 $g(x)$。因此 $B$ 是”为 $g$ 量身定做的“反例。这个量身定做的性质保证：任何一个候选的”原像” $b$（即声称 $g(b)=B$ 的那个 $b$）都会在它自己的位置上被卡住——因为 $B$ 在 $b$ 处的规定恰好是”$b\notin g(b)$”，而 $g(b)=B$，所以规定变成”$b\notin B$”，与 $g(b)=B$ 要求的”$b\in B$”正好相反。一个集合不可能同时满足 $b\in B$ 与 $b\notin B$，这就是全部的反驳力量。请注意这个反驳不需要知道 $g$ 的其他任何取值——它自动成立。

(3) 对角化思想的普遍性。 同一个骨架在数学与计算机科学中反复出现：“给定一份声称包罗万象的清单，我造一个对象，它在第 $n$ 位上与清单第 $n$ 项不同，于是它不在清单里。”

• Cantor 对角线（实数不可数）：清单是”所有实数的十进制展开”，第 $n$ 个实数的第 $n$ 位改掉，得到新实数不在清单里（Lecture 6 会讲）。
• 图灵停机问题（Turing, 1936）：假设存在程序 $H$ 能判定”程序 $P$ 在输入 $P$ 上是否停机”；构造程序 $D$：若 $H(P,P)$ 说”会停”就死循环，若说”不停”就停。再问 $H(D,D)$，两头矛盾。这里的 $D$ 就是 $B$。
• Gödel 不完备性（1931）：构造一个句子 $G$ 说”我在本系统中不可证”——$G$ 就是那个”在自身位置上取反”的对角元素。
• “不存在所有集合的集合”：取 $A=$ 一切集合，则 $\wp(A)$ 也是集合，故 $\wp(A)\subset A$，从而 $\vert \wp(A)\vert \le\vert A\vert $，与 Cantor 定理 $\vert A\vert <\vert \wp(A)\vert $ 矛盾——这是罗素悖论的另一副面孔。

(4) 这个证明在任何集合上都成立。 推导过程中除了”$A$ 是集合”以外没有用到 $A$ 的任何特殊性质：$A$ 可以有限、可以可数、可以不可数，$A$ 的元素甚至可以本身就是集合（$\wp$ 的迭代正是这种情况）。特别地，取 $A=\mathbb{N}$：立刻得到

\[\vert \mathbb{N}\vert <\vert \wp(\mathbb{N})\vert ,\]

即 $\wp(\mathbb{N})$ 是不可数集。这是本课程第一次证明”不可数”的存在：在此之前我们只证明了 $\mathbb{N}$、$\mathbb{Z}$、$\mathbb{Q}$ 可数；现在我们知道至少有一个集合比它们都大。再取 $A=\wp(\mathbb{N})$，得到 $\wp(\wp(\mathbb{N}))$ 更大……于是（源文件 Remark 16）

\[\vert \mathbb{N}\vert <\vert \wp(\mathbb{N})\vert <\vert \wp(\wp(\mathbb{N}))\vert <\cdots,\]

无穷集有无穷多个不同的”大小”，不存在”最大的集合”。这在 1874–1891 年由 Cantor 发现时震动了整个数学界，Hilbert 把它列为”没有比这更值得惊叹的数学成果”。

【证明技巧总结】

1. 把”$<$”拆成”$\le$ 且 $\neq$”：证明严格不等式时，先构造单向的单射（通常很容易），再把全部力气花在”不可能相等”上。这是本课程处理基数不等式的标准套路。
2. 对角化构造（反例依赖假设）：要证明”不存在满足性质 $P$ 的映射”，就假设存在 $g$，然后用 $g$ 自己定义一个对象，使其在每个位置上都与 $g$ 的行为相反。口诀：”照着你造，专门跟你不一样。”
3. 分情形穷尽（Remark 17 的方法论）：当需要检查”$b\in B$ 还是 $b\notin B$”时，老老实实把两种情形都写出来；只要每一支都矛盾，结论就是”假设不成立”。不要在没验证完所有分支前宣布矛盾。
4. 修改假设要重新计算构造：对角化反例依赖假设，所以”打补丁”（把 $B$ 塞进 $g$ 的值域）会使 $B$ 变成另一个集合 $B^{\prime}$，矛盾重新出现。这一”补丁永远打不完”的性质，是 Cantor 定理区别于”某个映射凑巧不满”的本质。

推论 18（Corollary 18）

• 定理陈述：对一切 $n\in\mathbb{N}\cup\{0\}$，

• 证明策略：直接引用 Theorem 15：取 $A=\{1,2,\dots,n\}$（$n=0$ 时取 $A=\varnothing$），则 $\vert A\vert =n$ 且 $\vert \wp(A)\vert =2^n$，由 $\vert A\vert <\vert \wp(A)\vert $ 即得。源文件 Remark 19 补充说”这也可以用归纳法证明，见 Assignment 1”。

• 逐步推导（$n\ge 1$ 的情形）：
  1. 令 $A=\{1,2,\dots,n\}$，则 $\vert A\vert =n$。（依据：有限集基数的定义。）
  2. $\wp(A)$ 恰有 $2^n$ 个元素：每个子集由”每个 $k\in\{1,\dots,n\}$ 是否入选”的 $n$ 位二进制选择唯一决定，共有 $2^n$ 种选择。（依据：乘法原理；这是源文件”$\vert A\vert =n\Rightarrow\vert \wp(A)\vert =2^n$”的证明思路。）
  3. 由定理 15，$\vert A\vert <\vert \wp(A)\vert $，即 $n<2^n$。（依据：定理 15。）
  4. 数值核对：$n=0,1,2,3,4,5$ 时 $2^n=1,2,4,8,16,32$，确实 $n<2^n$（$n=2$ 时 $2<4$ 是最”紧”的一档；$n=3$ 之后差距迅速拉开）。$\blacksquare$
• 【证明机制解说】：这个推论本身平凡（学生早在中学就知道 $n<2^n$），它的意义在于展示了定理 15 的一致性检验：Cantor 定理对有限集退化成我们熟悉的组合事实，说明它并没有把”大小”这个概念搞乱。
• 【证明技巧总结】：新定理的第一个应用应当是可验证的已知事实——用它去算一个你早就会算的例子，可以同时检验定理的正确性与自己对定义的理解。

定理 27（若 $\sup E$ 是 $\mathbb{Q}$ 中的数，则它的平方必为 $2$）

• 定理陈述：设

若 $x\in\mathbb{Q}$ 满足 $x=\sup E$，则

（源文件原文：”If $x\in\mathbb{Q}$ and $x=\sup\{q\in\mathbb{Q}\mid q>0,q^2<2\}$ then $x>0$ and $x^2=2$.”）

• 证明策略：这是一个”用两步夹逼确定一个等号“的证明，与 [JL] Example 1.2.3 完全同构。要证 $x^2=2$，就分别证 $x^2\ge 2$ 与 $x^2\le 2$（实数/有理数上 $\le$ 是反对称的，两向夹住即等号）。两半都用反证 + 构造性修正：
  • 若 $x^2<2$：造一个 $h>0$，使 $x+h\in E$ 且 $x+h>x$，直接否证”$x$ 是上界”。这就是“上界不够高”要挨打。
  • 若 $x^2>2$：造一个 $h>0$，使 $x-h$ 仍是 $E$ 的上界，但 $x-h<x$，否证”$x$ 是最小的上界”。这就是“上界太高”要挨打。

  两个修正量 $h$ 的选取遵循同一原则：让一阶项恰好吃掉一半的差距，用一个固定约束（$h<1$）吸收二阶余项。

• 逐步推导：

  第 0 步（把 $E$ 看清楚）：$1\in E$，因为 $1>0$ 且 $1^2=1<2$。所以 $E\neq\varnothing$。$2$ 是 $E$ 的上界，因为对任意 $q\in E$ 有 $q^2<2<4=2^2$，而 $q>0$，所以 $q<2$。（依据：正数比较大小可以平方/开方——特别地 $0<q<2\Rightarrow q^2<4$。）

  第一部分：$x>0$。

  1. 因为 $1\in E$ 且 $x$ 是 $E$ 的上界，由上界定义得 $1\le x$。（依据：上界定义 (Definition 24)。）
  2. 于是 $x\ge 1>0$，即 $x>0$。（依据：序的传递性；(1) 与 $1>0$。）特别地，$x\neq 0$，这保证下面可以作分母。

  第二部分：$x^2\ge 2$。

  1. 反设 $x^2<2$。则 $2-x^2>0$。（依据：假设 + 序的相容性。）
  2. 定义

1. 两个候选数都为正：$\frac12>0$；$\frac{2-x^2}{2(2x+1)}>0$ 因为分子 $2-x^2>0$（第 3 步）而分母 $2(2x+1)>0$（第 2 步 $x>0$）。故 $h>0$。（依据：正数的 $\min$ 为正。）
2. 同时 $h\le\frac12<1$。（依据：$\min$ 的定义。）这个”$h<1$”是后面吸收 $h^2$ 的钥匙。
3. 展开并估计：

第二步用了 $h^2<h$，它来自 $0<h<1$（第 6 步）。（依据：$h^2=h\cdot h<h\cdot 1=h$，因为 $h>0$ 且 $h<1$。）

1. 再用 $h\le\frac{2-x^2}{2(2x+1)}$ 与 $2x+1>0$，两边乘以 $2x+1$ 得 $h(2x+1)\le\frac{2-x^2}{2}$。于是

最后一步用 $x^2<2$。（依据：第 3 步的假设 + 代数变形。）

1. 因此 $(x+h)^2<2$，且 $x+h>x>0$，所以 $x+h\in E$。（依据：$E$ 的定义；$x+h>0$ 由 $x>0,h>0$ 得。）
2. 但 $x+h>x$，说明 $x$ 不是 $E$ 的上界，与第 0 步的”$x=\sup E$ 是上界”矛盾。（依据：上界定义 + $x=\sup E$ 蕴含 $x$ 是上界。）故假设不成立：

第三部分：$x^2\le 2$。

1. 反设 $x^2>2$。则 $x^2-2>0$。（依据：假设。）
2. 定义

\(h:=\frac{x^2-2}{2x}>0.\) （依据：分子、分母均为正，第 2 步已保证 $x>0$。）

1. 验证 $x-h>0$：

\(x-h=x-\frac{x^2-2}{2x}=\frac{2x^2-(x^2-2)}{2x}=\frac{x^2+2}{2x}>0.\) （依据：通分 + 代数；分子 $x^2+2>0$，分母 $2x>0$。）

1. 计算 $(x-h)^2$。注意 $2xh=2x\cdot\frac{x^2-2}{2x}=x^2-2$，故

\((x-h)^2=x^2-2xh+h^2=x^2-(x^2-2)+h^2=2+h^2>2.\) （依据：代数变形 + $h^2>0$。）这一步的设计意图很清楚：$h$ 被恰好选定为使 $(x-h)^2$ 偏离 $2$ 的量正好是 $h^2$，从而严格大于 $2$。

1. 现在证明 $x-h$ 是 $E$ 的上界。任取 $q\in E$。由 $E$ 的定义 $q^2<2$，而第 14 步给出 $2<(x-h)^2$，所以

\(q^2<(x-h)^2,\qquad\text{即}\qquad (x-h)^2-q^2>0.\) （依据：序的传递性 + 移项。）

1. 因式分解：$(x-h)^2-q^2=(x-h-q)(x-h+q)$。（依据：平方差公式。）
2. 由第 13 步 $x-h>0$、由 $q\in E$ 有 $q>0$，所以 $x-h+q>0$。（依据：正数之和为正。）
3. 两个因子乘积 $>0$ 而其中一个因子 $x-h+q>0$，故另一个因子必 $>0$：

\(x-h-q>0,\qquad\text{即}\qquad q<x-h.\) （依据：正数除正数仍为正——在不等式两边同除以正数 $x-h+q$ 保持方向。）

1. 由于 $q\in E$ 是任取的，第 18 步说明 $x-h$ 是 $E$ 的上界。（依据：上界的定义。）
2. 但由 $h>0$ 得 $x-h<x$。一个比 $x$ 更小的上界存在，与”$x$ 是最小上界”矛盾。（依据：上确界定义的条件 (B)：$x=\sup E$ 必须 $\le$ 一切上界，特别地 $x\le x-h$，与 $x-h<x$ 矛盾。）故假设不成立：

第四部分：合并。

1. 由第 10 步与第 20 步，$x^2\ge 2$ 且 $x^2\le 2$，由序的反对称性得 $x^2=2$。（依据：$\le$ 的反对称性。）结合第一部分 $x>0$，定理证毕。$\blacksquare$

源文件勘误：源文件在证明第一部分的末尾把 “(x+h)^2<x^2+(2-x^2)\cdot\frac{2x+1}{2(2x+1)}=x^2+\frac{2-x^2}{2}<2+\frac{2-2}{2}=2” 写成了一串不太顺畅的式（末尾的 “$2+\frac{2-2}{2}$” 应为 $\frac{2+x^2}{2}<2$）；在第二部分把因式分解写成了 “$((x-h)+q)((x-h)+q)>0$”，第二个因子应为 $(x-h)-q$。本文采用的是修正后的正确推导，结论与源文件完全一致。

• 【证明机制解说】
  • “两步夹逼”是分析学证等号的标准姿势。 $a=b$ 拆成 $a\le b$ 与 $b\le a$；这里目标 $x^2=2$ 就攻 $x^2\ge2$ 与 $x^2\le2$。请当成肌肉记忆：看到等号，先问”两个方向的不等式分别怎么来”。（[JL] Example 1.2.3 也强调”analysts show equality by showing two inequalities”。）
  • 修正量 $h$ 不是”从帽子里变出来的”：它是反推出来的。要 $(x+h)^2<2$，展开得 $2xh+h^2<2-x^2$。$h$ 小时左边几乎是 $2xh$，第一反应是取 $h<\frac{2-x^2}{2x}$；但分母含 $x$（我们只知道 $x>0$），不好控制。于是改用放缩：$h<1$ 时 $h^2<h$，故 $2xh+h^2<h(2x+1)$，分母换成常数 $2x+1>0$，条件变为 $h\le\frac{2-x^2}{2(2x+1)}$；同时为用 $h^2<h$ 还需 $h<1$，取 $\min\{\frac12,\cdot\}$ 一并满足。先写目标不等式 → 展开 → 放缩掉高阶项 → 解出 $h$ 的范围，这就是构造的全部逻辑。
  • 为什么第一半用 $x+h$、第二半用 $x-h$？ 因为 $\sup$ 定义有两条：(A) 是上界，(B) 是最小上界。$x^2<2$ 时造出 $x+h\in E$ 打破 (A)；$x^2>2$ 时造出更小上界 $x-h$ 打破 (B)。这正是”分类讨论 $x^2<2$ / $x^2>2$”的动机：$x^2\neq2$ 的两个失败模式，恰好分别对应 $\sup$ 定义的两条条件。
  • 为什么不可能 $x^2=2$ 在 $\mathbb{Q}$ 中发生？ 这正是下一节 Theorem 28 的内容：$\mathbb{Q}$ 中没有平方为 $2$ 的数。Theorem 27 说”$\sup E$ 若存在则平方必为 $2$”，Theorem 28 说”$\mathbb{Q}$ 中不存在平方为 $2$ 的数”，两条合起来就是”$\sup E$ 在 $\mathbb{Q}$ 中不存在”。这是典型的”归约”策略：把一个关于 $\sup$ 存在问题，归约成一个关于方程 $x^2=2$ 的问题。
• 【证明技巧总结】
  1. 两步夹逼证等号：$a=b\iff(a\le b\ \text{且}\ b\le a)$。反向不等式的证法通常是”若严格不等则构造出与定义矛盾的对象”。
  2. $\min\{1,\cdot\}$ 吸收高阶项：在本课程中要估计含 $h^2,h^3$ 的表达式时，约定 $h<1$（或 $h<\frac12$）先把高次项压成一次项：$h^2<h$、$h^3<h$。这个技巧在 Taylor 定理、级数估计里反复出现。
  3. 使误差恰好减半：选取 $h\le\frac{2-x^2}{2(2x+1)}$（分子带 $\frac12$）保证修正后的量严格小于”半路”的位置，从而留出安全余量，绝不出现等号临界。
  4. 因子符号判定：$A^2-q^2>0$ 且 $A+q>0$ $\Rightarrow A-q>0$。只要乘积为正、且一个因子为正，另一个必为正（”同号”推理）。
  5. 反推构造：先写出你想要的结论（$(x+h)^2<2$），展开、放缩，倒推出 $h$ 应满足的充分条件。写证明时按”定义 $h$ → 验证条件 → 推出结论”的顺序，倒推过程不必写出来（[JL] 明确提醒：”the order in which we write the proof is not necessarily the order in which we come up with the proof”）。

定理 28（$\mathbb{Q}$ 不具备最小上界性质）

• 定理陈述：集合

在 $\mathbb{Q}$ 中没有上确界。（源文件原文：”The set $E=\{q\in\mathbb{Q}\mid q>0\text{ and }q^2<2\}$ does not have a supremum in $\mathbb{Q}$.”）

• 证明策略：反证法 + 良序原理（well-ordering principle）+ 无穷递降（infinite descent）。计划：

  1. 反设存在 $x\in\mathbb{Q}$ 使 $x=\sup E$；
  2. 由 Theorem 27 得 $x^2=2$，即”$\mathbb{Q}$ 中有一数平方为 $2$”；
  3. 记 $x=\frac mn$。关键是用 $\sup$ 信息换来一个新的、更小的、同类型的整数：由 $x^2=2$ 与 $x>1$ 造出 $k_0$ 的一个”下降” $k_1<k_0$；
  4. 用良序原理说”不存在这样的下降”（最小元不能再小），矛盾。

  为什么选这个策略？因为我们没有任何关于 $\mathbb{Q}$ 的代数”素性”就可以直接下手（那需要唯一分解），但 Lecture 1 已证明了 $\mathbb{N}$ 的良序原理：$\mathbb{N}$ 的每个非空子集有最小元。于是把”$\mathbb{Q}$ 中方程无解”翻译成”$\mathbb{N}$ 的某个非空子集没有最小元”，即得矛盾。这种”把有理数问题转化为整数问题，再用良序原理砍断“的手法，是数论与分析的经典桥梁。

• 逐步推导：

  1. 反设存在 $x\in\mathbb{Q}$ 使 $x=\sup E$。（依据：反证假设。）
  2. 由定理 27，$x^2=2$ 且 $x>0$。（依据：定理 27。）
  3. 于是 $x>1$。理由：若 $x\le 1$，则由 $0<x\le1$ 得 $x^2\le 1<2$，与 $x^2=2$ 矛盾。（依据：正数平方保序 + $1^2=1$。）
  4. 因 $x$ 是正有理数，存在 $m,n\in\mathbb{N}$ 使 $x=\frac mn$，且可取 $m>n$（因为 $x>1$，$x=\frac mn>1\Rightarrow m>n$）。（依据：正有理数的定义 $\mathbb{Q}=\{\frac mn:m,n\in\mathbb{N}\}$。）
  5. 特别地，$n x=m\in\mathbb{N}$，故 $n\in S$（依据：$S$ 的定义），于是 $S\neq\varnothing$。

\(S:=\{k\in\mathbb{N}:kx\in\mathbb{N}\}.\)

1. 由 $\mathbb{N}$ 的良序原理，$S$ 有最小元；记作 $k_0\in S$。（依据：Lecture 1 的良序原理：$\mathbb{N}$ 的每个非空子集有最小元。）这是整个证明的枢纽：我们要让 $k_0$ 与一个更小的同类元素共存，从而违反最小性。
2. 定义

由 $k_0x\in\mathbb{N}$（因为 $k_0\in S$）与 $k_0\in\mathbb{N}$ 得 $k_1\in\mathbb{Z}$。（依据：整数对减法封闭。）

1. 又 $k_1=k_0(x-1)>0$，因为 $k_0\in\mathbb{N}$ 即 $k_0\ge1>0$，而第 3 步给出 $x-1>0$。

\(k_1\in\mathbb{N}.\) （依据：正数之积为正。）结合 $k_1\in\mathbb{Z}$，得（依据：正整数 $=$ 正整数的定义。）

1. 再看 $x<2$。理由：若 $x\ge 2$，则 $x^2\ge 4>2$，与 $x^2=2$ 矛盾。（依据：平方保序 + $2^2=4$。）
2. 于是

因为 $k_0>0$ 且 $x-1<2-1$。（依据：不等式两边同乘正数 $k_0$ 保持方向。）

1. 由第 8 步 $k_1\in\mathbb{N}$、第 10 步 $k_1<k_0$、以及第 6 步 $k_0$ 是 $S$ 的最小元，得

\(k_1\notin S.\) （依据：最小元的定义：$S$ 中任何元素都 $\ge k_0$。）

1. 但另一方面，直接计算：

\(x\,k_1=x\,(k_0x-k_0)=k_0x^2-xk_0\overset{x^2=2}{=}2k_0-xk_0=k_0-k_1.\) （依据：代数变形 + 第 2 步 $x^2=2$。）

1. 由第 8 步 $k_1\in\mathbb{N}$、第 10 步 $k_1<k_0$ 得 $k_0-k_1\in\mathbb{Z}$ 且 $k_0-k_1>0$，故 $k_0-k_1\in\mathbb{N}$。（依据：正整数定义。）
2. 于是 $x k_1=k_0-k_1\in\mathbb{N}$，且 $k_1\in\mathbb{N}$，按 $S$ 的定义得

\(k_1\in S.\) （依据：$S=\{k\in\mathbb{N}:kx\in\mathbb{N}\}$。）

1. 第 11 步说 $k_1\notin S$，第 14 步说 $k_1\in S$，矛盾。（依据：排中律。）因此第 1 步的反设不成立：不存在 $x\in\mathbb{Q}$ 使 $x=\sup E$。$\blacksquare$

源文件勘误：源文件写 “$k_1=k_0x-k_0\in\mathbb{Z}$” 后紧接着说 “$k_1=k_0(x-1)>0$ since $k_0\in\mathbb{N}$ and $x>1$”，逻辑无误；但它把 “$x<2$” 的理由写成 “$x^2=2\Rightarrow x<2$，as otherwise $x^2>4>2$”，严格说应为 $x\ge2\Rightarrow x^2\ge4>2$（$x=2$ 时 $x^2=4$，取”$>$”仍然成立，故不影响结论）。本文已按严格写法处理。

• 【证明机制解说】
  • “洞”的图像。 把 $\mathbb{Q}$ 想成一根满是刻度、却到处是针眼小孔的直线。$E$ 就是”$\sqrt2$ 左边的全部正有理数”，有上界（$2$、$\frac32$、$\frac{99}{70}$ 都是），但”最低天花板”恰好落在孔里——$\sqrt2\notin\mathbb{Q}$。于是“有上界”却”没有上确界”不是悖论，而是这个宇宙真的缺了一个点。

      ℚ 数轴上的"洞"：E = {q ∈ ℚ : q > 0, q² < 2}
    
     E 里的数在这边                                    上界在那边
    ◄──────────────────────────────────────────┤        ┤──────────►
     0.5  1.0  1.2  1.4 1.41 1.414 1.4142 …    │  √2    │ 1.5   2
                                               ▲        ▲
                                      E 的"右端点"   E 的一个粗上界
                                       （ℚ 里不存在！）
    ────────────────────────────────────────────────────────────────
    在 ℚ 中取任意 x：
      x² < 2 ⟹ ∃h>0 使 x+h ∈ E 且 x+h > x   ⟹ x 不是上界！
      x² > 2 ⟹ ∃h>0 使 x−h 仍是 E 的上界     ⟹ x 不是最小上界！
    唯有 x² = 2 才两全，可 √2 ∉ ℚ ⟹ E 在 ℚ 中无 sup ⟹ ℚ 不具备 LUB 性质。
    

  • Theorem 27 与 Theorem 28 的分工：前者是纯分析的（$h$ 微调证”候选者必须平方为 $2$”，只用序与代数），后者是纯数论/良序的（证”$\mathbb{Q}$ 中无平方为 $2$ 之数”）。合起来即得不存在性。“分析管长什么样，数论管不存在”，切分之后每一步都简单。
  • 为什么用良序原理而不是”无穷递降”？ 第 6–15 步其实在演示一个永动机式的荒谬：从 $x^2=2$ 出发，我们总能从 $S$ 的一个元素 $k_0$ 造出更小的同类元素 $k_1\in S$，于是可以无限重复 $k_0>k_1>k_2>\cdots$，全是正整数——这与”正整数不能无限下降”相矛盾。良序原理正是”不能无限下降”的精确定形式。记住这条等价链：良序原理 ⟺ 数学归纳法 ⟺ 不存在 $\mathbb{N}$ 中的无穷严格递降序列。
  • “如果让你自己重新发明这个证明”：先问”$\sqrt2\notin\mathbb{Q}$ 怎么证？”标准答法是用 $x=\frac mn$ 约分后得出 $m,n$ 都能被 $2$ 整除，矛盾（[JL] Example 1.1.4）。但那要求”最简分数”这种表示论事实。而这里我们只用良序原理与 $S=\{k:kx\in\mathbb{N}\}$ 的最小元，本质上等价于”分母取最小”，但完全避开了素因子分解。凡是形如”存在分母最小的表示”的论证，都是良序原理在岗。
  • 这个结论的意义。 $\mathbb{Q}$ 有加法、乘法、除法（除零）、有完备的比大小规则、还是”稠密”的（任两数之间有无穷多有理数），但它们不足以支撑分析学：$E$ 连一个上确界都拿不出。$\mathbb{Q}$ 对代数家够用（源文件与 [JL] 都这样评价），对分析家不够用——因为分析学需要大量地、随意地取上确界（”take suprema willy-nilly”，[JL] §1.2 语）。这就是我们必须造出 $\mathbb{R}$ 的原因，也是 Lecture 4 的全部动机。
• 【证明技巧总结】
  1. 把 $\sup$ 问题归约为方程问题：先证”若 $\sup$ 存在则必满足方程 $P$”（Theorem 27），再证”$\mathbb{Q}$ 中方程 $P$ 无解”（Theorem 28）。
  2. 良序原理 + 最小元制造矛盾：想证明某类正整数表示不存在，就取”分母最小”的表示 $k_0$，再构造一个更小的 $k_1$，与最小性冲突。这是无穷递降的标准化写法。
  3. 反证时把所有”必须成立”的量算出来备用：本证明一开始就囤积了 $x>0$（来自 $1\in E$）、$x>1$（来自 $x^2=2$ 且 $x\le1$ 会矛盾）、$x<2$（来自 $x\ge2$ 会矛盾）、$x\in\mathbb{Q}$ 的三个事实，后面每一步都正好用上一条。反证前先把候选对象的性质榨干，是写这类证明的实用习惯。
  4. 两个 $k$ 的恒等式是设计的核心：$xk_1=k_0-k_1$ 之所以漂亮，全因 $x^2=2$ 把 $k_0x^2$ 换成了 $2k_0$。这种”用方程把平方项换成常数项”的手法，在代数数论（$\mathbb{Z}[\sqrt2]$ 的范数论证）中也会重现。

【补充】命题：上确界的 $\epsilon$-刻画（”两步法”的完整形式）

源文件在定义了 $\sup$ 之后就直接去证明 Theorem 27/28，没有单列这条命题；但它是 Lecture 3 全部技术中使用频率最高的一条，也是 OCW Assignment 3 第 4 题要求证明的内容（原题：”Let $A$ be a subset of $\mathbb{R}$ which is bounded above, and let $a_0$ be an upper bound for $A$. Prove that $a_0=\sup A$ if and only if for every $\epsilon>0$, there exists $a\in A$ such that $a_0-\epsilon<a$.”）。因此把它作为【补充】命题完整写在这里。

• 命题陈述：设 $A\subset\mathbb{R}$ 非空且有上界，$a_0$ 是 $A$ 的一个上界。则

（右端的等价写法：$\forall\epsilon>0,\ A\cap(a_0-\epsilon,a_0]\neq\varnothing$；也就是”$A$ 中有元素能任意逼近 $a_0$ 的左邻域”。）

• 证明策略：这是一个”$\iff$”，两个方向分别打 $\sup$ 定义的两个条件：
  • ($\Longrightarrow$) 条件 (B) 说”$a_0$ 是最小的上界”。要证明”没有比 $a_0$ 更小的上界”，最直接的方式就是反证：若某个 $a_0-\epsilon$ 竟然也是上界，就与 (B) 冲突。这是典型的”把 $\forall\exists$ 的否定写出来再用最小性击落“。
  • ($\Longleftarrow$) 已知 (A)（$a_0$ 是上界），只需证 (B)。仍用反证：若某个上界 $b$ 比 $a_0$ 小，那么 $\epsilon:=a_0-b>0$，而命题条件保证 $A$ 中有一个元素超过 $b$——直接打破”$b$ 是上界”。

• 逐步推导：

  方向一（$\Longrightarrow$）：设 $a_0=\sup A$，证明 $\forall\epsilon>0\ \exists a\in A,\ a_0-\epsilon<a$。

  1. 取任意 $\epsilon>0$。（依据：要证”$\forall\epsilon>0$”，故 $\epsilon$ 是任给但固定的。）
  2. 反设不存在这样的 $a$，即 $\forall a\in A$，$a\le a_0-\epsilon$。（依据：$\exists a\in A,\ a>a_0-\epsilon$ 的否定。）
  3. 第 2 步说明 $a_0-\epsilon$ 是 $A$ 的一个上界。（依据：上界的定义 (Definition 24)。）
  4. 但 $a_0-\epsilon<a_0$（因为 $\epsilon>0$），于是存在一个比 $a_0$ 更小的上界。（依据：$\epsilon>0\Rightarrow a_0-\epsilon<a_0$。）
  5. 这与 $a_0$ 是最小上界（条件 (B)）矛盾。（依据：条件 (B) 要求 $a_0\le$ 一切上界，特别地 $a_0\le a_0-\epsilon$，与第 4 步矛盾。）
  6. 所以反设不成立，存在 $a\in A$ 使 $a_0-\epsilon<a$。（依据：反证法。）因 $\epsilon$ 任取，方向一得证。

  方向二（$\Longleftarrow$）：设 $a_0$ 是上界且条件成立，证明 $a_0=\sup A$。

  1. 条件 (A) 已由假设给出：$a_0$ 是 $A$ 的上界。（依据：命题假设。）
  2. 证明条件 (B)：设 $b$ 是 $A$ 的任一上界，要证 $a_0\le b$。（依据：$\sup$ 定义的条件 (B)。）
  3. 反设 $b<a_0$，令 $\epsilon:=a_0-b>0$。（依据：正数的定义。）
  4. 由命题条件（取这个 $\epsilon$），存在 $a\in A$ 使

\(a>a_0-\epsilon=a_0-(a_0-b)=b.\) （依据：命题的右端条件 + 代数。）

1. 但 $b$ 是上界意味着 $\forall a\in A,\ a\le b$，与 $a>b$ 矛盾。（依据：上界的定义。）
2. 故 $b<a_0$ 不成立，即 $a_0\le b$。由 $b$ 是任一上界，条件 (B) 成立。（依据：反证法 + $\le$ 的三歧性。）
3. 由第 7、12 步，$a_0$ 满足 (A) 与 (B)，故 $a_0=\sup A$。$\blacksquare$
   • 具体示例（把 $\epsilon$ 取成具体数字）：取 $A=\left\{1-\frac1n:n\in\mathbb{N}\right\}$，$a_0=1$。
     • 我们可以先直接验证 $1=\sup A$：$1-\frac1n<1$ 说明 $1$ 是上界；对任意 $\epsilon>0$，要 $1-\frac1n>1-\epsilon$ 只需 $\frac1n<\epsilon$，即 $n>\frac1\epsilon$。取 $\epsilon=0.001=\frac{1}{1000}$，则需 $n>1000$，取 $n=1001$：

（已用 Python 精确有理数核对：$1-\frac{1}{1001}>\frac{999}{1000}$ 成立。）

• 再取 $\epsilon=0.01=\frac{1}{100}$，则需 $n>100$，取 $n=101$：$a=1-\frac{1}{101}\approx0.990099>0.99=a_0-\epsilon$ ✓。
• 取 $\epsilon=10^{-6}$，取 $n=10^6+1$：$a=1-\frac{1}{10^6+1}\approx0.999999000001>0.999999$ ✓。

• 反过来说，任何 $\epsilon>0$ 都做得到——正因如此，$A$ 中的元素能”任意逼近 $1$”却永远取不到 $1$。这就是”$1=\sup A$ 且 $1\notin A$”的精确含义。

• 反例（说明”$a_0$ 是上界”这一假设不可省）：取 $A=(0,1)$，$a_0=7$。$7$ 是上界吗？是（$\forall a\in A,\ a<1<7$）。它满足 $\epsilon$-条件吗？取 $\epsilon=1$：需要 $a>7-1=6$ 的 $a\in A$，不存在。所以条件失败，而 $7\neq\sup A=1$——两边一致。（此例说明：命题里的”$a_0$ 是上界”是前提，去掉它，$\Longleftarrow$ 方向第 7 步就无法起步。）

• 反例（说明 $\epsilon$ 必须”对一切正数”）：只对某一个 $\epsilon>0$ 成立是不够的。取 $A=(0,1)$，$a_0=1$，取固定的 $\epsilon=2$：存在 $a\in A$ 使 $a>1-2=-1$（比如 $a=\frac12$），条件”成立”，但若允许这样放松，$a_0=1$ 与 $A=(0,1)$ 的 $\sup$ 是对的，看不出问题。换个例子：$A=(0,1)$，$a_0=3$，取固定的 $\epsilon=5$：存在 $a>3-5=-2$ ✓，条件”成立”，但 $3\neq\sup A$。所以量词必须是 $\forall\epsilon>0$（对一切不论多小的 $\epsilon$）；这正是”任意逼近”的技术含义。

  【证明机制解说】

  (1) 为什么”$\epsilon$-刻画”如此重要？ 因为 $\sup$ 的定义 (B) 说的是”$\forall$ 上界 $b$，$a_0\le b$”——这是一个关于上界集合的陈述，用起来要先”把上界集合想清楚”。而 $\epsilon$-刻画把它换成了”$\forall\epsilon>0\ \exists a\in A$，$a>a_0-\epsilon$”——这是一个关于 $A$ 内部元素的陈述。后者在实践中好用得多：你不需要知道 $A$ 的所有上界是谁，只需要在 $A$ 里造出一个逼近 $a_0$ 的元素。

  (2) 直觉图像：$\sup$ 是”被 $A$ 从左边无限逼近的墙”。 墙是 $a_0$；对任意小的 $\epsilon>0$，$A$ 都有一只手伸进 $(a_0-\epsilon,a_0]$ 这个窗口里。$\epsilon$ 越小，窗口越窄，但 $A$ 总能伸手进来。

       ε-刻画示意：A = {1 - 1/n}，a₀ = 1（"最低的天花板"，1 ∉ A）
  
     A 中的点：●──●──●─●─● ● ● ● ● │   (点可以任意接近 1 却取不到 1)
               0  0.5 0.9 0.99 0.999 …│
                                      ↑ a₀ = 1  ← 墙
     ε = 0.01  窗口 (0.99, 1]  ⟵ A 中 0.990099… 落在里面 ✓
     ε = 0.001 窗口 (0.999, 1] ⟵ A 中 0.999001… 落在里面 ✓
     ε → 0     窗口无限变窄，A 永远有元素落进去 ⟹ a₀ = sup A
  

  (3) “两步法”就是这条命题的模板。 要证 $s=\sup S$，就做两件事：

  • 第 1 步（证 $s$ 是上界）：$\forall x\in S$，$x\le s$。这一步通常靠”减法为正”或”两边平方”等单调性。
  • 第 2 步（证没有更小的上界）：$\forall\epsilon>0\ \exists x\in S$，$x>s-\epsilon$。这一步是构造性的：给定 $\epsilon$，你要动手造出那个 $x$（常常带 $n$ 或 $h$）。

  请注意第 2 步不是“证不存在更小的上界”这种空洞的否定，而是要产出一个具体的元素。凡是”证 $\sup$”的题，只要套这个模板，就不会找不到方向。

  【证明技巧总结】

  1. $\sup$ 两步法（必须背下来）：① $s$ 是上界；② $\forall\epsilon>0\ \exists x\in S,\ x>s-\epsilon$。等价地：① $\forall x\in S,\ x\le s$；② 对每个比 $s$ 小的候选 $b<s$，都在 $S$ 中找到一个元素超过 $b$（取 $\epsilon=s-b$）。
  2. 证明”$a_0$ 是最小的上界”就反设”有一个更小的上界”：把否命题写具体（”$a_0-\epsilon$ 是上界”或”某个 $b<a_0$ 是上界”），再推出与上界定义冲突。这是本课程否定型命题的通用打法。
  3. 否定 $\forall\epsilon\exists x$ 要小心：$\neg\big(\forall\epsilon>0\ \exists x\in S,\ x>s-\epsilon\big)$ 等于 $\exists\epsilon>0\ \forall x\in S,\ x\le s-\epsilon$。注意 $\exists$ 与 $\forall$ 交换了位置、不等号方向翻转。量词顺序写错就会得到”$\exists\epsilon$ 使一切成立”这种错误结论（见下文”常见误区”）。
  4. 把 $\epsilon$ 当”预算”来花：通常先让 $\epsilon>0$ 任给，最后用一个关于 $\epsilon$ 的显式构造（含 $n>\frac1\epsilon$、$h\le\frac{\epsilon}{C}$ 之类）收尾。养成”$\epsilon$ 是给你的，$n/h$ 是你选的”这一角色分工意识。

【补充】同一技巧的另一副面孔：Assignment 2 第 7 题（立方根版）

本小节不是 Lecture 3 的源文件定理，而是 OCW Assignment 2 第 7 题：它要求把 Theorem 27 / [JL] Example 1.2.3 的技巧从平方推广到立方，最能检验你是否真的掌握了”反推构造 $h$”这套机制（Hint 明说：”Adapt the proof used in Example 1.2.3.”）。

题目：设 $E=\{x\in\mathbb{R}:x>0\ \text{且}\ x^3<2\}$。(a) 证明 $E$ 有上界。(b) 令 $r=\sup E$（由 (a) 及 LUB 性质存在），证明 $r>0$ 且 $r^3=2$。

(a) 的证明：任取 $x\in E$，则 $x^3<2<8=2^3$。由 $x>0$ 与立方在正数上保序，$x<2$。所以 $2$ 是 $E$ 的上界。（另外 $1\in E$，故 $E\neq\varnothing$，$r$ 确实存在。）

(b) 的证明（$r^3\ge2$ 的一半）：$1\in E$ 且 $r$ 是上界 $\Rightarrow r\ge1>0$。反设 $r^3<2$，取

用二项式展开 $(r+h)^3=r^3+3r^2h+3rh^2+h^3$，并在 $0<h<1$ 时放缩高阶项（因 $h^2<h$、$h^3<h$）：

于是

所以 $r+h\in E$ 且 $r+h>r$，$r$ 不是上界，矛盾。故 $r^3\ge2$。（放缩规律：三阶余项的系数 $3r^2+3r+1$ 恰是 $(r+1)^3-r^3$；一般地 $0<h<1$ 时 $(r+h)^n-r^n<h\big((r+1)^n-r^n\big)$。）

数值走一遍：取 $r=\frac54=1.25$，$r^3=1.953125<2$。此时 $\frac{2-r^3}{2(3r^2+3r+1)}=\frac{0.046875}{18.875}\approx0.0024834$，故 $h\approx0.0024834$，$r+h\approx1.2524834$，$(r+h)^3\approx1.9647893<2$ ——确实仍在 $E$ 中且更大。（Python 精确有理数核对：$h=\frac{3}{1208}$，$(r+h)^3<2$ 成立。）

(b) 的证明（$r^3\le2$ 的一半）：反设 $r^3>2$，取 $h:=\dfrac{r^3-2}{3r^2}>0$。先验证 $r-h$ 仍是正数：

（分子 $2r^3+2>0$ 因 $r>0$，分母 $3r^2>0$）。再作一个配方式的恒等变形——本节最漂亮的技巧：

（最后一个等号是因为 $3rh^2-h^3=h^2(3r-h)$。）而 $h^2>0$（因 $h>0$），且 $3r-h>0$（因 $h<3r\iff r^3-2<9r^3\iff -2<8r^3$，由 $r>0$ 成立），所以 $h^2(3r-h)>0$，于是

现在证明 $r-h$ 是 $E$ 的上界：任取 $q\in E$，则 $q^3<2<(r-h)^3$；令 $A:=r-h>0$，由 $0<q$ 与 $q^3<A^3$ 得 $q<A$（否则 $q\ge A>0$ 会给出 $q^3\ge A^3$，矛盾）。由于 $q\in E$ 任取，$r-h$ 是 $E$ 的上界；而 $r-h<r$，与 $r=\sup E$ 的最小性（条件 (B)）矛盾。故 $r^3\le2$。

数值走一遍：取 $r=\frac{13}{10}=1.3$，$r^3=2.197>2$。此时 $h=\frac{197}{5070}\approx0.0388560$，$r-h\approx1.2611440>0$，$(r-h)^3\approx2.0058295>2$ ✓，且 $2+h^2(3r-h)\approx2.0058295$ 与 $(r-h)^3$ 完全吻合 ✓（已用 Python 精确有理数核对）。

两半合并得 $r^3=2$，即 $r=\sqrt[3]{2}$。这道题证明了 $\mathbb{R}$ 中 $\sqrt[3]2$ 的存在性，同时再次说明：把 $2$ 换成 $\sqrt2$、把 $2$ 次换成 $3$ 次，LUB 性质照样给你答案——但换成 $\mathbb{Q}$，两样都拿不到（Theorem 28 的立方版同样成立）。

与教材的对应

源文件编号对照速查：本讲官方编号为 Question 14、Theorem 15、Remark 16、Remark 17、Corollary 18、Remark 19、Remark 20、Problem 21、Theorem 22、Definition 23、Definition 24、Example 25、Definition 26、Theorem 27、Theorem 28。

• 对应 [JL] §1.1 “Basic properties”（1.5 讲）：其 Definition 1.1.1 / 1.1.2 / 1.1.3 就是源文件 Definition 23 / 24 / 26，逐一对应（见上表）。两点补充：
  • [JL] 明确指出 $\sup E$、$\inf E$ 若存在则自动唯一（这正是本文在”上确界”小节补的【补充命题】）；并提醒 LUB 性质又名 completeness property 或 Dedekind completeness property（以 Richard Dedekind 命名）——这个”又名完备性”很重要：Lecture 10 的 Cauchy 完备性与它是同一件事的两种说法。
  • [JL] Example 1.1.4 用最简分数反证 $\sqrt2\notin\mathbb{Q}$（$m^2=2n^2\Rightarrow m,n$ 皆偶，与最简矛盾）。这与本讲 Theorem 28 用良序原理的证法结论相同、路子不同，建议两种都会。
• 对应 [JL] §1.2 “The set of real numbers”（2 讲），该节给出：
  • Theorem 1.2.1 = 源文件 Theorem 22（存在唯一的含 $\mathbb{Q}$ 且具 LUB 性质的有序域 $\mathbb{R}$）。
  • Proposition 1.2.2：若 $x\le\epsilon$ 对一切 $\epsilon>0$ 成立，则 $x\le 0$。这是分析学证明非严格不等式的万能工具，与本文的 $\epsilon$-刻画互为表里。
  • Example 1.2.3（= 源文件 Theorem 27 的 $\mathbb{R}$ 版）：Claim 是”存在唯一的正实数 $r$ 使 $r^2=2$，记作 $\sqrt2$”。证明结构逐字对应：取 $A=\{x:x^2<2\}$、$r:=\sup A$，分 $r^2\ge2$（用 $h<\frac{2-s^2}{2s+1}$ 造 $s+h\in A$）与 $r^2\le2$（用 $h=\frac{s^2-2}{2s}$ 造更小上界 $s-h$）两半。读源文件 Theorem 27 时，把 [JL] Example 1.2.3 摊在旁边对照——两者只差”上界集合是 $\mathbb{Q}$ 还是 $\mathbb{R}$”以及”是否补一句 $\sqrt2\notin\mathbb{Q}$”。
  • §1.2.3 “Using supremum and infimum” 给出 $x+A$、$xA$ 的 $\sup/\inf$ 运算律，以及本讲 $\epsilon$-刻画的正式版本：”若 $S$ 非空有上界，则 $\forall\epsilon>0\ \exists x\in S$，$\sup S-\epsilon<x\le\sup S$”（[JL] 列为命题，证明留给读者）。这就是 OCW Assignment 3 第 4 题的来源。
  • §1.2.4 “Maxima and minima” 讨论 $\max/\min$ 与 $\sup/\inf$ 的关系，对应本文”$\sup$ 可以不属于 $E$”的辨析。
• 对应 OCW Assignment 2（发布讲次为 Lecture 4，但内容直接建立在 Lecture 3 上；原题见 hw_all.txt）：
  • 第 7 题：”Let $E=\{x\in\mathbb{R}:x>0\text{ and }x^3<2\}$. (a) Prove that $E$ is bounded above. (b) Let $r=\sup E$ (which exists by part (a)). Prove that $r>0$ and $r^3=2$. Hint: Adapt the proof used in Example 1.2.3.” —— 练的是把源文件 Theorem 27 的 $\epsilon/h$ 技巧从平方迁移到立方（本文已把完整证明写在”【补充】同一技巧的另一副面孔”中，含 $r=\frac54$、$r=\frac{13}{10}$ 两组数值）。
  • 第 1、2、3、4 题（Exercise 1.1.1, 1.1.2, 1.1.5, 1.1.6）练 [JL] §1.1 的有序域基本性质（如 $x<0,y<z\Rightarrow xy>xz$；非空有限集必有 $\max/\min$；$0<x<y\Rightarrow x^2<y^2$；有界集的子集也有界且 $\inf B\le\inf A\le\sup A\le\sup B$）——这些正是本讲”有序集 + sup/inf”定义的直接操练。
  • 第 5、6 题（Exercise 1.2.7, 1.2.9）是 §1.2 的 $\sup/\inf$ 习题（含 $A+B$、$AB$ 的 $\sup$ 运算律）。
• 对应 OCW Assignment 3（发布讲次为 Lecture 6，原题见 hw_all.txt）：
  • 第 4 题：”Let $A$ be a subset of $\mathbb{R}$ which is bounded above, and let $a_0$ be an upper bound for $A$. Prove that $a_0=\sup A$ if and only if for every $\epsilon>0$, there exists $a\in A$ such that $a_0-\epsilon<a$.” —— 本讲 $\epsilon$-刻画的完整题面，本文已给出完整两方向证明与 $\epsilon=0.001$、$\epsilon=0.01$、$\epsilon=10^{-6}$ 三组数值验证。这是 Lecture 3 最该动手做的题。
  • 第 2 题：”Let $E\subset(0,1)$ be the set of all real numbers with decimal representation using only the digits 1 and 2 … Prove that $\vert E\vert =\vert \wp(\mathbb{N})\vert $.”（Hint：考虑 $f:E\to\wp(\mathbb{N})$，$f(x)=\{j\in\mathbb{N}:d_{-j}=2\}$。）—— 练的是用 Cantor 定理 + CSB 判定一个集合的大小恰为 $\vert \wp(\mathbb{N})\vert $。本文思考题 Q1 给出完整解答。
  • 第 3(a)(b) 题：(a) 两个互不相交的可数无限集的并仍可数无限；(b) 证明 $\mathbb{R}\setminus\mathbb{Q}$ 不可数（允许引用”$\mathbb{R}$ 不可数、$\mathbb{R}\setminus\mathbb{Q}$ 无限”）——第 (b) 问正是本讲 Cantor 定理的直接后代：$\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$，可数 + 可数只能是可数，而 $\mathbb{R}$ 不可数，故 $\mathbb{R}\setminus\mathbb{Q}$ 必须不可数。
  • 第 1 题：证明任意两实数之间存在无理数（用 $\sqrt2$ 缩放 + 有理数稠密性）——用到 $\sqrt2$ 的存在，其存在性正是本讲 Theorem 27 与 LUB 性质的产物。
  • 第 5 题：开集的定义与运算（$(-\infty,a)$、$(a,b)$、任意并、有限交开；$\mathbb{Q}$ 不是开集）——本讲定义的 $\sup/\inf$ 为描述这些集合提供了语言。
• 对应 OCW Midterm（2020-10-16，原题见 hw_all.txt）：
  • 第 1(b) 题：”When $E$ is a countable subset of $\mathbb{R}$, is the complement $\mathbb{R}\setminus E$ always uncountable? Explain why or why not.” —— 答：是，永远不可数。 若 $\mathbb{R}\setminus E$ 可数，则 $\mathbb{R}=E\cup(\mathbb{R}\setminus E)$ 是可数集的可数并，从而可数，与 Cantor 定理（$\mathbb{R}$ 不可数，源文件 Corollary 18 的同胞结论 / [JL] §1.4 Theorem）矛盾。这题的整个论证只用了本讲的基数技术。
  • 第 1(c) 题：”When $E$ is an uncountable subset of $\mathbb{R}$, is the complement $\mathbb{R}\setminus E$ always countable? Explain why or why not.” —— 答：不是。 反例：$E=(0,1)\cup(3,4)$ 不可数，其余集 $(-\infty,0]\cup[1,3]\cup[4,\infty)$ 也包含区间 $(1,3)$，同样不可数；更极端的反例（用 Assignment 3 第 3(b) 题）：$E=\mathbb{R}\setminus\mathbb{Q}$ 不可数，其余集 $\mathbb{Q}$ 可数——同一个”不可数”的帽子下，补集可以不可数、也可以可数，所以不能一概而论。
  • 第 1(a) 题（原像与交）与本讲无直接关系，属 Lecture 2 的函数/像原像内容，此处列出以说明本讲的命题在期中卷中的位置。

与其他讲次的关联

• 向后依赖 Lecture 1–2（本讲的技术来源）：
  • Lecture 1 的良序原理（$\mathbb{N}$ 的每个非空子集有最小元）是 Theorem 28 第 6 步的唯一数论工具。没有它，我们就无法从 $x^2=2$ 推出矛盾。
  • Lecture 2 的定义 11（基数比较） 与本讲的 $\vert A\vert <\vert \wp(A)\vert $ 记号直接衔接；Lecture 2 的 Cantor–Schröder–Bernstein 定理在本讲被用于 Assignment 3 第 2 题那类”精确算出一个集合的基数”的问题（本文思考题 Q1）。
  • Lecture 2 已证的可数集事实（$\vert \mathbb{Z}\vert =\vert \mathbb{N}\vert $、$\vert \{q\in\mathbb{Q}:q>0\}\vert =\vert \mathbb{N}\vert $，后者的证明在 Assignment 1 第 6 题）是”$\mathbb{R}\setminus\mathbb{Q}$ 不可数”这类推论的前提。
• 向前指向 Lecture 4（直接续集）：源文件在本讲末尾留下钩子——”$\mathbb{Q}$ is an example of a field, which we will start to discuss in the next lecture”，而源文件 Theorem 22 宣告的”存在唯一的、包含 $\mathbb{Q}$ 且具有 LUB 性质的有序域 $\mathbb{R}$“要到 Lecture 4 才被赋予精确定义（Definition 30 域、Definition 33 有序域）并完成刻画。本讲只证明”$\mathbb{Q}$ 不够用”，下一讲才把 $\mathbb{R}$ 立起来。 本讲 Theorem 28 是 Lecture 4 全部动机的来源。
• 向前指向 Lecture 5（立刻被使用）：Lecture 5 的 Archimedes 性质（$\forall x\in\mathbb{R}\ \exists n\in\mathbb{N},n>x$）、有理数稠密性、绝对值的性质，全部建立在 LUB 性质之上；而 $\sup A$ 的 $\epsilon$-刻画（本讲）在 Lecture 5 会被反复使用，例如证明”$\sup$ 的运算律”。本讲 Theorem 27 中”取 $q<x-h$”的因子符号推理也会在 Lecture 5 的绝对值不等式里复现。
• 向前指向 Lecture 6 与 Lecture 9–10（地基作用）：
  • Lecture 6 用十进制展开 + 对角化证明 $\mathbb{R}$ 不可数——这就是本讲对角化论证的第二次出场，只是”清单”从”$A\to\wp(A)$ 的映射”换成了”实数序列”，”反例对象”从 $B$ 换成了改掉对角位的新实数 $y$（[JL] §1.5 的 Cantor diagonalization）。本讲的 Cantor 定理一旦掌握，Lecture 6 的证明几乎是免费的。
  • Lecture 9 的 Bolzano–Weierstrass 定理（有界序列必有收敛子列）与 Lecture 10 的 Cauchy 完备性（$\mathbb{R}$ 中 Cauchy 序列必收敛）都靠 LUB 性质；而 $\mathbb{Q}$ 中 Cauchy 序列可以不收敛（例如 $\mathbb{Q}$ 中逼近 $\sqrt2$ 的序列），正与本讲 Theorem 28 “$\mathbb{Q}$ 缺一个点”是同一件事。
• 向前指向 Lecture 16 与 Lecture 21（最终收获）：Lecture 16 的极值定理（闭区间上连续函数取到最大最小值）与 Bolzano 介值定理（用二分法 + LUB）是 LUB 性质的直接果实——$f$ 在 $[a,b]$ 上的最大值是 $\sup f([a,b])$，必须靠 LUB 才能断言它取得到；Lecture 21 的连续函数可积性同样以”$\sup$ 分析”（上下积分之差）为工具。所以本讲定义 $\sup$ 的那两行，是后半门课的种子。

关键要点

1. Cantor 定理（源文件 Theorem 15）：对任意集合 $A$，$\vert A\vert <\vert \wp(A)\vert $。证明分两步：$f(x)=\{x\}$ 给出单射（故 $\vert A\vert \le\vert \wp(A)\vert $）；再反设存在满射 $g:A\to\wp(A)$，构造对角集 \(B=\{x\in A:x\notin g(x)\}\in\wp(A),\) 取 $b\in A$ 使 $g(b)=B$，则 “$b\in B\Rightarrow b\notin g(b)=B$” 与 “$b\notin B\Rightarrow b\in g(b)=B$” 两支都矛盾。推论：$\wp(\mathbb{N})$ 不可数，且 $\vert \mathbb{N}\vert <\vert \wp(\mathbb{N})\vert <\vert \wp(\wp(\mathbb{N}))\vert <\cdots$（源文件 Remark 16）。
2. 有序集（源文件 Definition 23）：$S$ 配合关系 $<$，满足 ① 三歧性（$\forall x,y$：$x<y$ 或 $y<x$ 或 $x=y$）；② 传递性（$x<y$ 且 $y<z\Rightarrow x<z$）。非例：$(\wp(\mathbb{N}),\subset)$ 不满足三歧性。
3. 上界与上确界（源文件 Definition 24）：$b$ 是 $E$ 的上界 $\iff\forall x\in E,x\le b$；$b_0=\sup E$ $\iff$ (A) $b_0$ 是上界，且 (B) 对一切上界 $b$ 有 $b_0\le b$。$\sup E$ 若存在则唯一；$\sup E$ 可以不属于 $E$（例如 $\sup(0,1)=1$），因此 $\sup\neq\max$。
4. $\sup$ 的两步法与 $\epsilon$-刻画（[JL] §1.2；OCW Assignment 3 第 4 题）：$a_0$ 是 $A$ 的上界时， \(a_0=\sup A\iff\forall\epsilon>0\ \exists a\in A,\ a_0-\epsilon<a.\) 由此得到”证 $\sup$ 的标准两步”：① 证 $a_0$ 是上界；② 对每个 $\epsilon>0$ 在 $A$ 中造出超过 $a_0-\epsilon$ 的元素。（例如 $A=\{1-\frac1n\}$，$\epsilon=0.001\Rightarrow n=1001$ 即可。）
5. 最小上界性质与 $\mathbb{Q}$ 的失败（源文件 Definition 26、Theorem 27、Theorem 28）：$S$ 具有 LUB 性质 $\iff$ 每个非空且有上界的 $E\subset S$ 都在 $S$ 中有 $\sup$。$\mathbb{R}$ 具备（源文件 Theorem 22），而 $\mathbb{Q}$ 不具备：$E=\{q\in\mathbb{Q}:q>0,q^2<2\}$ 非空、有上界 $2$，但若 $x=\sup E$ 则必有 $x^2=2$（Theorem 27），而 $\mathbb{Q}$ 中无平方为 $2$ 之数（Theorem 28）。 LUB 性质是 $\mathbb{R}$ 与 $\mathbb{Q}$ 的分界线，也是全课程后续一切定理的地基。

常见误区与注意事项

1. 误区：把 $\sup E$ 与 $\max E$ 混为一谈。
   • 错误做法：证明 $s=\sup E$ 后直接写”$s\in E$，故 $s=\max E$”，或者反过来认为”$\sup$ 一定取不到”。
   • 为什么错：$\sup$ 只在上界集合里取最小元，它不欠 $E$ 一个成员资格。源文件 Example 25 的第二个例子 $E=\{q\in\mathbb{Q}:0\le q<1\}$：$\inf E=0\in E$ 但 $\sup E=1\notin E$；本文补充的 $E=\{1/n\}$：$\sup E=1\in E$ 但 $\inf E=0\notin E$。同一个集合，$\sup$ 与 $\inf$ 的归属可以完全不同。
   • 正确做法：$\max E$ 存在 $\Longrightarrow\sup E=\max E$；反之必须单独检查 $s\in E$ 是否成立。要判断 $s\in E$，通常看 $E$ 的定义区间是闭还是开（或看 $E$ 中的元素能否任意逼近 $s$）。
2. 误区：把”有上界”与”有上确界”混为一谈。
   • 错误做法：看到 $E$ 有上界就断言”$\sup E$ 存在”。
   • 为什么错：这正是本讲要打的靶子。$E=\{q\in\mathbb{Q}:q>0,q^2<2\}$ 有上界 $2$，但在 $\mathbb{Q}$ 中没有上确界（Theorem 28）。”有上界”只说”天花板存在”，”有上确界”说”最低的那块天花板存在”——后者需要 LUB 性质来担保。
   • 正确做法：先分清你在哪个有序集里工作。在 $\mathbb{R}$ 里可以放心引用 LUB 性质断言 $\sup$ 存在；在 $\mathbb{Q}$、$\mathbb{Z}$、$-\mathbb{N}$ 或抽象有序集里，必须先逐个检查 LUB 性质是否成立（$\mathbb{Z}$ 与 $-\mathbb{N}$ 成立，$\mathbb{Q}$ 不成立）。
3. 误区：$\epsilon$-刻画里量词顺序写反。
   • 错误做法：把”$\forall\epsilon>0\ \exists a\in A,\ a_0-\epsilon<a$”写成”$\exists\epsilon>0\ \forall a\in A,\ a_0-\epsilon<a$”（即”存在一个固定的 $\epsilon$ 使一切 $a$ 都够大”），或写成”$\forall a\in A\ \exists\epsilon>0,\ a_0-\epsilon<a$”（后者对任何 $a$ 都成立，因为只需取 $\epsilon$ 很大，是废话）。
   • 为什么错：两种情况都远远弱于原条件，会得出错误结论。例如 $A=(0,1)$、$a_0=3$：取 $\epsilon=5$，则一切 $a\in A$ 都满足 $a>3-5=-2$，第二种错写法”成立”，但 $3\neq\sup A=1$。再看”$\forall a\ \exists\epsilon$”形式：取 $A=\{0\}$、$a_0=10$，对 $a=0$ 取 $\epsilon=11$ 得 $0>10-11=-1$ ✓，条件”成立”，但 $10\neq\sup A=0$。
   • 正确做法：记住角色分工——$\epsilon$ 是对手给你的（任意小！），$a$ 是你造的（可以依赖 $\epsilon$）。原条件说的是”无论对手把窗口 $(a_0-\epsilon,a_0]$ 收得多窄，你都能在 $A$ 里找到一个元素伸进窗口”。写证明时先写”任取 $\epsilon>0$”，最后再构造 $a$。
4. 误区：反证时只检查一种情形就宣布矛盾（Cantor 定理的两支论证）。
   • 错误做法：在第 8 步只写”设 $b\in B$，则 $b\notin B$，矛盾，证毕”。
   • 为什么错：$b\in B$ 与 $b\notin B$ 并不互相排斥到只需检查一支——恰恰相反，它们是排中律下仅有的两种可能，必须两支都排除才算穷尽。只写一支，等于默认了 $b\in B$（即暗中把要证的结论当假设用），逻辑上有洞。
   • 正确做法：按源文件 Remark 17 的方法论，明确写出”有两种（且仅有两种）情形”，逐支推出矛盾，最后声明”两种情形都矛盾，故假设不成立”。凡是形如”$P$ 或 $\neg P$”的分类，两支都要落地。
5. 误区：在 $\mathbb{Q}$ 中做 $\sup$ 的论证时，偷用 $\mathbb{R}$ 的性质（或反之，把定理 27 与 28 的分工弄混）。
   • 错误做法一：证明 Theorem 27 时写”$x^2<2$ 时取 $h=\sqrt2-x>0$”——$\sqrt2$ 正是我们还不存在的东西（在 $\mathbb{Q}$ 的语境里它的存在性就是待证的），这是循环论证。正确做法是用纯代数的、只含 $h$ 与 $x$ 的量：$h=\min\{\frac12,\frac{2-x^2}{2(2x+1)}\}$。
   • 错误做法二：认为”Theorem 27 证明了 $\sup E$ 不存在”。Theorem 27 只说”若 $x=\sup E$ 则 $x^2=2$”（条件陈述）；不存在性是 Theorem 28 用数论（良序原理）补上的。两条定理各管一半，缺一不可。
   • 正确做法：书写时把”域的代数运算 + 序”与”$\mathbb{Q}$ 的数论结构”分开；凡是需要”$\mathbb{R}$ 中的数”的地方（$\sqrt2$、$\sqrt[3]2$）都要标注为”由 LUB 性质保证存在”，不得在 $\mathbb{Q}$ 的句子里直接使用。

思考题（带答案）

Q1.（用 Cantor 定理/CSB 精确算基数；对应 OCW Assignment 3 第 2 题）设

即 $(0,1)$ 中所有只由数字 $1$ 和 $2$ 组成的十进制小数。证明

Q2.（完整做一次”证 $\sup$”的两步法）设

证明 $\sup A=2$，并判断 $\max A$ 是否存在、$\inf A$ 等于多少、$\inf A\in A$ 吗？

Q3.（概念理解；【补充】题，取自 [JL] §1.4 之后的思路，源文件未列）记 $\mathbb{R}^{\mathbb{R}}$ 为一切函数 $f:\mathbb{R}\to\mathbb{R}$ 组成的集合。证明

并说明这个证明与 Lecture 3 的对角化论证是同一个证明。