01 / 导读
导读
引用
Hammack, R. (2018). Book of Proof (3rd ed.). Richard Hammack. Free official edition: https://richardhammack.github.io/BookOfProof/
章节概要
第1章：集合
本书以"全部数学都可以用集合来描述"为出发点，因此第一章先建立此后各章都要用到的语汇：集合构造记号、笛卡儿积、子集、幂集、并集、交集、差集与补集、韦恩图以及带指标的集合族。本章最后把常见的数系看作集合，并简要介绍罗素悖论，说明为什么在"什么算作集合"的问题上需要谨慎。
第2章：逻辑
本章讲解把证明串联起来的逻辑。它定义命题、"且""或""非"等联结词、条件命题和双条件命题，并用真值表确立德摩根律、条件命题与其逆否命题等价之类的逻辑等价关系。随后讨论量词、英语与符号逻辑之间的互译、量化命题的否定以及推理规则；结尾一节说明学习逻辑的理由：它确定了"如果……那么"和"对所有"等措辞的确切含义。
第3章：计数
本章在第三版中有所扩充，讨论如何不逐一清点而回答"有多少"。内容依次为列表、乘法原理、加法原理和减法原理、阶乘与排列、作为子集计数的二项式系数、帕斯卡三角形与二项式定理、容斥原理、多重集计数、除法原理与鸽巢原理，最后介绍组合证明——通过说明两个表达式计数的是同一对象来证明它们相等。引言把本章列为可选，但它为后面的例题和习题提供了素材。
第4章：直接证明
第二部分从"定理""证明""定义"的含义讲起，并给出后续各章所依赖的精确定义（偶数与奇数、整除、素数、最大公约数等）。对于形如"如果 P，那么 Q"的命题，直接证明被表述为一个提纲：假设 P，推理得到 Q，并以整数性质为例反复练习。本章还说明如何按情形分类证明，以及如何对类似情形只论证一次。
第5章：逆否证明
本章以第2章建立的逻辑等价为基础，通过证明"如果非 Q，那么非 P"来证明"如果 P，那么 Q"，并举出比直接证明简单得多的例子。它引入模 n 同余作为新命题的来源。随后一节讨论数学写作，列出若干实用规则，例如句子不以符号开头、独立展示的公式也要加标点、用文字把符号隔开等。
第6章：反证法
第三种主要技巧是假设命题为假，再推出荒谬的结论。本章从逻辑上说明这一方法的合理性，并用它证明经典结果，包括 √2 是无理数和素数有无穷多个，然后把它推广到条件命题，并与其他技巧结合使用。结尾的建议是先尝试直接证明或逆否证明，因为反证法证明中常常隐藏着更简单的逆否证明。
第7章：非条件命题的证明
第三部分把工具箱扩展到不具有"如果 P，那么 Q"形式的命题："当且仅当"命题、一组相互等价的命题、存在性证明以及存在且唯一性证明。本章还对比了构造性证明（给出对象本身）与非构造性证明（不指明对象而证明其必然存在）。
第8章：涉及集合的证明
本章把前面的技巧用于集合论的三项基本任务：证明某个元素属于某个集合、证明一个集合是另一个集合的子集、证明两个集合相等（双向包含）。一个关于完全数的长例子沿着归于欧几里得和欧拉的推理，说明集合相等的论证可以承载实质性的数论内容，并涉及梅森素数。
第9章：反驳
本章先把命题分为已知为真、已知为假和尚未解决三类，然后说明如何证明一个命题为假。主要工具是反例；本章还讨论如何反驳存在性命题（证明其全称否定）以及用反证法进行反驳。
第10章：数学归纳法
本章以"前 n 个奇数之和等于 n²"这一猜想为引子，介绍普通归纳法、强归纳法和最小反例证明法，并用这些方法证明算术基本定理（素因数分解的存在性与唯一性），以及关于斐波那契数的恒等式。
第11章：关系
第四部分从关系的一般理论开始，关系被定义为有序对的集合。本章研究自反性、对称性和传递性，等价关系，以及等价类与划分之间的对应。它以构造模 n 整数为示例，最后讨论两个不同集合之间的关系，为函数的定义做准备。
第12章：函数
函数被定义为特殊的关系，从而得到一种超越公式的一般观点。本章讨论单射、满射与双射，用函数的语言重述鸽巢原理，并讲解复合、反函数以及集合的像与原像。
第13章：微积分中的证明
本章为第三版新增，并明确标为可选，介绍分析学中使用的证明风格。它从三角不等式和极限的 ε–δ 定义出发，证明某些极限不存在，推导极限运算法则，进而讨论连续性与导数、无穷远处的极限以及数列与级数的收敛。本章假定读者学过微积分。
第14章：集合的基数
最后一章通过双射定义"基数相等"，并说明无穷集合也有大小之分：整数集和有理数集是可数无穷的，而实数集不是。本章证明任何集合都小于其幂集，给出判断可数性的准则，并证明康托尔–伯恩斯坦–施罗德定理，用它说明实数集与自然数集的幂集基数相同；结尾提到连续统假设。
核心概念
第1章：集合
- 集合构造记号：通过元素满足的条件来描述集合，例如 {x ∈ ℤ : x 是偶数}。
- 幂集：给定集合的全部子集组成的集合；含 n 个元素的集合有 2ⁿ 个子集。
- 罗素悖论：由"所有不属于自身的集合组成的集合"引出的矛盾，说明并非每一种描述都能定义一个集合。
第2章：逻辑
- 条件命题：P ⇒ Q 仅在 P 真而 Q 假时为假。
- 逻辑等价：真值表相同的两个命题，例如条件命题与其逆否命题。
- 量词的否定："对所有 x，P(x)"的否定是"存在 x 使 P(x) 不成立"，反之亦然。
第3章：计数
- 乘法原理：若列表分阶段构造且每一阶段的选择数固定，则列表总数等于各阶段选择数之积。
- 二项式系数：n 元集合中 k 元子集的个数，也给出二项式定理中的系数。
- 组合证明：通过说明等式两边计数的是同一组对象来证明恒等式。
第4章：直接证明
- 作为工具的定义：精确的含义规定（例如若 n = 2a 对某个整数 a 成立，则 n 为偶数），证明就是逐步展开这些定义。
- 直接证明：假设 P，利用定义和已知事实推出 Q。
- 分情形证明：把假设分成穷尽的若干情形，在每一种情形下证明结论。
第5章：逆否证明
- 逆否命题："非 Q 蕴涵非 P"，与"P 蕴涵 Q"逻辑等价。
- 模 n 同余：当 n 整除 a − b 时记 a ≡ b (mod n)。
第6章：反证法
- 反证法：假设命题的否定成立，推出形如"C 且非 C"的结论。
- 隐藏的逆否证明：许多反证法证明都可以改写成更简单的逆否证明。
第7章：非条件命题的证明
- "当且仅当"证明：同时证明 P ⇒ Q 及其逆命题 Q ⇒ P。
- 构造性证明与非构造性证明：给出具体对象，或在不指明对象的情况下证明其必然存在。
第8章：涉及集合的证明
- 子集证明：任取 A 中一个元素，证明它属于 B。
- 双向包含证明集合相等：分别证明 A ⊆ B 和 B ⊆ A。
- 完全数：等于其小于自身的全部正因数之和的自然数，例如 6 和 28。
第9章：反驳
- 反例：说明全称命题为假的单个实例。
- 反驳存在性命题：通过证明其全称否定来说明"存在……"的命题为假。
第10章：数学归纳法
- 归纳法：证明基础情形，并证明每一情形蕴涵下一情形，从而命题对所有自然数成立。
- 强归纳法：在归纳步骤中使用此前所有情形，而不仅仅是前一个情形。
- 最小反例：假设存在最小的不成立情形，并由此推出矛盾。
第11章：关系
- 等价关系：同时具有自反性、对称性和传递性的关系。
- 划分：把集合分成互不相交的非空部分；等价关系的等价类构成一个划分。
- 模 n 整数：整数在模 n 同余下的等价类所组成的集合。
第12章：函数
- 单射与满射：不同输入对应不同输出的函数是单射；陪域中每个元素都是某个输出的函数是满射。
- 反函数：当且仅当函数是双射时存在。
- 像与原像：定义域某个子集的全部输出，以及落入陪域某个子集的全部输入。
第13章：微积分中的证明
- ε–δ 极限：若对每个 ε > 0 都存在 δ > 0，使得当 0 < |x − c| < δ 时 |f(x) − L| < ε，则称 x → c 时 f(x) → L。
- 三角不等式：|a + b| ≤ |a| + |b|，是极限证明中的基本估计。
第14章：集合的基数
- 基数相等：两个集合之间若存在双射，则它们大小相同。
- 可数集与不可数集：与 ℕ 等大（或有限）的集合，以及像 ℝ 这样更大的无穷集合。
- 康托尔–伯恩斯坦–施罗德定理：两个集合之间若有双向的单射，则必存在双射。
评析
优点
- 按技巧编排。 第二、三部分把直接证明、逆否证明、反证法、"当且仅当"、存在性、反驳和归纳法逐一分开，每种方法先给出证明提纲再举例。初学者很容易判断自己要证明的是哪一类命题、应当尝试哪种模板。
- 既重逻辑也重写作。 5.3 节关于数学写作的规则，以及 6.4 节"优先选择更简单方法"的建议，都把证明当作写给别人读的文本。配合细致的范例证明，这有助于学生写出不仅正确而且易读的论证。
- 结构灵活、说明清楚。 引言给出依赖关系图，表明第3、10、13章可以省略，还给出标明可选小节的十四周教学进度表。教师可以把课程引向离散数学（第1–12章），也可以引向分析学预备（除第3章外全部）。
- 习题丰富并附部分答案。 每节或每章末都有习题，书末给出奇数题答案，既便于自学，也把偶数题留作考核之用。
局限
- 逻辑部分较为非形式化。 第2章讲授的真值表、量词和推理规则足以支撑写证明，但没有形式证明系统、一阶语言的语义或公理化集合论；对逻辑本身感兴趣的读者需要另找教材。
- 例子偏重整数。 在第13章之前，大多数例子都围绕奇偶性、整除和同余。这降低了先修要求，但将要学习线性代数或分析的学生在这些领域里见到的证明相对较少。
- 微积分一章要求更高。 第13章假定读者学过微积分，并较快地讲完极限、连续性、数列与级数；它是分析式证明的入门，而不能替代分析课程。
- 许可限制。 免费 PDF 采用非商业、禁止演绎的知识共享许可，教师不能改编或重组正文。
在课程中的定位
在这份"数理逻辑与集合论"书单中，Book of Proof 是通向以证明为中心的数学的过渡教材，与 Daniel Velleman 所著 How to Prove It（一般被视为系统介绍证明策略的入门书）地位相当；两者都可以作为第一本教材互相替代，也可以把其中一本当作另一本的补充习题来源。Peter Eccles 的 An Introduction to Mathematical Reasoning、Allenby 的 Numbers and Proofs 和 Liebeck 的 A Concise Introduction to Pure Mathematics 一般被描述为通过数、集合与函数进入纯粹数学的导论；在熟练掌握 Hammack 第一至第三部分的技巧之后，它们是自然的后续读物或配套读物。
就课程的逻辑部分而言，Hammack 是预备而非替代。Leary 与 Kristiansen 的 A Friendly Introduction to Mathematical Logic 和 Enderton 的 A Mathematical Introduction to Logic 研究形式语言、演绎和完备性，恰恰需要本书所培养的对量词、归纳法和集合记号的熟练运用。学生应先读 Hammack，再转向其中一本逻辑教材。
如何使用本书
本书面向从计算型数学转向证明型数学的学生——通常是第一门"证明导论"或过渡课程的学习者。几乎全部内容只需要中学代数；第13章需要学过微积分，其他章节中个别用到微积分或线性代数的例题和习题可以跳过。
一个可行的阅读计划是参照作者自己的进度表：较快但认真地读完第1、2章（逻辑处处用到），把第4–6章作为核心，接着读第7–10章，最后读第11、12、14章。第3章可选，但它提供了后面习题会用到的例子；第13章适合在第一门分析课之前阅读。自学者应在阅读每个范例证明之前先自己尝试，遵循每种技巧给出的提纲，按照 5.3 节的规则用完整的句子写出每节若干道习题，并对照书末答案检查奇数题。作者网站还提供免费 PDF 和印刷版信息。
版本与来源
本导读依据 Book of Proof 第三版（Edition 3.4，© 2018 Richard Hammack，CC BY-NC-ND 4.0），阅读的是作者官方网站 https://richardhammack.github.io/BookOfProof/ 提供的免费 PDF。导读参考了第三版序言、引言（各部分结构、依赖关系图和教学进度表）、完整目录，以及全部十四章的开篇、所有小节标题和主要范例证明（包括 5.3、6.4、8.4、10.3–10.4、12.3、13.2 和 14.1–14.4 节），并参考了结语和答案部分的编排。