Lecture 1: Sets, Set Operations, and Mathematical Induction（集合、集合运算与数学归纳法）
Lecture 1: Sets, Set Operations, and Mathematical Induction（集合、集合运算与数学归纳法）
概述
本讲是 MIT 18.100A（实分析）的第一讲，教材是 Jiří Lebl 的 Basic Analysis: Introduction to Real Analysis, Volume I（下文简称 Lebl，笔记中以 [L] 指代）。本讲表面上讲的是”集合”与”数学归纳法”这两件看似初等的事情，但它们的真正地位是：为整门课程提供语言（notation/language）与最基本的证明工具（proof method）。后面 Lecture 3 的 Cantor 定理、Lecture 8 的极限定理、Lecture 9 的子序列定理，全都要靠本讲建立的东西来书写与证明。
按源文件的结构，本讲包含以下编号内容，笔记将逐条覆盖：
| 编号 | 内容 | 类型 |
|---|---|---|
| Remark 1 | 课程两大目标 | 课程说明 |
| — | 集合、空集 $\emptyset$、八个逻辑/集合记号 | 定义（非编号） |
| Definition 2 | 集合关系：子集、相等、真子集；集合构造记号；四个数集 | 定义 |
| Problem 3 | 如何描述 $\mathbb{R}$？ | 问题（悬念） |
| — | 五种集合运算：并、交、差、补、不相交 | 定义（非编号） |
| Theorem 4 | De Morgan 定律（四条） | 定理 |
| Axiom 5 | 良序原理（Well-ordering property） | 公理 |
| Theorem 6 | 数学归纳法（Induction），由良序原理证明 | 定理 |
| Remark 7 | 反证法的逻辑说明 | 说明 |
| Theorem 8 | 等比级数求和公式 | 定理 |
| Theorem 9 | Bernoulli 不等式 | 定理 |
为什么要先讲这些？ 因为 Remark 1 中列出的课程目标，决定了我们必须先有共同的语言与共同的推理规则：
Remark 1（课程两大目标）。 本课程有两个主要目标：
- 获得证明的经验（gain experience with proofs）：既包括读懂别人写的证明，也包括自己写出严格的证明。
- 证明关于实数、函数与极限的命题（prove statements about real numbers, functions, and limits）：即把目标 1 中获得的技艺，用在真正的分析对象上。
对这两条目标的展开说明：
目标 1 的两半。 “读证明”意味着你看到一个证明时，能准确说出：(i) 它在证什么（结论的精确陈述）；(ii) 它用了什么假设、什么公理、什么已证定理；(iii) 每一步的依据是什么。这三件事在本讲中会被反复示范——例如 Theorem 6 的证明里，每一步都会注明”由良序原理”或”由归纳假设”。”写证明”则意味着你能从结论出发设计策略（直接证明？反证？双向包含？归纳？），再把策略落成一句一句可检验的推论。本讲的核心训练点正是策略与落地。
目标 2 的含义。 “实数、函数与极限”是这门课的全部研究对象。注意源文件把三者并列：实数是舞台（Problem 3 问的就是”$\mathbb{R}$ 到底是什么”），函数是舞台上的演员，极限是这部戏的情节。本课程后续的一切——序列极限（Lectures 5–10）、连续性（Lectures 14+）、导数、积分——都是在这三者上展开的。
本课程与微积分课的关键区别：从”计算”到”证明”。 这是初学者最容易低估的一点。微积分课（Calculus）通常关心算出答案；实分析课关心证明答案。举一个源文件式的例子：
\[\lim_{n\to\infty}\frac{n^{2}}{n^{2}+n+1}=1 .\]在微积分课里，这是一道”计算题”：分子分母同除 $n^{2}$，得 $\dfrac{1}{1+1/n+1/n^{2}}\to\dfrac{1}{1+0+0}=1$，写完收工。在 18.100A 里，这句话不是一个可以使用的推论，而是一个待证明的命题。要证明它，你不能说”当 $n$ 很大时 $1/n\to0$”，因为 $1/n\to0$ 本身就是要证明的命题。你必须回到极限的定义：
\[\forall\epsilon>0,\ \exists N\in\mathbb{N},\ \forall n\ge N:\ \left\vert \frac{n^{2}}{n^{2}+n+1}-1\right\vert <\epsilon .\]然后对给定的 $\epsilon$ 构造出具体的 $N$。这类”$\epsilon$-$N$ 论证”将在 Lecture 8 中系统展开，而这个例子正是那里的标准练习。请记住这个对照：微积分的答案是结论，实分析的答案是证明。
因此本讲的定位是”工具箱”:先给语言（集合记号），再给两把最常用的工具（双向包含法 与 数学归纳法），工具一旦到手，后续课程就能稳步推进。
核心定义与直观解释
本节把源文件中所有”定义类”内容逐条展开：严格定义 → 直观解释 → 为什么需要这个条件 → 具体示例 → 反例（如适用）。
1. 集合与空集（Sets, Empty Set）
严格定义。 一个集合（set）是一批对象的汇集，这些对象称为该集合的元素（elements）或成员（members）。空集（empty set）记作 $\emptyset$，是不含任何元素的集合。
直观解释。 集合是”把一些东西装进一个袋子”。袋子本身不关心东西的排列顺序，也不关心同一个东西被”提到”几次。因此
\[\{1,2,3\}=\{3,1,2\}=\{1,1,2,2,3\}.\]为什么需要空集？ 因为很多命题的自然表述会”自然地”落到空集上。例如”$A$ 与 $B$ 不相交”的定义就是 $A\cap B=\emptyset$；良序原理的结论”$S$ 有最小元”只对 $S\neq\emptyset$ 成立——空集没有最小元，这正是为什么 Theorem 6 的证明最后要推出 $S=\emptyset$。若不允许空集存在，”没有元素”这一情形就无法被陈述。
示例。 $\{x\in\mathbb{R}\mid x^{2}+1=0\}=\emptyset$（在实数范围内无解）。 反例（需要警惕的写法）。 $\{\emptyset\}$ 不是空集：它有一个元素，那个元素是空集。所以 $\emptyset\neq\{\emptyset\}$，且 $\vert \emptyset\vert =0$、$\vert \{\emptyset\}\vert =1$。这是初学者最常犯的记号错误之一。
2. 记号表（Notation Table）
设 $S$ 是一个集合。源文件给出的八个记号及其含义：
| 记号 | 读法 | 含义 |
|---|---|---|
| $a\in S$ | “$a$ 属于 $S$” | $a$ 是 $S$ 中的元素 |
| $a\notin S$ | “$a$ 不属于 $S$” | $a$ 不是 $S$ 中的元素 |
| $\forall$ | “对一切”（for all） | 全称量词 |
| $:=$ | “定义为”（define） | 左侧被右侧定义 |
| $\exists$ | “存在”（there exists） | 存在量词 |
| $\exists!$ | “存在唯一”（there exists a unique） | 存在且至多一个 |
| $\Rightarrow$ | “蕴含”（implies） | 若左真则右真 |
| $\iff$ | “当且仅当”（if and only if） | 左右同真同假 |
直观解释与易错点。
- $\forall$ 与 $\exists$ 是”量词”，它们的顺序决定了命题的含义。$\forall\epsilon>0\,\exists N$ 与 $\exists N\,\forall\epsilon>0$ 是完全不同的命题（前者是本课程”收敛”的正确形式；后者意味着存在一个 $N$ 对一切 $\epsilon$ 都好，即”最终恒等”，过于强）。Lecture 5 起会反复利用这一区别。
- $:=$ 是”定义号”，表示我们在命名一个对象；它与 $\Rightarrow$、$=$ 都不是一回事。写 $A:=B$ 表示”把 $B$ 命名为 $A$”，而不是”$A$ 与 $B$ 相等”这一待证命题。
- $\exists!$ 必须拆成两半来用：存在性（$\exists$）与唯一性（若 $x,y$ 都满足则 $x=y$）。Assignment 1 第 6 题证明 $f$ 是双射时，”唯一素因子分解”提供的正是这种”存在且唯一”。
- $\iff$ 与 $\Rightarrow$ 的区别，正是本讲”双向包含法”的记号基础：$A=B$ 的证明就是 $A\subset B \iff$ 与 $B\subset A$ 两半合起来。
- $\Rightarrow$ 的用法中要小心”方向”：$P\Rightarrow Q$ 成立并不意味着 $Q\Rightarrow P$ 成立。De Morgan 定律的证明里，两个方向的推理链方向是相反的，必须分开写。
示例（正确使用 $\exists!$）。 $\forall a\in\mathbb{R},\ \exists!\,b\in\mathbb{R}: a+b=0$——存在（取 $b=-a$）且唯一（若 $a+b=a+b^{\prime}=0$ 则 $b=b^{\prime}$）。
3. Definition 2（Set Relations，集合关系）
Definition 2（Set Relations）。 我们希望刻画不同集合之间的关系，于是有以下记号/定义：
- 集合 $A$ 是 $B$ 的子集（subset），记作 $A\subset B$，如果 $A$ 的每个元素都在 $B$ 中。等价地，给定 $A\subset B$，则 $a\in A\Rightarrow a\in B$。
- 两个集合 $A$ 与 $B$ 相等（equal），记作 $A=B$，如果 $A\subset B$ 且 $B\subset A$。
- 集合 $A$ 是 $B$ 的真子集（proper subset），记作 $A\subsetneq B$，如果 $A\subset B$ 且 $A\neq B$。
严格定义的形式化写法。
\[A\subset B \ :\iff\ \forall x,\ (x\in A\Rightarrow x\in B).\] \[A=B \ :\iff\ (A\subset B)\wedge(B\subset A).\] \[A\subsetneq B \ :\iff\ (A\subset B)\wedge(A\neq B).\]直观解释。 “$A\subset B$”意味着 $A$ 被”装进”了 $B$：不要求 $A$ 用满 $B$，也不要求 $A\neq B$。等号也一样被允许——这是初学者第一个心理障碍：子集不必是真子集。$\mathbb{N}\subset\mathbb{N}$ 是对的（每个自然数都是自然数）。
为什么 $A=B$ 要用双向包含来定义？ 因为集合的”相等”不是符号层面的相等（我们不比较两个袋子的外观），而是外延（extensionality）层面的相等：两个集合相等当且仅当它们有完全相同的元素。没有哪个方向是多余的预算：只证 $A\subset B$ 只说明”$A$ 不比 $B$ 大”，还可能是严格更小。所以证明两个集合相等，唯一的标准动作就是证明两个包含方向。本讲的 Theorem 4 就是这一方法的示范。
具体示例（三种关系都出现）。 取 $A=\{1,2\}$，$B=\{1,2,3\}$，$C=\{1,2\}$。则：$A\subset B$；$A\subsetneq B$（因为 $3\in B$ 但 $3\notin A$，故 $A\neq B$）；$A=C$ 而不是 $A\subsetneq C$；$\emptyset\subset A$ 且 $\emptyset\subsetneq A$。
反例（两个方向不能互相替代）。 设 $A=\mathbb{N}$，$B=\mathbb{Z}$。有 $A\subset B$，但 $B\not\subset A$（$-1\in B$ 而 $-1\notin A$）。所以”看起来像包含”不等于相等。又设 $A=\{1,2,3\}$，$B=\{x\in\mathbb{N}\mid x\le3\}$：此时 $A\subset B$ 且 $B\subset A$，故 $A=B$——这正是我们必须把两个方向都写清楚的原因：两个不同写法定义的集合，可能相等。
4. 集合构造记号（Set Building Notation）
源文件给出的写法：
\[\{x\in A\mid P(x)\}\quad\text{或}\quad\{x\mid P(x)\},\]读作”所有满足性质 $P(x)$ 的 $x\in A$”。
直观解释。 这是”筛选器”：从 $A$ 里挑出满足 $P$ 的那些元素，构成新集合。源文件给的例子是 $\{x\mid x\text{ 是偶数}\}$。
为什么要求写 $x\in A$？ 第一种写法（$\{x\in A\mid P(x)\}$）是安全的：它明确说明了筛选范围来自已知的集合 $A$，因此不会产生”集合论悖论”（如 $\{x\mid x\notin x\}$ 这类无限制概括导致的 Russell 悖论）。第二种写法 $\{x\mid P(x)\}$ 在课程中被宽松地使用（如”所有偶数”），但严格来说它隐含了一个论域。建议：自己写证明时优先用 $\{x\in A\mid P(x)\}$。
示例。 $\{x\in\mathbb{R}\mid x^{2}<2\}$ 是开区间 $(-\sqrt2,\sqrt2)$；$\{x\in\mathbb{N}\mid x\text{ 是素数}\}=\{2,3,5,7,11,\dots\}$。 反例（循环定义）。 $\{x\mid x\text{ 是一个很小的数}\}$ 不是集合构造：性质 $P$ 必须是一个有明确真假的命题，”很小”不是。好的 $P$ 如 $x^{2}<2$、$x$ 是偶数、$x\in g(x)$。
5. 四个数集（The Number Sets）
源文件列出并断言
\[\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}.\]- 自然数（natural numbers）：$\mathbb{N}=\{1,2,3,4,\dots\}$。
- 整数（integers）：$\mathbb{Z}=\{0,1,-1,2,-2,3,-3,\dots\}$。
- 有理数（rational numbers）：$\mathbb{Q}=\left\{\frac mn\ \middle\vert \ m,n\in\mathbb{Z}\ \text{且}\ n\neq0\right\}$。
- 实数（real numbers）：$\mathbb{R}$。
注意一处重要的约定。 本课程（以及 Lebl 教材）采取 $\mathbb{N}=\{1,2,3,\dots\}$，即自然数从 1 开始，不含 0。这一点会直接影响归纳法的写法：Theorem 8 与 Theorem 9 的归纳都从 $n=1$ 起证；良序原理中的最小元 $\ge1$；而 Lecture 3 的 Corollary 18 则要用到 $\mathbb{N}\cup\{0\}$ 才能从 $n=0$ 起表述。若你习惯 $\mathbb{N}=\{0,1,2,\dots\}$，务必在阅读时换算。
直观解释（嵌套图）。
实数 R
┌──────────────────────────────────────┐
│ 有理数 Q │
│ ┌─────────────────────────┐ │
│ │ 整数 Z │ │
│ │ ┌──────────┐ │ │
│ │ │ 自然数 N │ │ │
│ │ │ 1,2,3,.. │ │ │
│ │ │ (0 不在内)│ │ │
│ │ └──────────┘ │ │
│ │ ..., -2, -1, 0 │ │
│ └─────────────────────────┘ │
│ m/n (m,n ∈ Z, n ≠ 0) │
│ 还有"洞"：√2, π, e 等无理数在此层 │
└──────────────────────────────────────┘
每一步包含都是"真子集"：N ⊊ Z ⊊ Q ⊊ R
为什么每个包含都是真包含（$\subsetneq$）？ 要证 $\mathbb{N}\subsetneq\mathbb{Z}$，需要一个元素在 $\mathbb{Z}$ 中而不在 $\mathbb{N}$ 中：取 $0$（或 $-1$）。要证 $\mathbb{Z}\subsetneq\mathbb{Q}$，取 $1/2$。要证 $\mathbb{Q}\subsetneq\mathbb{R}$，需要证明存在非有理实数——这不是一眼可见的，$\sqrt2\notin\mathbb{Q}$ 的经典奇偶性证明会在 Lecture 3 附近出现（Lebl §1.1 的练习亦涉及）。
反例（包含链条中”不显然”的一环）。 $\mathbb{Q}\subset\mathbb{R}$ 看起来当然，但它的严格证明依赖于 $\mathbb{R}$ 的构造——而”$\mathbb{R}$ 是什么”正是 Problem 3 要问的、Lectures 3–4 才会回答的问题。这说明本讲的”$\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}$”在 Lecture 1 阶段是断言/待精化的事实，不是已完成证明的定理。
6. Problem 3（如何描述 $\mathbb{R}$？）
Problem 3. 我们如何描述 $\mathbb{R}$？
源文件的处理方式非常有教学意味：它不回答，而是明确地把答案推迟到 Lectures 3 和 4，然后说”In the meantime, let’s continue our study of sets and proof methods”（在此期间，我们继续研究集合与证明方法）。
为什么这是一个真问题？ 因为 $\mathbb{N},\mathbb{Z},\mathbb{Q}$ 都能用简短的显式描述（后继、正负整数、分子分母之比）来给出，而 $\mathbb{R}$ 不能：$\mathbb{R}$ 中的绝大多数元素无法被任何有限公式写出来。你当然可以说”$\mathbb{R}$ 是所有小数展开的集合”，但这立刻引出一串问题：$0.999\dots=1$ 吗？不同的展开会不会表示同一个数？小数展开的运算如何定义？更根本地：$\mathbb{Q}$ 已经”很稠密”（任意两个有理数之间还有有理数），为什么还需要 $\mathbb{R}$？
答案的形状（悬念）。 Lecture 3 会揭示 $\mathbb{Q}$ 的致命缺陷：$\mathbb{Q}$ 缺少最小上界性质（least upper bound property）——例如 $\{q\in\mathbb{Q}\mid q>0,\ q^{2}<2\}$ 在 $\mathbb{Q}$ 中有上界却无最小上界。$\mathbb{R}$ 就是把这些”洞”补上之后的集合。Lecture 3 的 Theorem 22 会给出精确刻画：存在唯一的、包含 $\mathbb{Q}$ 的、具有最小上界性质的有序域（ordered field），我们记之为 $\mathbb{R}$。 所以 Problem 3 的答案不是”$\mathbb{R}=\mathbb{Q}$ 加无理数”这种粗糙说法，而是一组公理式的性质刻画。
自学建议。 现在就把 Problem 3 记成”全课程的第一个悬念”。Lecture 1 之后每一讲你都可以回问一句：”这一讲用到了 $\mathbb{R}$ 的哪条性质？”——Lecture 8 的单调有界定理用的是最小上界性质；Lecture 5 的三角不等式用的是有序域性质。这样 $\mathbb{R}$ 的概念会在使用中被逐步”填实”。
7. 五种集合运算（Set Operations）
源文件给出五个定义（不编号）：
（1）并（union）：$A\cup B=\{x\mid x\in A\ \text{或}\ x\in B\}$。 （2）交（intersection）：$A\cap B=\{x\mid x\in A\ \text{且}\ x\in B\}$。 （3）差（set difference）：$A\setminus B=\{x\in A\mid x\notin B\}$。 （4）补（complement）：$A^{c}=\{x\mid x\notin A\}$。 （5）不相交（disjoint）：$A$ 与 $B$ 不相交当且仅当 $A\cap B=\emptyset$。
直观解释。 并是”合并”，交是”公共部分”，差是”减掉”，补是”外面的一切”。源文件用的”或”（or）在数学中一律是包含或（inclusive or）：$x$ 可以同时在 $A$ 和 $B$ 中。这一点必须强调，因为日常语言的”或”有时是排他的。
为什么补 $A^{c}$ 需要额外小心？ 因为 $A^{c}=\{x\mid x\notin A\}$ 依赖于”$x$ 从哪个论域（universe）中取”。同一个 $A=\{1\}$，在论域 $\{1,2\}$ 中 $A^{c}=\{2\}$；在论域 $\mathbb{N}$ 中 $A^{c}=\{2,3,4,\dots\}$。在本课程的语境中，论域默认是 $\mathbb{R}$（当 $A\subset\mathbb{R}$ 时，$A^{c}=\mathbb{R}\setminus A$）。Failure to fix the universe 是集合等式出错的头号原因——Theorem 4 第 3、4 条用”差”而不是”补”来表述，正是为了规避论域问题：$A\setminus(B\cup C)$ 只涉及 $A$ 内部，无需外部论域。
示例。 设 $A=\{1,2,3\}$，$B=\{3,4\}$。则 $A\cup B=\{1,2,3,4\}$；$A\cap B=\{3\}$；$A\setminus B=\{1,2\}$；$B\setminus A=\{4\}$；$A\setminus B$ 与 $B\setminus A$ 不相交（因为 $(A\setminus B)\cap(B\setminus A)=\emptyset$）。
反例（并交差的非对称性）。
- $A\cup B=B\cup A$ 且 $A\cap B=B\cap A$（交换律成立），但 $A\setminus B\neq B\setminus A$（见上例：$\{1,2\}\neq\{4\}$）。
- $A\setminus(A\setminus B)=A\cap B$，不是 $B$。
- “不相交”是对称的：$A\cap B=\emptyset\iff B\cap A=\emptyset$。
集合关系示意图（De Morgan 的直观）。
全集(论域) U: 在 B、C 之外的部分就是 (B ∪ C)^c
┌─────────────────────────────────────────┐
│ U │
│ ┌───────────┐ │
│ │ B │ │
│ │ ┌───────┼──────┐ │
│ │ │ B ∩ C │ │ │
│ └───┼───────┘ C │ │
│ └──────────────┘ │
│ 阴影(B、C 之外)=(B∪C)^c = B^c ∩ C^c │
│ 在 B、C 之外 ⟺ 既不在 B 且 不在 C │
└─────────────────────────────────────────┘
对偶：(B ∩ C)^c = B^c ∪ C^c
"不在交集中" ⟺ "至少一个集合没进去"
定理与完整证明（核心）
本节逐一给出 Axiom 5、Theorem 4、Theorem 6、Theorem 8、Theorem 9 的陈述、证明策略、逐步推导（每步注明依据）、【证明机制解说】、【证明技巧总结】。
Theorem 4（De Morgan’s Laws，德摩根定律）
Theorem 4（De Morgan’s Laws）。 若 $A,B,C$ 是集合，则
- $(B\cup C)^{c}=B^{c}\cap C^{c}$，
- $(B\cap C)^{c}=B^{c}\cup C^{c}$，
- $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$，
- $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$。
源文件的说明是：我们只证第一条，作为”这样的证明该长什么样”的示范，其余留给你。本笔记按任务要求证第一、二条；第 3、4 条在”思考与练习”意义上留给读者（它们与第 1、2 条同构，只是把 $^{c}$ 换成了 $A\setminus(\cdot)$）。
第 1 条：$(B\cup C)^{c}=B^{c}\cap C^{c}$。
证明策略。 目标是一个集合等式。根据 Definition 2 第 2 款，集合相等必须双向包含来证，因此策略固定为两步：(I) 证 $(B\cup C)^{c}\subset B^{c}\cap C^{c}$；(II) 证 $B^{c}\cap C^{c}\subset(B\cup C)^{c}$。每一步都使用 Definition 2 第 1 款的判据：任取 $x$ 属于左边，推出 $x$ 属于右边。
完整证明（源文件证明的逐步展开）。
设 $B,C$ 是集合。我们需要证明
\[(B\cup C)^{c}\subset B^{c}\cap C^{c}\qquad\text{以及}\qquad B^{c}\cap C^{c}\subset(B\cup C)^{c}.\]（I）先证 $(B\cup C)^{c}\subset B^{c}\cap C^{c}$。 任取 $x\in(B\cup C)^{c}$。
- 由补集定义（$A^{c}=\{x\mid x\notin A\}$，取 $A=B\cup C$），$x\in(B\cup C)^{c}\Rightarrow x\notin B\cup C$。依据： 补集的定义。
- 由并集定义（$B\cup C=\{x\mid x\in B\ \text{或}\ x\in C\}$），$x\notin B\cup C\Rightarrow$ “（$x\in B$ 或 $x\in C$）”为假。依据： 并集的定义。
- 由命题逻辑中”$\neg(P\vee Q)\iff(\neg P)\wedge(\neg Q)$”，”（$x\in B$ 或 $x\in C$）”为假 $\Rightarrow$ $x\notin B$ 且 $x\notin C$。依据： 德摩根律的逻辑版本（本题真正的逻辑内核；第 2 条的证明也用它）。
- 由补集定义，$x\notin B\Rightarrow x\in B^{c}$；$x\notin C\Rightarrow x\in C^{c}$。依据： 补集的定义。
- 由交集定义，$x\in B^{c}$ 且 $x\in C^{c}\Rightarrow x\in B^{c}\cap C^{c}$。依据： 交集的定义。
- 综合 1–5：对任意 $x\in(B\cup C)^{c}$ 都有 $x\in B^{c}\cap C^{c}$，故 $(B\cup C)^{c}\subset B^{c}\cap C^{c}$。依据： 子集的定义。
（II）再证 $B^{c}\cap C^{c}\subset(B\cup C)^{c}$。 任取 $x\in B^{c}\cap C^{c}$。
- 由交集定义，$x\in B^{c}$ 且 $x\in C^{c}$。依据： 交集的定义。
- 由补集定义，$x\notin B$ 且 $x\notin C$。依据： 补集的定义。
- 由”$x\notin B$ 且 $x\notin C$” $\Rightarrow$ “（$x\in B$ 或 $x\in C$）”为假。依据： $(\neg P)\wedge(\neg Q)\Rightarrow\neg(P\vee Q)$（第 (I) 部分第 3 步所用等价式的反方向）。
- 由并集定义，”（$x\in B$ 或 $x\in C$）”为假 $\iff x\notin B\cup C$。依据： 并集的定义。
- 由补集定义，$x\notin B\cup C\Rightarrow x\in(B\cup C)^{c}$。依据： 补集的定义。
- 综合 1–5：任取 $x\in B^{c}\cap C^{c}$ 都有 $x\in(B\cup C)^{c}$，故 $B^{c}\cap C^{c}\subset(B\cup C)^{c}$。依据： 子集的定义。
（III）合并。 由 (I) 与 (II)，两个包含方向都成立；由 Definition 2 第 2 款（集合相等 $\iff$ 双向包含），$(B\cup C)^{c}=B^{c}\cap C^{c}$。$\blacksquare$
【证明机制解说】 这条定理的全部内容其实只有一句话：“不在并集里”等价于”既不在 $B$ 里也不在 $C$ 里”。数学上的所有动作只是把这句话用 Written in set-theoretic language：$\notin$ 翻译成 $^{c}$，$\text{或}\to\text{且}$，$\text{且}\to\text{或}$。注意”或”与”且”的互换是 De Morgan 定律的特征：取补会把并变成交、交变成并。这一现象在逻辑中（$\neg(P\vee Q)\equiv(\neg P)\wedge(\neg Q)$）、在不等式区间中（$x\notin(a,b]\iff x\le a$ 或 $x>b$）、在极限的否定中（$\neg(\forall\epsilon\exists N\cdots)\iff\exists\epsilon\forall N\cdots$）反复出现，是整个分析课程中”否定一个命题”技术的基础。因此 Theorem 4 不是一道集合论练习题，而是后续所有反证法与否定式论证的语法基础。
【证明技巧总结】
- 集合等式 = 双向包含，这是不可绕过的模板。看到 $X=Y$，第一件事就是写下两行 $X\subset Y$ 与 $Y\subset X$。
- 双向包含各自独立证明，互不干扰。先用 (I) 的假设 $x\in X$ 推到 $Y$，再用 (II) 的假设 $x\in Y$ 推到 $X$；不要试图用一条链”来回”推。
- 每一步都回到定义。本题中出现的每一个 $\subset,\cup,\cap,{}^{c}$ 都被换成了它的定义中最原始的 $\in$ 或 $\notin$ 表述。这是集合论证明的唯一可靠方法：“元素追踪法”（element chasing）。
- 写清”任取 $x\in X$”与”因此对任意 $x$ 成立”。前者是被证明的对象的引入，后者是把逐点结论升级为集合包含的桥梁（子集定义的 $\forall$）。
第 2 条：$(B\cap C)^{c}=B^{c}\cup C^{c}$。
证明策略。 与第 1 条完全同构，仍然双向包含。逻辑内核换成对偶的那一条：$\neg(P\wedge Q)\iff(\neg P)\vee(\neg Q)$。
完整证明。
设 $B,C$ 是集合。需证 $(B\cap C)^{c}\subset B^{c}\cup C^{c}$ 与 $B^{c}\cup C^{c}\subset(B\cap C)^{c}$。
（I）$(B\cap C)^{c}\subset B^{c}\cup C^{c}$。 任取 $x\in(B\cap C)^{c}$。
- $x\in(B\cap C)^{c}\Rightarrow x\notin B\cap C$。依据： 补集定义。
- $B\cap C=\{x\mid x\in B\ \text{且}\ x\in C\}$，故 $x\notin B\cap C\Rightarrow$ “（$x\in B$ 且 $x\in C$）”为假。依据： 交集定义。
- 由逻辑等价 $\neg(P\wedge Q)\iff(\neg P)\vee(\neg Q)$，”（$x\in B$ 且 $x\in C$）”为假 $\Rightarrow$ $x\notin B$ 或 $x\notin C$。依据： 命题逻辑（De Morgan 的对偶形式）。
- 分情形：情形 (a) $x\notin B$： 由补集定义 $x\in B^{c}$，而 $B^{c}\subset B^{c}\cup C^{c}$（并集定义），故 $x\in B^{c}\cup C^{c}$。情形 (b) $x\notin C$： 同理 $x\in C^{c}\subset B^{c}\cup C^{c}$。两种情形都得 $x\in B^{c}\cup C^{c}$，由分情形（casework）论证结论总成立。依据： 或命题的消去律（proof by cases）。
- 因此 $(B\cap C)^{c}\subset B^{c}\cup C^{c}$。依据： 子集定义。
（II）$B^{c}\cup C^{c}\subset(B\cap C)^{c}$。 任取 $x\in B^{c}\cup C^{c}$。
- 由并集定义，$x\in B^{c}$ 或 $x\in C^{c}$。依据： 并集定义。
- 分情形：情形 (a) $x\in B^{c}$： $x\notin B$（补集定义）$\Rightarrow$”（$x\in B$ 且 $x\in C$）”为假（一支已假）$\Rightarrow x\notin B\cap C$（交集定义）$\Rightarrow x\in(B\cap C)^{c}$（补集定义）。情形 (b) $x\in C^{c}$： 同理 $x\notin C\Rightarrow x\notin B\cap C\Rightarrow x\in(B\cap C)^{c}$。
- 两种情形都给出 $x\in(B\cap C)^{c}$，故 $B^{c}\cup C^{c}\subset(B\cap C)^{c}$。依据： 子集定义。
（III）合并。 两个方向均成立，故由 Definition 2 第 2 款 $(B\cap C)^{c}=B^{c}\cup C^{c}$。$\blacksquare$
【证明机制解说】 第 2 条比第 1 条多了一层”分情形”，原因在于路径不同：
- 第 1 条走的路是 两个 $^{c}$ 的信息合起来（$x\notin B$ 且 $x\notin C$），所以到达 $B^{c}\cap C^{c}$ 时”且”已经就位，不需要分情形。
- 第 2 条走的路是 一条”或”的信息（$x\notin B$ 或 $x\notin C$），而要落到 $B^{c}\cup C^{c}$ 上必须”分头处理”：既然不知道是哪一支成立，就必须假设两支分别成立并各自推出结论。这就是 proof by cases。
请特别注意方向 (II) 中，”$x\notin B$” 加上”且”命题的假：一个”且”命题只要有一支假就整体假。因此 (II) 甚至比 (I) 更简单——它不需要把两支都排掉，只需要排掉一支。
这两条合起来还揭示了 De Morgan 定律的美感（对偶性）：把 $\cup\leftrightarrow\cap$、$^{c}$ 保留，等式依然成立。你甚至可以猜出第 3、4 条也满足同类对偶：$A\setminus(\cdot)$ 相对于 $A$ 扮演了”局部补集”的角色，$A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$ 就是 (1) 的”相对化”版本。
【证明技巧总结】
- 遇到”或”：一定分情形（proof by cases）。写下”情形 (a)”、”情形 (b)”，各自推到同一个结论。
- 遇到”且”：可同时使用两支信息，不必分情形。这是判断”要不要分情形”的快速准则。
- 逻辑律与集合律一一对应：$\neg(P\vee Q)\equiv(\neg P)\wedge(\neg Q)$ 对应本题第 1 条；$\neg(P\wedge Q)\equiv(\neg P)\vee(\neg Q)$ 对应本题第 2 条。记住这个对应表，集合恒等式的证明就变成了”翻译练习”。
- 不要忘记(I)和(II)的假设是不同的。(I) 从 $x\in$ 左边出发，(II) 从 $x\in$ 右边出发，两段的推理链方向相反。混在一起写是本类证明最常见的失分点。
Axiom 5（Well-ordering property，良序原理）
Axiom 5（良序原理）。 $\mathbb{N}$ 的良序性质是指：若 $S\subset\mathbb{N}$，则存在 $x\in S$ 使得对一切 $y\in S$ 都有 $x\le y$。换言之，$S$ 总有最小元素。
源文件紧接着强调：注意这是一条公理，因此我们必须不加证明地假设它。
精确陈述与推论。 严格地写：
\[\forall S\subseteq\mathbb{N},\ \left(S\neq\emptyset\ \Rightarrow\ \exists x\in S,\ \forall y\in S:\ x\le y\right).\]（源文件把”若 $S\subset\mathbb{N}$ 则存在最小元”写在空集上略有语病：空集没有最小元。正确的形式必须显式写出 $S\neq\emptyset$。请以 $S\neq\emptyset$ 的版本为准。）
直观解释。 良序原理说的是”$\mathbb{N}$ 里不能无限往下降“：任何非空的自然数集合都有一个起点。等价地说，不存在无穷严格递减的自然数序列 $a_1>a_2>a_3>\cdots$。这一点使 $\mathbb{N}$ 与 $\mathbb{Z}$、$\mathbb{Q}$、$\mathbb{R}$ 截然不同：
- $\mathbb{Z}$ 不是良序的：$\mathbb{Z}$ 本身非空但没有最小元。
- $\mathbb{Q}$ 不是良序的：$\{1/n\mid n\in\mathbb{N}\}$ 非空但没有最小元（$0$ 是下确界但不属于该集合）。
- $\mathbb{R}$ 更不是：$(0,1)$ 非空无最小元。
- $\mathbb{N}$ 是良序的：$\{7,3,11\}$ 的最小元是 $3$；$\{n\in\mathbb{N}\mid n>100\}$ 的最小元是 $101$。
为什么它必须是公理？ 因为要”证明”良序原理，你必须先有关于 $\mathbb{N}$ 的某种刻画，而 $\mathbb{N}$ 的刻画方式有两种标准选法：
- 以 Peano 公理为起点，把归纳法原理（或等价地，良序原理）取作公理之一；
- 以良序原理为起点，证明归纳法（这正是 Theorem 6 所做的）。
这两种做法是”公理的选择”问题，不是数学定理的推导问题。源文件选择了路线 2，所以良序原理是本课程对 $\mathbb{N}$ 的基本假设。初学者最常见的错误，就是把良序原理当成一个”显然的、可以证的事实”——它不是被证明的，而是被假设的；它的”明显性”来自我们对 $1,2,3,\dots$ 的直观，而公理的作用正是把这种直观固定下来。
用途预览。 Axiom 5 在整个 18.100A 中主要作为一个”工具性公理”出现：Theorem 6 用它证明归纳法，归纳法再用遍全课程。此外，Lecture 9 中构造子序列时会用到”在无穷多个指标中取最小者”这一动作，其合法性也来自良序原理。没有良序原理，就没有归纳法；没有归纳法，本课程几乎无法起步。
Theorem 6（Induction，数学归纳法）
Theorem 6（Induction）。 这个概念由 Pascal 于 1665 年发明。设 $P(n)$ 是一个依赖于 $n\in\mathbb{N}$ 的命题。假设：
- （基础情形 base case）$P(1)$ 为真，且
- （归纳步 inductive step）若 $P(m)$ 为真，则 $P(m+1)$ 为真。
则 $P(n)$ 对一切 $n\in\mathbb{N}$ 为真。
精确陈述。
\[\Big(P(1)\ \wedge\ \forall m\in\mathbb{N}\,\big(P(m)\Rightarrow P(m+1)\big)\Big)\ \Longrightarrow\ \forall n\in\mathbb{N}\,P(n).\]证明策略（源文件给出的路线）。 这是一个”对一切 $n$”的命题，直接逐个验证不可能。策略是反证法 + 良序原理：
- 把”反例的集合”收集起来，定义为 $S=\{n\in\mathbb{N}\mid P(n)\ \text{不真}\}$；
- 目标变成证明 $S=\emptyset$；
- 假设 $S\neq\emptyset$，用良序原理取最小元 $m$；
- 用基础情形说明 $m\neq1$，从而 $m-1\in\mathbb{N}$；
- 用 $m$ 的最小性得到 $P(m-1)$ 为真；
- 用归纳步得到 $P(m)$ 为真，与 $m\in S$ 矛盾。
完整证明（逐步，每步注明依据）。
证明。 设 $S=\{n\in\mathbb{N}\mid P(n)\ \text{不真}\}$。
我们想要证明的是 $S=\emptyset$。 这一步是”转化目标”：$\forall n\in\mathbb{N}\,P(n)$ 为真 $\iff$ 不存在 $n$ 使 $P(n)$ 为假 $\iff S=\emptyset$。依据： $S$ 的定义与集合相等的含义。
我们用反证法来证明它。（依据：Remark 7——反证法是”假设我们要的结论为假，然后推出假命题”。）因此，本例中我们假设 $S\neq\emptyset$ 并推出一句假话。
- 假设 $S\neq\emptyset$。 依据： 反证法的假设。
- 由 $\mathbb{N}$ 的良序性质，$S$ 有最小元 $m\in S$。 依据： Axiom 5（这是整条证明中唯一使用公理的地方；此步的合法性完全依赖于 $S\subseteq\mathbb{N}$ 且 $S\neq\emptyset$）。
- 由于 $P(1)$ 为真，故 $m\neq1$，即 $m>1$。 依据： 基础情形假设 + $m\in S$ 意味着 $P(m)$ 不真；若 $m=1$，则 $P(1)$ 同时为真与不真，不可能。又 $m\in\mathbb{N}=\{1,2,3,\dots\}$，故 $m\neq1\Rightarrow m>1$。（此处用到 $\mathbb{N}$ 与 $<$ 的次序性质，本讲按”$\mathbb{N}$ 有次序 $1<2<3<\cdots$”使用。）
- 由于 $m$ 是 $S$ 的最小元，$m-1\notin S$，即 $P(m-1)$ 为真。 依据： $m$ 的最小性（对一切 $y\in S$ 有 $m\le y$）+ $m-1<m$。注意 $m-1\in\mathbb{N}$：因为 $m>1$ 且 $m\in\mathbb{N}$，所以 $m-1\ge1$。（这一步是初学者最容易漏写的”合法性检查”：必须先确认 $m-1$ 仍在 $\mathbb{N}$ 中，才能谈 $P(m-1)$，因为 $P$ 只对 $\mathbb{N}$ 中的 $n$ 定义。）
- 由归纳步假设（$P(m-1)\Rightarrow P(m)$），$P(m)$ 为真。 依据： 归纳步假设（取其中的 $m$ 为 $m-1$；因 $m-1\in\mathbb{N}$，代入合法）。
- 故 $m\notin S$。 依据： $S$ 的定义（$S$ 只收 $P$ 不真的 $n$）。
- 但 $m\in S$ 且 $m\notin S$，这是矛盾。 依据： 第 2 步与第 6 步；矛盾律（$m\in S$ 与 $m\notin S$ 不能同真）。
- 因此 $S=\emptyset$，从而 $P(n)$ 对一切 $n\in\mathbb{N}$ 为真。 $\blacksquare$ 依据： 反证法（由假设 $S\neq\emptyset$ 推出矛盾，故 $S\neq\emptyset$ 为假，即 $S=\emptyset$）+ 第 0 步的转化。
【证明机制解说】 这条证明的骨架是一个漂亮的”极小反例（minimal counterexample）“论证。它的内核思想是：
\[\text{若存在反例，则存在} \textbf{最小的} \text{反例。}\]然后对这个最小反例 $m$ 施加”两面夹击”：一方面，$m$ 最小 $\Rightarrow m-1$ 不是反例 $\Rightarrow P(m-1)$ 真；另一方面，归纳步 $\Rightarrow P(m-1)$ 真蕴含 $P(m)$ 真。于是 $m$ 既在 $S$ 中（它是反例）又不在 $S$ 中（$P(m)$ 真），矛盾。矛盾的全部力量来自”$m$ 的最小性”与”归纳步”的对撞。
值得注意的是：这条证明里基础情形 $P(1)$ 的作用非常具体，它只被用了一次——用来保证 $m\neq1$，从而使 $m-1$ 有意义。如果缺少基础情形，$m$ 可能是 $1$，那么 $m-1=0\notin\mathbb{N}$，第 4 步就无法进行，整个论证断裂。这解释了为什么归纳法必须有基础情形：它不是”顺手验证一下”，而是把”下降一步”这个动作在到达边界时截停。
还要注意逻辑链条的方向：归纳步假设的是 $P(m-1)\Rightarrow P(m)$（顺着 $m-1$ 到 $m$ 的升方向），而证明中我们是沿着降方向从 $m$ 走到 $m-1$，再用升方向的蕴含走回 $m$。这种”降一步、升一步”的往返，是极小反例论证的标志。
【证明技巧总结】
- 归纳法的标准文本结构：(i) 明确定义 $P(n)$；(ii) 验证 $P(1)$（写出计算/推理）；(iii) “假设 $P(k)$ 为真”（必须原样写下归纳假设，它是后面唯一可用的资源）；(iv) 从归纳假设推出 $P(k+1)$；(v) 引用定理收尾，明确说出”由归纳法，$P(n)$ 对一切 $n\in\mathbb{N}$ 成立”。
- 归纳假设要”抄一遍”。Theorem 8、Theorem 9 的证明中都把假设等式完整重写了一行；这不是啰嗦，而是把可用资源显式摆在桌面上。
- 不要把 $P(k+1)$ 的结论当前提用。常见错误是从”$P(k+1)$ 应该等于什么”出发去变形，这是循环论证；正确方向是从 $P(k)$ 的表达式出发，加上一项或乘一个因子，算出 $P(k+1)$ 的样子。
- 基础情形不能省，也不能从 $n=0$ 乱起。本课程 $\mathbb{N}=\{1,2,\dots\}$，所以基础情形是 $n=1$。若命题实际只对 $n\ge2$ 有意义（例如”$\sqrt{n+1}$ 与 $\sqrt{n}$ 的比较”），则改取 $P(2)$ 为基础情形即可，但必须说明。
- 证明的合法性细节要交代：如 $m-1\in\mathbb{N}$、$1+c>0$、$mc^{2}\ge0$ 这类”为了让下一步成立”的小检查，正是严格证明与草稿的分界线。
Remark 7（反证法的逻辑说明）
Remark 7。 当我们用反证法（proof by contradiction）证明某事时，我们假设我们想要的结论是假的，然后证明我们会到达一个假命题。逻辑规则因此蕴含：最初的假设（即”结论为假”）必定是假的。所以在这个情形下，我们会假设 $S\neq\emptyset$ 并推出一个假命题。
展开说明。 反证法的逻辑形式是：
\[\Big(\neg Q\Rightarrow(P\wedge\neg P)\Big)\ \Longrightarrow\ Q .\]也常写作：若从 $\neg Q$ 能推出矛盾，则 $Q$ 成立。它的合法性来自经典逻辑中的排中律（law of excluded middle）：$Q$ 与 $\neg Q$ 必有一个为真；既然 $\neg Q$ 会导出矛盾（因而不可能为真），那么只能是 $Q$ 为真。
三种易混的证明法，请务必区分。
| 方法 | 你要假设什么 | 你要推出什么 |
|---|---|---|
| 直接证明（direct proof） | $P$ | $Q$ |
| 逆否证明（contrapositive） | $\neg Q$ | $\neg P$ |
| 反证法（contradiction） | $\neg Q$（通常还加上已知前提 $P$） | 任何矛盾 $R\wedge\neg R$ |
注意二者在实践中的微妙差别。 证明”$A\subset B$”时，逆否形式是”$x\notin B\Rightarrow x\notin A$”，往往比直接形式更好写；而 Theorem 6 的证明中，我们假设的是”$\forall n\,P(n)$ 为假”，即”$\exists n$ 使 $P(n)$ 为假”，这比逆否形式多了存在性的内容，正是这一点让我们能调用良序原理取出具体的 $m$。记住这个模式：反证法的钥匙常常是”把否定转化为存在”，再用良序原理/极限定义把存在对象抓在手里。
一个易犯的错。 反证法里推出的”假命题”必须是真正的矛盾（如 $m\in S$ 且 $m\notin S$，或 $0=1$），不能只是”与我的直觉不符”或”看起来很奇怪”。Theorem 6 的证明之所以干净，就在于它最终落到一个明确的、形式化的矛盾上。
Theorem 8（等比级数求和）
Theorem 8。 对一切实数 $c\neq1$ 以及一切 $n\in\mathbb{N}$， \(1+c+c^{2}+\cdots+c^{n}=\frac{1-c^{n+1}}{1-c}.\)
证明策略。 断言对”一切 $n\in\mathbb{N}$”成立，所以用（Theorem 6 的）归纳法。取
\[P(n):\quad 1+c+c^{2}+\cdots+c^{n}=\frac{1-c^{n+1}}{1-c}.\]基础情形直接计算；归纳步把 $P(k)$ 的等式两边同加 $c^{k+1}$，再用代数化简凑出 $P(k+1)$ 的右端。
完整证明。
证明。 我们用归纳法证明。
基础情形（$n=1$）。 方程的左边在 $n=1$ 时是 $1+c$。右边是
\[\frac{1-c^{2}}{1-c}=\frac{(1-c)(1+c)}{1-c}=1+c .\]（中间的因式分解 $1-c^{2}=(1-c)(1+c)$ 用的是平方差公式；最后的约分用到 $c\neq1$，故 $1-c\neq0$，除法合法——这正是定理假设 $c\neq1$ 的作用。）左右两边相等，故基础情形得证。依据： 直接计算 + 因式分解 + $c\neq1$ 保证分母非零。
归纳步。 假设方程对 $k\in\mathbb{N}$ 成立，即
\[1+c+c^{2}+\cdots+c^{k}=\frac{1-c^{k+1}}{1-c}. \tag{IH}\]依据： 归纳假设（(IH)，induction hypothesis）。
于是
\[\begin{aligned} 1+c+c^{2}+\cdots+c^{k}+c^{k+1} &=(1+c+c^{2}+\cdots+c^{k})+c^{k+1} &&\text{加法结合律（把前 $k+1$ 项打包）}\\ &=\frac{1-c^{k+1}}{1-c}+c^{k+1} &&\text{依据 (IH)}\\ &=\frac{1-c^{k+1}+c^{k+1}(1-c)}{1-c} &&\text{通分：}c^{k+1}\text{ 写成 }\tfrac{c^{k+1}(1-c)}{1-c}\\ &=\frac{1-c^{k+1}+c^{k+1}-c^{(k+1)+1}}{1-c} &&\text{分配律：}c^{k+1}(1-c)=c^{k+1}-c^{k+2}\\ &=\frac{1-c^{(k+1)+1}}{1-c} &&\text{合并同类项：$-c^{k+1}+c^{k+1}=0$} \end{aligned}\]最后一行正是 $P(k+1)$ 的断言（把 $P(n)$ 中的 $n$ 换成 $k+1$）。依据： 归纳步由此完成。
结论。 由 Theorem 6（归纳法），$P(n)$ 对一切 $n\in\mathbb{N}$ 成立，即对一切 $c\neq1$ 与一切 $n\in\mathbb{N}$，
\[1+c+c^{2}+\cdots+c^{n}=\frac{1-c^{n+1}}{1-c}.\qquad\blacksquare\]【证明机制解说】 这条证明的机制是”递推 + 代数整理“：命题 $P(n)$ 的左右两侧都随 $n$ 增长，而增长的方式是”加一项 $c^{n+1}$”。归纳法的任务就是验证左侧的递推规则（加一项）在右侧也有对应的递推规则（把 $c^{n+1}$ 的指数升 1）。关键的中间步骤是通分：
\[\frac{1-c^{k+1}}{1-c}+c^{k+1}=\frac{1-c^{k+1}+c^{k+1}-c^{k+2}}{1-c}=\frac{1-c^{k+2}}{1-c}.\]
注意 $-c^{k+1}$ 与 $+c^{k+1}$ 恰好抵消，这就是”指数从 $k+1$ 变成 $k+2$”的代数机制。这个”错位相消（telescoping 的味道）”在后续课程里还会以各种形式出现（例如 Lecture 8 中处理 $(x^{n}-y^{n})/(x-y)$、以及级数的部分和）。
另一处必须记住的是假设 $c\neq1$ 的位置：它只在”$1-c\neq0$、可以作除数”这一点上被用到，其余地方的代数恒等式对所有 $c$ 成立。若 $c=1$，左边是 $n+1$，右边是 $0/0$ 无意义，等式不成立——所以 $c\neq1$ 不是技术性摆设，而是命题有意义的前提。这正是”每个假设都要检查它在哪里被用到”的范例。
【证明技巧总结】
- 归纳步的目标要提前写下来。在动手前先写下 $P(k+1)$ 的样子：$1+c+\cdots+c^{k+1}=(1-c^{k+2})/(1-c)$。目标是这个形状，中间步骤就变成了”朝着它变形”。
- 从 $P(k)$ 的左侧出发，加上新的一项——这是所有”求和型”命题的标准起点。（反面做法：从 $P(k+1)$ 出发减去一项，虽然有时可行，但更容易变成循环论证。）
- 通分时把 $1-c$ 留在分母，不要图省事用 $1/(1-c)$ 之类记号，保持分母统一可以在最后一步立刻看出指数形式。
- 检查假设的使用点：本定理的 $c\neq1$ 用在基础情形的约分与每一步的分母合法性上。写证明时若能指出这一点，说明你真的读懂了定理。
- 基础情形要算，不能写”显然成立”。这里 $n=1$ 的计算包含因式分解，是基础情形里唯一有内容的地方。
Theorem 9（Bernoulli 不等式）
Theorem 9。 对一切 $c\ge-1$ 以及一切 $n\in\mathbb{N}$，$(1+c)^{n}\ge1+nc$。
证明策略。 又是”对一切 $n\in\mathbb{N}$”的命题，用归纳法。基础情形是等号；归纳步把 $(1+c)^{m}$ 乘上因子 $(1+c)$，用归纳假设作下界估计，再扔掉非负项 $mc^{2}$。
完整证明（源文件证明的逐步展开）。
证明。 我们通过归纳法证明。
基础情形（$n=1$）。 $(1+c)^{1}=1+1\cdot c$。依据： 直接计算（两端都是 $1+c$，取等号）。✅
归纳步。 假设
\[(1+c)^{m}\ge1+mc. \tag{IH}\]依据： 归纳假设。
则
\[\begin{aligned} (1+c)^{m+1} &=(1+c)^{m}\cdot(1+c) &&\text{指数法则 } a^{m+1}=a^{m}\cdot a\\ &\ge(1+mc)\cdot(1+c) &&\text{由 (IH) 两边同乘 } 1+c\\ &\phantom{\ge}\quad\text{（合法性：}c\ge-1\Rightarrow 1+c\ge0\text{，方向不变）}\\ &=1+(m+1)c+mc^{2} &&\text{展开：}(1+mc)(1+c)=1+c+mc+mc^{2}\\ &\ge1+(m+1)c. &&\text{因为 } mc^{2}\ge0\text{（$m\\in\\mathbb{N}$ 故 } m>0\text{，且 } c^{2}\ge0\text{）} \end{aligned}\]依据： 指数法则；归纳假设；$c\ge-1$；分配律；实数平方的非负性。
由归纳法，我们的证明完成。 即 $\forall c\ge-1,\ \forall n\in\mathbb{N}:\ (1+c)^{n}\ge1+nc$。$\blacksquare$
【证明机制解说】 这条证明有两个技术要点，都必须点名：
要点一：为什么必须 $c\ge-1$？ 不等式 $a\ge b$ 两边同乘一个数 $t$ 时，只有当 $t\ge0$ 才能保持方向（若 $t<0$，方向翻转）。此处 $t=1+c$，所以需要 $1+c\ge0$，即 $c\ge-1$。如果 $c<-1$，则 $1+c<0$，乘上去不等号反向，归纳步崩溃。定理的假设精确地对应了这个需求——这是”假设不是摆设”的第二个范例。
要点二：为什么要扔掉 $mc^{2}$？ 我们算出了 $1+(m+1)c+mc^{2}$，但目标只是 $1+(m+1)c$。不等式方向是 $\ge$，所以舍弃一个非负项是正确的（右端变小，不等式仍成立）。这里 $m>0$ 与 $c^{2}\ge0$ 保证了 $mc^{2}\ge0$。注意若 $m$ 允许为 $0$，则 $mc^{2}=0$，也仍然 $\ge0$，所以这一步其实是稳健的；但 $m\in\mathbb{N}$ 时我们连 “$c^{2}$ 必须真的正” 都不需要担心。
这条不等式为什么重要？ 它给出的是”指数增长至少是线性增长”的定量控制。等价地，令 $x=1+c\ge0$，则 $x\ge1$ 时 $x^{n}\ge1+n(x-1)$。这是整个课程中把”$n$ 很大”翻译成”$c^{n}$ 很大”的唯一初等工具，Lecture 8 的 Theorem 94 正是这样使用它（详见”与其他讲次的关联”）。
【证明技巧总结】
- 乘一个因子时先问方向：”两边同乘 $1+c$，不等号方向是否保持？”——需要 $1+c\ge0$，于是定理假设 $c\ge-1$ 被自然地”推导”出来。养成”假设从需求中生成”的意识，你就能自己猜出定理的正确形式。
- $\ge$ 的证明常用”多算一点然后扔掉”。算出精确值 $1+(m+1)c+mc^{2}$，再丢掉非负项得到下界。看到”$\ge$ 且右边更简单”的题型，第一反应就该是”找一项可以扔的非负项”。
- 幂的递推用指数法则显式写出：$(1+c)^{m+1}=(1+c)^{m}(1+c)$。不要跳步。
- 结尾必须显式引用归纳法定理。源文件写”By induction, our proof is complete”——这句话不是客套，它是把 $P(1)$ 与 $P(m)\Rightarrow P(m+1)$ 组装成 $\forall n\,P(n)$ 的那一步（依赖 Theorem 6）。
归纳法与良序原理的证明结构流程图
┌───────────────────────────────────────────────┐
│ Axiom 5 良序原理 (只能假设, 不可证明) │
│ S ⊆ N 且 S ≠ ∅ ⟹ S 有最小元 m │
└────────────────────┬──────────────────────────┘
│ 唯一公理工具
▼
┌───────────────────────────────────────────────┐
│ Theorem 6 归纳法: 证 ∀n∈N, P(n) │
│ 改写目标: 证 S = {n : P(n) 假} = ∅ │
└────────────────────┬──────────────────────────┘
│ 反证法 (Remark 7)
▼
假设 S ≠ ∅
↓ 良序原理 → 取最小反例 m ∈ S
↓ base case P(1) 真 → m ≠ 1 ⟹ m − 1 ∈ N
↓ m 最小 → m − 1 ∉ S 即 P(m−1) 真
↓ 归纳步 → P(m−1) ⟹ P(m), 故 P(m) 真 ⟹ m ∉ S
↓
m ∈ S 且 m ∉ S ⇐ 矛盾! 故假设为假
▼
S = ∅ ⟹ ∀n∈N, P(n) 成立
│ 作为常规工具反复使用
▼
┌───────────────────────────────────────────────┐
│ Theorem 8 等比求和 / Theorem 9 Bernoulli (归纳)│
│ ↓ 后续: L3 Cor.18 · L5 三角不等式推广 · │
│ L8 Remark 90 / Thm 94 · L9 子序列 │
└───────────────────────────────────────────────┘
与教材的对应
本讲对应 Lebl, Basic Analysis I §0.3（Basic set theory / 基本集合论），以及紧接着的归纳法部分。两次作业的对应关系如下。
Assignment 1（Reading Section 0.3）
| 题号 | 内容 | 这一题在练什么（一句话） |
|---|---|---|
| 1 | Exercise 0.3.6 | 用双向包含法证明一个集合恒等式，把”集合等式必须两个方向”的模板练成肌肉记忆。 |
| 2 | Exercise 0.3.11 | 处理补集与论域的关系（如 $A\setminus B=A\cap B^{c}$ 一类恒等式），练习”补集依赖于论域”这一细节。 |
| 3 | Exercise 0.3.12 | 练习多重集合运算的化简与分情形论证（proof by cases），把 Theorem 4 的技术推广到更复杂的表达式。 |
| 4 | Exercise 0.3.15 | 练习集合包含关系的传递性与”元素追踪法”，巩固 $\subset$ 与 $\subsetneq$ 的区别。 |
| 5 | Exercise 0.3.19 | 把集合恒等式写成”对一切 $x$，$x\in$ 左 $\iff x\in$ 右”的逐点形式，训练 $\iff$ 与双向包含的等价使用。 |
| 6 | 证明 $\lvert\{q\in\mathbb{Q}:q>0\}\rvert=\lvert\mathbb{N}\rvert$ | 本讲与 Lecture 2 的桥梁：用唯一素因子分解（unique prime factorization）构造函数 $f:\{q\in\mathbb{Q}:q>0\}\to\mathbb{N}$ 并证明它是双射——训练”用 $\exists!$（存在且唯一）同时拿下单射与满射”，这正是 Lecture 2 基数理论（Definition 11）的核心技能。 |
Assignment 1 第 6 题的补充说明（因为它对 Lecture 2 的关联最直接）。 题目给出并允许不加证明地使用一个定理：对 $q\in\mathbb{Q},\ q>0$，若 $q\in\mathbb{N}\setminus\{1\}$ 则 $q$ 有唯一的素因子分解 $q=p_1^{r_1}p_2^{r_2}\cdots p_N^{r_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}}$，其中 $p_i,q_j$ 为互不相同的素数、指数为正整数，且这种写法唯一。定义 $f(1)=1$，对 $q\in\mathbb{N}\setminus\{1\}$ 取 $f(q)=p_1^{2r_1}\cdots p_N^{2r_N}$，对 $q\in\mathbb{Q}\setminus\mathbb{N}$ 取 $f(q)=p_1^{2r_1}\cdots p_N^{2r_N}q_1^{2s_1-1}\cdots q_M^{2s_M-1}$。第 (a) 问要求计算 $f(4/15)$ 并求出满足 $f(q)=108$ 的 $q$；第 (b) 问要求用该定理证明 $f$ 是双射。
- 训练点 1：“存在且唯一”如何同时给出单射与满射——存在性（$\exists$）保证 $f$ 的定义良定且满射，唯一性（$\exists!$）保证 $f$ 可逆因而单射。
- 训练点 2：指数奇偶性的编码技巧——分子用偶指数、分母用奇指数，于是”分子/分母”这一信息被嵌进了指数的奇偶性里，这正是构造双射时”把两份信息打包进一个数”的经典手法。
- 训练点 3：与 Lecture 2 的 Example 13 第 3 条（$\lvert\{q\in\mathbb{Q}:q>0\}\rvert=\lvert\mathbb{N}\rvert$）是同一个命题——Lecture 2 明确把它”留作 Assignment 1 的练习”。所以这道题是把两讲缝合起来的关节。
Assignment 2（Reading Sections 0.3, 1.1, 1.2）
| 题号 | 内容 | 这一题在练什么（一句话） |
|---|---|---|
| 1 | Exercise 1.1.1 | 练习实数/有理数的代数性质与基本不等式技巧，为 §1.1 的绝对值与不等式打底。 |
| 2 | Exercise 1.1.2 | 练习绝对值（absolute value）的运算与三角不等式的初等用法。 |
| 3 | Exercise 1.1.5 | 由已知不等式推导新不等式，训练”从定义出发变形”而非依赖直觉。 |
| 4 | Exercise 1.1.6 | 练习上界、下界与确界（supremum/infimum）的基本判定。 |
| 5 | Exercise 1.2.7 | 练习最小上界性质（least upper bound property）的应用，判断集合是否有上界并求 $\sup$。 |
| 6 | Exercise 1.2.9 | 练习用确界的定义（既是上界又是最小上界）进行严格论证。 |
| 7 | $E=\{x\in\mathbb{R}:x>0,\ x^{3}<2\}$：证 $E$ 有上界；令 $r=\sup E$，证 $r>0$ 且 $r^{3}=2$ | 本课程的”第一个真正的分析证明”：先说 $2$ 是上界（因为 $x^{3}<2<8=2^{3}\Rightarrow x<2$），再由最小上界性质取 $r=\sup E$，然后用”微小扰动”论证排除 $r^{3}<2$ 与 $r^{3}>2$ 两种情形，从而 $r^{3}=2$——这正是 Lecture 3 中证明 $\mathbb{Q}$ 有”洞”而 $\mathbb{R}$ 没有的技术原型（题目提示”Adapt the proof used in Example 1.2.3”）。 |
把两次作业连起来看。 Assignment 1 训练的是本讲的两种语言工具（双向包含、双射构造）；Assignment 2 训练的是下一阶段的实数结构工具（绝对值、上确界、最小上界性质）。本讲的 Theorem 8 与 Theorem 9 则是这两次作业各自都会用到的”计算/估计引擎”。如果本讲学得扎实，Assignment 1 会显得温和平常；如果本讲敷衍过去，Assignment 2 第 7 题几乎一定写不出来。
与其他讲次的关联
本讲是全课程的地基，五条关联线索必须具体记住：
① 良序原理 → 归纳法 → 后续一切”对一切 $n$”的命题。 这一条链条的每一环都在本讲内完成：Axiom 5（唯一假设）⟹ Theorem 6（归纳法）⟹ Theorem 8、Theorem 9 的证明。此后整门课程中每一句形如”$\forall n\in\mathbb{N}$”的断言，其证明的最终依据都追溯到本条链。 例如 Lecture 3 的 Corollary 18（对一切 $n\in\mathbb{N}\cup\{0\}$ 有 $n<2^{n}$，源文件的 Remark 19 指出”这也可用归纳法证明，见 Assignment 1”）；再如 Lecture 8 的 Remark 90（$\lim_{n\to\infty}(x_n)^{k}=x^{k}$，源文件明确说”By induction, one can prove that”）。当你看到一句”对一切 $n$”却没有任何证明时，作者省略的通常就是归纳法。
② Bernoulli 不等式（Theorem 9）→ Lecture 8 的 Theorem 94。 这是本讲最重要的一条对外关联。Lecture 8 的 Theorem 94 断言：若 $0<c<1$ 则 $\lim_{n\to\infty}c^{n}=0$；若 $c>1$ 则 $\{c^{n}\}$ 无界。在证明后半部分时，Lecture 8 取 $B\ge0$，选择 $n\in\mathbb{N}$ 使 $n>\dfrac{B}{c-1}$，然后写出
\[c^{n}=\bigl(1+(c-1)\bigr)^{n}\ \ge\ 1+n(c-1)\ \ge\ n(c-1)>B,\]并特别注明：”To see why this center inequality is true, see the last theorem shown in Lecture 1.“（要理解中间这个不等式为何成立，请看 Lecture 1 最后那个定理。——即 Theorem 9。）取 $c-1>-1$（因 $c>1$ 故 $c-1>0\ge-1$），Theorem 9 的假设满足，于是得到 $c^{n}\ge1+n(c-1)$。所以 Theorem 9 不是一道”不等式练习题”，而是 Lecture 8 证明指数序列无界性的关键一步。 请把这句话背下来：“$c>1$ 时 $c^{n}$ 增长得比任何线性函数都快，依据是 Bernoulli 不等式。”
③ 集合与双向包含 → Lecture 3 的 Cantor 定理证明。 Lecture 3 的 Theorem 15（Cantor）：若 $A$ 是集合，则 $\lvert A\rvert<\lvert\mathcal{P}(A)\rvert$。其证明是”对角线法”：反设 $\lvert A\rvert=\lvert\mathcal{P}(A)\rvert$，则存在满射 $g:A\to\mathcal{P}(A)$，构造
\[D:=\{x\in A\mid x\notin g(x)\}\in\mathcal{P}(A),\]再由 $g$ 的满射性取出 $b\in A$ 使 $g(b)=D$，然后分两种情形（$b\in D$ 与 $b\notin D$）各推出矛盾。请注意这条证明用到的正是本讲的三件东西：
- 集合构造记号 $\{x\in A\mid P(x)\}$，其中 $P(x)$ 是”$x\notin g(x)$”（对应本讲第 4 小节）；
- $b\in D$ 与 $b\notin D$ 的二分，这正是 Remark 7 式的反证法 + 分情形论证；
- 集合相等靠双向包含——在 Cantor 的证明里以 $g(b)=D$ 的形式出现，逐点展开后就是 $x\in g(b)\iff x\in D$，即两个包含方向。
特别提示：$D$ 与 De Morgan 定律在精神上同源。 $D$ 的定义中”$x$ 不在 $g(x)$ 里”就是把”属于”的补集放进集合构造记号里，而 Theorem 4 教你的正是如何处理这种”$\notin$”。换言之，Cantor 定理的证明 = 集合构造记号 + 双向包含 + 反证法 + 分情形，全是 Lecture 1 的库存。
④ Problem 3 → Lectures 3、4。 “如何描述 $\mathbb{R}$”的答案分两步给出。Lecture 3 揭示问题的症结：$\mathbb{Q}$ 缺少最小上界性质（源文件 Lecture 3 的标题就是 “Cantor’s Remarkable Theorem and the Rationals’ Lack of the Least Upper Bound Property”），并在 Theorem 22 给出目标刻画：”存在唯一的、包含 $\mathbb{Q}$ 的、具有最小上界性质的有序域，我们记之为 $\mathbb{R}$“。Lecture 4 则完成构造性回答（用 Dedekind 分割或等价方式真正把 $\mathbb{R}$ “造”出来）。所以 Problem 3 是全课程第一个被提出、跨两讲才被解决的问题，值得在笔记里单独标注”未决”直到 Lectures 3–4 讲完。
⑤ 归纳法 → Lecture 5 三角不等式推广、Lecture 8 Remark 90、Lecture 9 子序列下标 $k\le n_k$。 具体地说：
- Lecture 5 中把三角不等式 $\lvert x+y\rvert\le\lvert x\rvert+\lvert y\rvert$ 推广到任意有限多项 $\left\lvert\sum_{i=1}^{n}x_i\right\rvert\le\sum_{i=1}^{n}\lvert x_i\rvert$，标准做法就是对 $n$ 作归纳（基础情形 $n=1$ 是恒等式，$n=2$ 是三角不等式本身，归纳步再对两个”块”用一次三角不等式）。
- Lecture 8 的 Remark 90 断言 $\lim_{n\to\infty}(x_n)^{k}=x^{k}$（其中 $x_n\to x$），源文件直接注明”By induction, one can prove that”——归纳的对象是幂次 $k$。
- Lecture 9 处理子序列（subsequence）时必须用到 $k\le n_k$（子序列的第 $k$ 项下标至少是 $k$），这一事实的标准证明也是对 $k$ 作归纳，且其”为什么不能无限下降”的直觉正来自良序原理。
一句话总结全部关联： 本讲给了你语言（集合记号、$\in,\subset,\iff$）、证明模板（双向包含、分情形、反证法）与唯一公理工具（良序原理 → 归纳法）。Lectures 3 到 10 的每一页都在使用这三样东西，而你之所以能在 Lecture 8 里说出”$c^{n}$ 无界”，是因为你在 Lecture 1 的最后一页学了 Bernoulli 不等式。
关键要点
- Remark 1 的两大目标是本课程的灵魂：一是”证明的经验”（读 + 写），二是”关于实数、函数与极限的命题”。微积分重计算、实分析重证明；$\lim\frac{n^{2}}{n^{2}+n+1}=1$ 在微积分里是计算，在这里是要用 $\epsilon$-$N$ 证明的命题（Lecture 8）。
- 集合相等的定义就是双向包含：$A=B\iff(A\subset B\ \text{且}\ B\subset A)$。因此凡证集合相等，必写两个方向；只证一个方向是逻辑上不完整的。
- $\subset$ 与 $\subsetneq$ 不同：$\subset$ 允许相等，$\subsetneq$ 要求不等。$A\subsetneq B$ 的证明 = “$A\subset B$” + “找一个 $b\in B$ 而 $b\notin A$”。
- 空集 $\emptyset$ 与 $\{\emptyset\}$ 不同：前者有 $0$ 个元素，后者有 $1$ 个元素。
- 所有集合恒等式的证明都回到”元素追踪法”：把 $\cup,\cap,\setminus,{}^{c}$ 全部展开成 $\in/\notin$，再用逻辑律（尤其 De Morgan 的逻辑版本）推进。
- Theorem 4 的四条 De Morgan 定律中，源文件完整示范了第 1 条；其证明结构是”双向包含 + 元素追踪”。第 2 条的证明额外需要分情形（proof by cases），因为”或”的信息必须分头处理。
- Axiom 5（良序原理）是不可证明的公理：$\mathbb{N}$ 的每个非空子集有最小元。它是本课程对 $\mathbb{N}$ 的唯一基本假设，也是 Theorem 6 证明中唯一使用公理的地方。
- Theorem 6（归纳法）由良序原理通过反证法证明，核心是”极小反例 $m$”：$P(1)$ 真 ⟹ $m\neq1$ ⟹ $m-1\in\mathbb{N}$ ⟹ $P(m-1)$ 真 ⟹ $P(m)$ 真，与 $m\in S$ 矛盾。基础情形的真正作用是让”下降一步”在边界处停下。
- Theorem 8 的等比求和公式在 $c\neq1$ 时成立；$c\neq1$ 的作用仅仅是保证分母 $1-c$ 非零。
- Theorem 9（Bernoulli 不等式）$(1+c)^{n}\ge1+nc$ 对 $c\ge-1$ 成立；$c\ge-1$ 的作用是保证同乘 $1+c$ 时不等号不变向；归纳步中”扔掉非负项 $mc^{2}$”是关键动作。这条不等式是 Lecture 8 Theorem 94 的直接工具。
- Problem 3（$\mathbb{R}$ 是什么）的答案是全课程的第一个悬念，将在 Lectures 3、4 揭晓：$\mathbb{R}$ 是包含 $\mathbb{Q}$ 的唯一具有最小上界性质的有序域。
- 归纳法写作的五件套：明确 $P(n)$ → 证 base case → 抄写归纳假设 → 从假设推 $P(k+1)$ → 引用 Theorem 6 收尾。
常见误区与注意事项
误区 1：证明集合相等时只证一个方向。
- 错误做法： 要证 $A=B$，取 $x\in A$，推出 $x\in B$，然后写”故 $A=B$”。$\blacksquare$
- 为什么错： Definition 2 第 2 款明确要求 $A\subset B$ 且 $B\subset A$ 两件事。只证 $A\subset B$ 得到的是”$A$ 不比 $B$ 大”，完全允许 $A\subsetneq B$ 的情形（例如 $A=\{1\},B=\{1,2\}$ 也满足 $A\subset B$，但 $A\neq B$）。
- 正确做法： 写下两段独立论证——(I) 任取 $x\in A$，证 $x\in B$；(II) 任取 $x\in B$，证 $x\in A$。最后引 Definition 2 第 2 款合并。两段的出发假设不同，中间推理链可以完全不同（Theorem 4 第 2 条的证明就是如此：(I) 需要分情形，(II) 也要分情形，但两支的走法不对称）。
误区 2：混淆 $\subset$ 与 $\subsetneq$。
- 错误做法（两种方向都常见）： (a) 把”$A\subset B$”读成”$A$ 真包含于 $B$”，于是认为 $\mathbb{N}\subset\mathbb{N}$ 是错的；(b) 要证 $A\subsetneq B$，却只证了 $A\subset B$ 就收工。
- 为什么错： 本课程（及 Lebl）中 $\subset$ 是允许相等的包含关系；$\subsetneq$ 才是严格形式。两者的证明代价不同：$\subsetneq$ 需要额外的反例元素。
- 正确做法： 证 $A\subsetneq B$ 时明确写两步：(i) 用元素追踪法证 $A\subset B$；(ii) 显式给出一个 $b\in B$ 且 $b\notin A$，由此 $A\neq B$。例如 $\mathbb{N}\subsetneq\mathbb{Z}$ 的反例元素是 $0$；$\mathbb{Z}\subsetneq\mathbb{Q}$ 的是 $1/2$；$\mathbb{Q}\subsetneq\mathbb{R}$ 的需要 $\sqrt2\notin\mathbb{Q}$ 的证明。
误区 3：归纳法里把”弱归纳”与”强归纳”搞混。
- 错误做法： 在 Theorem 6 式的弱归纳（weak induction）证明中直接写”假设 $P(m)$ 对所有 $m\le k$ 成立，证明 $P(k+1)$”，但从不说明为什么可以这样假设。或者反过来：命题的归纳步实际需要 $P(k-2)$（如递推式 $a_{n}=a_{n-1}+a_{n-2}$），却只假设了 $P(k)$，导致证不下去。
- 为什么错： Theorem 6 只给了”$P(m)\Rightarrow P(m+1)$”这一种形式（弱归纳 / 简单归纳）。”$\forall m\le k\,P(m)\Rightarrow P(k+1)$”是强归纳（strong induction），它是另一条（虽然等价的）原理，需要单独证明（或引用）。源文件 Lecture 1 只讲了弱归纳，因此本阶段的一切归纳证明都必须严格符合弱归纳的形式。
- 正确做法： (i) 先判断命题的归纳步到底需要多少前项信息；(ii) 若只需 $P(k)$，就用 Theorem 6 的弱归纳，把归纳假设”$P(k)$”原样写下来；(iii) 若需要多个前项，则要么在课程内另证强归纳（对 $n$ 作弱归纳来证明”$\forall m\le n\,P(m)$”这个新命题），要么到允许强归纳的教材章节再引用。关键纪律：不要在没有证明的情况下调用一个定理尚未给出的更强形式。
误区 4：把良序原理当作可以证明的定理。
- 错误做法： 试图”证明”良序原理，常见套路是：”设 $S\neq\emptyset$，取 $a_1\in S$，再取 $a_2<a_1$，如此下去……最后得到的 $a_k$ 就是最小元。”
- 为什么错： (i) 源文件的 Axiom 5 明确说”Note that this is an axiom, and thus we have to assume this without proof“；(ii) 上面的”证明”本身依赖于”不能无限下降”——而这恰恰就是良序原理的内容，属于循环论证；(iii) “如此下去……最后”这种写法在有限步内没有终止的保证，不是严格的归纳论证。
- 正确做法： 接受良序原理为 $\mathbb{N}$ 的基本假设（另一条等价路线是把 Peano 公理中的归纳原理取作公理，再由此推出良序原理；那是选择公理系统的问题，不是在本课程内证明定理）。在写作中，凡使用良序原理处，明确写出”by the well-ordering property of $\mathbb{N}$”（正如 Theorem 6 的证明所做）。同时注意良序原理只对 $\mathbb{N}$ 成立：对 $\mathbb{Z}$、$\mathbb{Q}$、$\mathbb{R}$ 均不成立，不要跨集合误用。
误区 5：归纳法只写 base case 与 inductive step，却不说明”因此对一切 $n$ 成立”的逻辑。
- 错误做法： 写完 $P(1)$ 与 $P(m)\Rightarrow P(m+1)$ 就停笔，或者含糊地说一句”以此类推，命题得证”。
- 为什么错： $P(1)$ 与 $P(m)\Rightarrow P(m+1)$ 是两个独立的事实；从它们到”$\forall n\in\mathbb{N}\,P(n)$”需要一次真正的推理，这正是 Theorem 6 的内容（借助良序原理的反证）。”以此类推”不是逻辑论证——它没有排除”某个足够大的 $n$ 处失败”的可能。
- 正确做法： 结尾显式写：”由 Theorem 6（数学归纳法），$P(n)$ 对一切 $n\in\mathbb{N}$ 成立。” 并确保 $P(n)$ 的陈述在开头就被精确定义过（例如 Theorem 8 的 $P(n)$ 是那个完整的等式，包含”$\forall c\neq1$”这一前提）。建议格式：开头写 $P(n):\ \cdots$，结尾写 By Theorem 6, $\forall n\in\mathbb{N},\ P(n)$。
误区 6（附加）：在不等式两边同乘一个数时不检查符号。
- 错误做法： 由 $a\ge b$ 直接写 $a(1+c)\ge b(1+c)$，或由 $x<y$ 推出 $x^{2}<y^{2}$。
- 为什么错： 乘以负数会使不等号反向；$x<y$ 也不能推出 $x^{2}<y^{2}$（取 $x=-3,y=1$）。Theorem 9 的归纳步正是靠 $c\ge-1\Rightarrow1+c\ge0$ 才合法。
- 正确做法： 每次乘除都先写一句”因为 $1+c\ge0$（由 $c\ge-1$），不等号方向保持”。同理，证平方不等式时先分 $0\le x<y$、$x<0\le y$、$x<y<0$ 等情形。
误区 7（附加）：把 $A^{c}$ 当作与论域无关的绝对对象。
- 错误做法： 断言”$A^{c}=\{x\mid x\notin A\}$，所以 $(\mathbb{N})^{c}$ 就是所有非自然数”——但没有说明非自然数取自哪个论域。
- 为什么错： 补集依赖论域。同一集合在不同论域下的补集完全不同。
- 正确做法： 要么固定论域（本课程默认 $\mathbb{R}$，当 $A\subset\mathbb{R}$ 时 $A^{c}=\mathbb{R}\setminus A$），要么改写为差集形式 $U\setminus A$ 把论域写出来。Theorem 4 的第 3、4 条特意用 $A\setminus(\cdot)$ 表述，正是回避论域问题的手段。
思考题（带答案）
Q1（概念题）：为什么良序原理不能由归纳法证明，而归纳法可以由良序原理证明？
答案。
先明确两个命题的精确形式：
- 良序原理（Axiom 5）： $\forall S\subseteq\mathbb{N}$，若 $S\neq\emptyset$，则 $\exists x\in S$ 使 $\forall y\in S:\ x\le y$。
- 归纳法（Theorem 6）： 若 $P(1)$ 真且 $\forall m\in\mathbb{N}\,(P(m)\Rightarrow P(m+1))$，则 $\forall n\in\mathbb{N}\,P(n)$。
(1) 为什么归纳法能由良序原理证明？ 因为从良序原理出发可以构造出一个完整的证明（即本讲的 Theorem 6）：定义反例集 $S=\{n\in\mathbb{N}\mid P(n)\ \text{不真}\}$，目标变为 $S=\emptyset$；反设 $S\neq\emptyset$，由良序原理取最小反例 $m$；由 $P(1)$ 真得 $m\neq1$，从而 $m-1\in\mathbb{N}$；由 $m$ 的最小性得 $P(m-1)$ 真；由归纳步得 $P(m)$ 真，于是 $m\notin S$，与 $m\in S$ 矛盾。这是一条逻辑上无缺口的推导，其中良序原理只被用了一次（取最小元），其余步骤都是定义展开与逻辑推理。所以”良序原理 ⟹ 归纳法”是一个定理。
(2) 为什么良序原理不能由归纳法证明？ 这里要区分两个层面。
- 层面一（公理系统层面，本课程的实际立场）： 源文件把良序原理明确标记为 Axiom（公理） 并写道”this is an axiom, and thus we have to assume this without proof“。在一个公理系统中，”证明”只能从公理与已证命题出发；良序原理被选为出发点之一，因此在本系统内它没有证明。这不是”我们还没找到证明”，而是”按定义它不需要证明”。
- 层面二（逻辑等价性层面，更细致的回答）： 若把 $\mathbb{N}$ 换成用 Peano 公理刻画，那么”归纳原理”与”良序原理”是逻辑等价的——也就是说，从归纳原理出发（配合其余 Peano 公理与基本算术）也可以推出良序原理。所以正确的说法不是”良序原理绝对不可能由归纳法证明”，而是：
- 在本课程采用的公理选择下，良序原理是原始假设，归纳法是它的推论；方向是单向的（Task 6 的证明给出了这一方向）。
- 换成另一套等价公理系统后，方向可以反转：把归纳原理取作公理，就能推出良序原理。此时两者关系是”等价“，而”哪一个是公理”是表述体系的选择，不是数学内容的差别。
用”起点不可再退”来直观理解： 假设有人给出一个从归纳法出发证明良序原理的论证，那么把这条论证与 Theorem 6 的证明首尾相接，我们就能在一个什么都不假设的系统里证明良序原理——但”什么都不假设”的系统连 $\mathbb{N}$ 这个对象都不存在（没有公理就没有对象），整个论证无从谈起。任何演绎系统都必须有起点；良序原理在本课程中就是起点之一。
(3) 一句话总结。 归纳法能由良序原理证明，是因为良序原理提供了一个存在性工具（”反例集若非空则有最小反例”），而归纳法的内容恰好可以通过这个工具被反证法拿下。良序原理不能（在本课程内）由归纳法证明，是因为它是被选定的公理；更精确地说，两者在 Peano 算术中是逻辑等价的，方向的选择属于公理系统的表述自由。记住：公理的地位不是”最显然的真理”，而是”演绎的起点”。
Q2（完整归纳法证明）：证明 $\forall n\in\mathbb{N}:\ 2^{n}>n$。
（任务允许在 $\sum_{i=1}^{n}i=\frac{n(n+1)}2$ 与 $2^{n}>n$ 中选一个；这里选 $2^{n}>n$，因为它同时能作为 Q3 的对照。）
答案（完整的 base case + inductive step）。
命题定义。 对每个 $n\in\mathbb{N}$，令
\[P(n):\quad 2^{n}>n .\]目标是证明 $\forall n\in\mathbb{N}\,P(n)$。
（i）基础情形 $n=1$。 $2^{1}=2>1=1$，故 $P(1)$ 为真。依据： 直接计算（$2>1$ 是实数序的基本事实）。✅
（ii）归纳步。 假设 $P(k)$ 为真，即 $2^{k}>k$。(IH)
依据： 归纳假设（此处必须原样抄写，它是下面唯一可用的资源）。
我们要证 $P(k+1)$，即 $2^{k+1}>k+1$。推导如下：
\[\begin{aligned} 2^{k+1} &=2\cdot 2^{k} &&\text{指数法则 }2^{k+1}=2\cdot2^{k}\\ &>2\cdot k &&\text{由 (IH) 两边同乘 }2>0\text{，不等号方向不变}\\ &=2k . \end{aligned}\]于是 $2^{k+1}>2k$。现在把 $2k$ 与 $k+1$ 比较：$2k-(k+1)=k-1\ge0$，依据： $k\in\mathbb{N}\Rightarrow k\ge1$。故 $2k\ge k+1$。串联两个不等式：
\[2^{k+1}>2k\ \ge\ k+1\ \Longrightarrow\ 2^{k+1}>k+1 .\]即 $P(k+1)$ 为真。依据： 指数法则；归纳假设 (IH)；$2>0$ 保证乘正数不反向；$k\ge1$ 保证 $2k\ge k+1$；不等式的传递性。
（iii）结论。 由 Theorem 6（数学归纳法），$P(n)$ 对一切 $n\in\mathbb{N}$ 成立，即
\[\forall n\in\mathbb{N}:\ 2^{n}>n .\qquad\blacksquare\]数值验算（用 python3 验证若干具体值）：
n = 1 → 2^n = 2 > 1 ✓
n = 2 → 2^n = 4 > 2 ✓
n = 3 → 2^n = 8 > 3 ✓
n = 10 → 2^n = 1024 > 10 ✓
n = 20 → 2^n = 1048576 > 20 ✓
答案的要点复述（为什么归纳步必须这样写）。 关键的一步是先乘 2 得到 $2k$，再证明 $2k\ge k+1$。初学者常犯的错误是直接写”$2\cdot2^{k}>2k>k+1$”，却不说明 $2k>k+1$ 的依据（$k\ge1$）。每一步都要有依据，这正是本讲反复训练的纪律。 另外注意：这里的”$k\ge1$”是 $\mathbb{N}=\{1,2,3,\dots\}$ 的直接后果；若采用 $\mathbb{N}=\{0,1,2,\dots\}$，基础情形要改成 $n=0$（$2^{0}=1>0$）且归纳步需要 $k\ge1$ 才成立——即 $k=0$ 时 $2k=0<1=k+1$，所以归纳步必须从 $k\ge1$ 起算。这正是”$\mathbb{N}$ 从 1 开始”这一约定会影响证明书写方式的具体例子。
Q3（用 Theorem 8 或 Theorem 9）：用 Bernoulli 不等式证明 $2^{n}>n$，并用 Theorem 8 计算 $\sum_{k=0}^{n}2^{-k}$ 及其极限。
答案分两部分。
第一部分：用 Theorem 9（Bernoulli 不等式）证明 $2^{n}\ge n+1$（从而 $2^{n}>n$）。
命题定义。 取 $c:=1$。注意 $c=1\ge-1$，故 Theorem 9 的假设满足。Theorem 9 断言对一切 $n\in\mathbb{N}$：
\[(1+c)^{n}\ge1+nc .\]代入 $c=1$：
\[2^{n}=(1+1)^{n}\ge1+n\cdot1=n+1 .\]因此 $2^{n}\ge n+1>n$，即 $2^{n}>n$ 对一切 $n\in\mathbb{N}$ 成立。$\blacksquare$
依据链： $c=1\ge-1$ 满足 Theorem 9 的前提 ⟹ Theorem 9 给出 $2^{n}\ge1+n$ ⟹ $n+1>n$（实数序）⟹ 传递性得 $2^{n}>n$。
更一般地，取任意 $c\ge-1$，Theorem 9 给出 $(1+c)^{n}\ge1+nc$；当 $c>0$ 时这正说明”指数增长快于线性增长”。若取 $c=0$，得到 $1\ge1$（等号）；若取 $c=-1$，得到 $0\ge1-n$，即 $n\ge1$。假设 $c\ge-1$ 是紧的：归纳步中”同乘 $1+c$”要求 $1+c\ge0$，而 $c<-1$ 时该步失效，$c=-1$ 恰好是边界。
与 Q2 的对照（重要）。 Q2 用归纳法直接证明了 $2^{n}>n$；这里用 Theorem 9（它本身由归纳法证明）一步推出了 $2^{n}\ge n+1$。这说明：好的定理能把归纳法的细节打包成可复用的工具。Q2 证明了”这件事是真的”，Theorem 9 则把它变成”随时可调用的引理”。这也是本讲把 Theorem 9 放在”与其他讲次的关联”中反复强调的原因——Lecture 8 需要 $c^{n}$ 无界时，正是这样一步调用它。
第二部分：用 Theorem 8 计算 $\sum_{k=0}^{n}2^{-k}$ 并求当 $n\to\infty$ 时的极限。
令 $c:=\dfrac12$。注意 $c=\frac12\neq1$，Theorem 8 的假设满足：对一切 $n\in\mathbb{N}$，
\[1+c+c^{2}+\cdots+c^{n}=\frac{1-c^{n+1}}{1-c}.\]但我们要计算的是 $\displaystyle\sum_{k=0}^{n}2^{-k}=2^{0}+2^{-1}+\cdots+2^{-n}$，即下标从 $0$ 到 $n$ 共 $n+1$ 项，而 Theorem 8 处理的是从 $0$ 次幂到 $n$ 次幂的 $n+1$ 项和 $1+c+\cdots+c^{n}$——两者一致：取 $c=1/2$，则 $c^{k}=2^{-k}$，故
\[\sum_{k=0}^{n}2^{-k}=1+\frac12+\frac1{2^{2}}+\cdots+\frac1{2^{n}}=\frac{1-\left(\frac12\right)^{n+1}}{1-\frac12}=\frac{1-2^{-(n+1)}}{\frac12}=2\left(1-2^{-(n+1)}\right)=2-\frac{1}{2^{n}} .\]核对最后一步： $2\left(1-2^{-(n+1)}\right)=2-2\cdot2^{-(n+1)}=2-2^{-n}$。✅ 所以
\[\boxed{\ \sum_{k=0}^{n}2^{-k}=2-\frac{1}{2^{n}}\ }\]数值验算（用 python3 精确有理数计算）：
n = 10: Σ_{k=0}^{10} 2^-k = 2047/1024 = 1.9990234375
2 - 1/2^10 = 2047/1024 = 1.9990234375 ✓ 与公式一致
（浮点求和亦为 1.9990234375）
求极限。 我们要求 $\displaystyle\lim_{n\to\infty}\sum_{k=0}^{n}2^{-k}$。由上面的闭式，问题化为求 $\displaystyle\lim_{n\to\infty}\frac{1}{2^{n}}$。这一步的正确依据正是本讲 Theorem 9 的推论（也是 Lecture 8 的 Theorem 94 的结论）：$c=\frac12\in(0,1)$ 时 $\lim_{n\to\infty}c^{n}=0$。在 Lecture 1 阶段，我们只能把它记为”待 Lecture 8 证明的事实”：直观上 $2^{-n}$ 每步减半，越来越小且总为正，故趋于 $0$。（Lecture 8 会用单调有界定理 + 最小上界性质严格证明：$0<2^{-(n+1)}<2^{-n}<1$ 故 $\{2^{-n}\}$ 单调递减有下界，设极限为 $L$，再由 $2^{-(n+1)}=\frac12\cdot2^{-n}$ 取极限得 $L=\frac L2$，故 $L=0$。）
于是
\[\lim_{n\to\infty}\sum_{k=0}^{n}2^{-k}=2-0=2 .\]意义。 这个结果说明无穷级数 $\displaystyle\sum_{k=0}^{\infty}2^{-k}=2$ 是有限的：尽管有无穷多项，但项衰减得足够快，总和恰好是 $2$。注意每一项都为正，部分和从下方单调递增逼近 $2$，永不越过 $2$——这正是”上确界 = 极限”的第一个直觉模型（Lecture 3 的最小上界性质、Lecture 5/8 的单调有界定理都以此为例）。数值上 $n=10$ 时部分和已经是 $1.9990234375$，与 $2$ 的差为 $1/1024\approx0.00098$，这也验证了误差估计 $2-\sum_{k=0}^{n}2^{-k}=2^{-n}$。
数值验算记录（bash 运行 python3）：
| 量 | 值 |
|---|---|
| $\sum_{k=0}^{10}2^{-k}$ | $\dfrac{2047}{1024}=1.9990234375$ |
| $2-\sum_{k=0}^{10}2^{-k}$ | $\dfrac{1}{1024}=0.0009765625$ |
| $2^{n}>n$ 验证 | $n=1,2,3,10,20$ 全部成立（$2^{20}=1048576>20$） |
| Bernoulli $c=1,n=10$ | $2^{10}=1024\ge1+10=11$ ✓ |