Lecture 0: Direct Proofs（直接证明）

目录 · ← l0 · l2 →

Lecture 0: Direct Proofs（直接证明）

概述

本讲是整门 CS70 的起点：在学会任何数学内容之前，先要弄清楚”什么才算真正证明了一个命题”。我们从”为什么实验验证不足以确立数学真理”这个问题出发，先补齐集合与数学记号这套通用语言（集合运算、$\mathbb{N}/\mathbb{Z}/\mathbb{Q}/\mathbb{R}$、$\in/\subseteq$、幂集、笛卡尔积、量词 $\forall/\exists$ 及其否定），再引入第一种证明技巧 —— 直接证明 (Direct Proof)：假设前件、逐步推导、得到后件。本讲用直接证明拿下三条与整除性 (divisibility) 相关的定理，并且通过”数字和被 $9$ 整除 $\iff$ $n$ 被 $9$ 整除”这个完整例子，说明命题与其逆命题是两件事、而证明等价（$\iff$）必须双向各证一次。这一讲确立的语言规范（量词、集合、整除）会一路用到 RSA、编码与可数性。

核心概念的直观解释

数学证明 (Mathematical Proof)

• 定义：一个证明是有限步的逻辑推导 (logical deductions) 序列，它从我们无条件接受的公理 (axioms / postulates) 出发，每一步都由逻辑规则从前面的陈述必然推出，最终得到待证命题。
• 直观解释（”它是什么意思？”）：证明像一段没有分支、没有循环、没有未定义操作的代码。每一行要么是”公理/已知事实”，要么是”由上一行经某条逻辑规则得到”。读完最后一行，你就被强制接受了结论 —— 你没有”相信”的自由，因为每一步都不给歧义留位置。这也解释了为什么证明与计算机有深刻的历史联系：一百年前对”证明”这个概念的探索（形式化、可机械检验）直接催生了计算机的发明。
• 为什么”实验”不够：考虑计算机科学中最典型的待证命题：(1) 程序 $P$ 是否对每一个输入都停机？(2) 程序 $P$ 是否对每一个 $x$ 都输出 $f(x)$？这两个命题都涉及无限多个输入。你测试了 $10^9$ 个 $x$ 都通过，命题依然可能在第 $10^9+1$ 个输入上崩掉 —— 你只证明了”$10^9$ 个特例成立”，而没有证明”全部成立”。证明的价值恰恰在于：用有限的手段，担保无限多个情形。

一层更细的结构：公理 → 定义 → 引理 → 定理

• 公理 (axiom / postulate)：我们不加证明就接受的起点陈述。”总得从某处开始”——数学不能无限地”为什么”下去。
• 定义 (definition)：给新对象或新记号赋予精确含义的约定，例如”$a \mid b$ 当且仅当存在整数 $q$ 使 $b = aq$”。定义不是需要证明的命题，它是在制造词汇。本课程用 $:=$ 表示”定义为”，例如 $q := 6$ 表示把 $q$ 定义成 $6$。
• 引理 (lemma)：为证明某个更大的定理而准备的辅助结果。写长证明时把关键步骤抽成引理，就像把长程序拆成子函数：好读、好复用、好检查。定理 0.2 的证明中，”$10 \equiv 1 \pmod 9$”这类事实就是引理式的零件。
• 定理 (theorem)：希望”对外发布”的主要结论。引理与定理的分界线并不严格，有些引理（如 L05 的欧几里得引理）比它服务的定理更有名。
• 直观解释：把证明想象成一栋楼。公理是地基（不能往下问了），定义是砖块的规格（规定什么叫”整除”、什么叫”子集”），引理是预制构件，定理是交付的成品，而逻辑推导是施工过程 —— 每一道工序都必须用规格允许的材料。
• 一个纪律：当你写下某一步却讲不清它的依据时，那一步就不是证明的一部分，而是一个洞。先回去把它补成”依据：某定义 / 某代数律 / 已证结果”，再往下写。

一个震撼的小例子（本讲反复使用的”证据陷阱”）

考虑命题 $(\forall n \in \mathbb{N})\; n^2 + n + 41 \text{ 是质数}$。手工代几个值：

从 $n=0$ 一直算到 $n=39$，四十个连续值全部是质数。任何人都会开始相信这个命题。但

$1681$ 是合数。所以命题为假。（顺带：$n=41$ 时 $41^2+41+41 = 1763 = 41 \times 43$，也失败。）这说明：再多的一致证据也不能代替证明，而一个反例 (counterexample) 就能推翻全称命题。请把这两个数字记住：$1681 = 41^2$。

集合 (Set) 与集合记号

• 定义：集合是良定义的对象汇集（”well defined” 指：对任意对象，都能明确回答它是否属于该集合）。成员叫元素 (element) 或成员 (member)。若 $x$ 是 $A$ 的元素写 $x \in A$，否则 $x \notin A$。
• 集合相等与外延公理 (axiom of extensionality)：$A = B$ 当且仅当它们元素完全相同。顺序与重复都不算数：

• 描述法：$\mathbb{Q} = \left\{\dfrac{a}{b} \;\middle\vert \; a, b \in \mathbb{Z},\; b \neq 0\right\}$，读作”所有分子为整数、分母为非零整数的分数构成的集合”。
• 具体示例：$A = \{2,3,5,7,11\}$ 是前五个质数；$2 \in A$，$4 \notin A$，$\vert A\vert = 5$。
• 基数 (cardinality)：$\vert A\vert $ 是元素个数。$\vert \varnothing\vert = 0$，其中 $\varnothing$ 是唯一的空集 (empty set)（也写作 $\{\}$）。注意区分：$\varnothing \neq \{\varnothing\}$ —— 前者元素个数为 $0$，后者有一个元素（那个元素恰好是空集）。

• 子集 (subset) 与真子集 (proper subset)：若 $A$ 的每个元素都在 $B$ 中，写 $A \subseteq B$（也写 $B \supseteq A$，$B$ 是 $A$ 的超集）。若 $A \subseteq B$ 且 $A \neq B$（即 $B$ 中至少有一个元素不在 $A$ 中），写 $A \subset B$ 或 $A \subsetneq B$。

  三条基本性质：$\varnothing \subseteq B$ 对任何 $B$ 成立；$\varnothing \subset A$ 对任何非空 $A$ 成立；$A \subseteq A$ 对任何 $A$ 成立。

• 具体示例：取 $B = \{1,2,3,4,5\}$。则 $\{1,2,3\} \subseteq B$ 且 $\{1,2,3\} \subset B$；而 $\{1,2,3,4,5\} \subseteq B$ 但不是 $B$ 的真子集（差别就在”$A \neq B$”这一个条件上）。

集合运算：交、并、差

• 定义：$A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}$；$A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}$（这里的”或”是包含式的：在 $A$、在 $B$、或两边都在，都算）；$B \setminus A = \{x \in B \mid x \notin A\}$（相对补 / 集合差）。若 $A \cap B = \varnothing$ 则称 $A$ 与 $B$ 不相交 (disjoint)。
• 直观解释：$\cap$ 是”两个名单的公共部分”，$\cup$ 是”两个名单的合并去重”（正因为去重，$\vert A \cup B\vert $ 一般不等于 $\vert A\vert +\vert B\vert $），$\setminus$ 是”从 $B$ 的名单里划掉 $A$ 的人”。
• 具体示例：$A = \{1,2,3,4\}$，$B = \{3,4,5\}$，$C = \{1,5,6\}$。则 $A \cap B = \{3,4\}$，$A \cup B = \{1,2,3,4,5\}$，$A \setminus B = \{1,2\}$，$B \setminus A = \{5\}$。取 $A$ 为全体正偶数、$B$ 为全体正奇数：$A \cap B = \varnothing$，$A \cup B = \mathbb{Z}^+$（这是 $\mathbb{Z}$ 的一个划分）。
• 易验算的性质：$A \cup B = B \cup A$，$A \cap B = B \cap A$，$A \cup \varnothing = A$，$A \cap \varnothing = \varnothing$，$A \setminus A = \varnothing$，$A \setminus \varnothing = A$，$\varnothing \setminus A = \varnothing$。

几个”人人都在用”的数集与结构

• 定义：$\mathbb{N} = \{0,1,2,3,\dots\}$（本课程约定 $0$ 是自然数）；$\mathbb{Z} = \{\dots,-2,-1,0,1,2,\dots\}$；$\mathbb{Q} = \{a/b \mid a,b \in \mathbb{Z}, b \neq 0\}$；$\mathbb{R}$ 是全体实数；$\mathbb{C}$ 是全体复数；$\mathbb{Z}^+ = \{1,2,3,\dots\}$ 是正整数。
• 闭包 (closure)：$\mathbb{Z}$ 对加法与乘法封闭（两个整数相加、相乘仍是整数），$\mathbb{N}$ 也对加法与乘法封闭。但两者都对减法不封闭（$0 - 3 = -3 \notin \mathbb{N}$），$\mathbb{Z}$ 对除法也不封闭（$3/2 \notin \mathbb{Z}$）—— 这正是后面引入 $\mathbb{Q}$ 的动机。这个”闭包”事实在本讲的证明里会被明确引用，请留意。
• 幂集 (power set)：$\mathcal{P}(S) = \{T \mid T \subseteq S\}$，即 $S$ 的全部子集构成的集合。若 $\vert S\vert = k$，则 $\vert \mathcal{P}(S)\vert = 2^k$。为什么是 $2^k$？ 构造一个子集时，$S$ 中每个元素都要独立地做一次二元选择：”要它”或”不要它”；$k$ 次独立选择共 $2^k$ 种结果，且不同选择给出不同子集（外延公理），所有子集也都由此产生。这个”每个元素独立二选一”的思路，之后在 L14 计数中会被正式化为乘法法则，在 L15 中变成”样本空间大小 $2^k$”。
• 具体示例：$S = \{1,2,3\}$，$\vert S\vert = 3$，故 $\vert \mathcal{P}(S)\vert = 2^3 = 8$：

注意 $\{1\} \subseteq \{1,2,3\}$（子集关系），而 $\{1\} \in \mathcal{P}(S)$（元素关系）—— 同一个对象在这两个句子里扮演的角色完全不同。

• 笛卡尔积 (Cartesian product)：$A \times B = \{(a,b) \mid a \in A,\; b \in B\}$，元素是有序对。”有序”很重要：$(1,u) \neq (u,1)$，且 $(1,2) \neq (2,1)$。
• 具体示例：$A = \{1,2,3\}$，$B = \{u,v\}$，则

$\mathbb{N} \times \mathbb{N} = \{(0,0),(1,0),(0,1),(1,1),(2,0),\dots\}$ 是全体自然数对；它可以按”对角线”枚举（下面第 5 节会看到，这个枚举技巧在 L12 可数性里是关键工具）。

求和与求积记号 (Sigma and Pi notation)

• 定义：$\sum_{i=m}^{n} f(i) = f(m) + f(m+1) + \cdots + f(n)$；$\prod_{i=m}^{n} f(i) = f(m) \cdot f(m+1) \cdots f(n)$。例如 $\sum_{i=1}^{n} i = 1+2+\cdots+n$，$\prod_{i=1}^{n} i = n!$。
• 具体示例：$\sum_{i=5}^{7} i^2 = 5^2 + 6^2 + 7^2 = 25 + 36 + 49 = 110$。$\prod_{i=1}^{10} i = 10! = 3{,}628{,}800$。
• 为什么要它：本讲定理只处理三位数（$n = 100a+10b+c$），所以可以手写。要把它推广到任意位数的 $n$，就必须用 $\sum$ 把 $n$ 写成 $n = \sum_{i=0}^{k-1} a_i 10^i$ —— 记号是为了让推广成为可能。

量词 (Quantifiers)：$\forall$ 与 $\exists$

• 定义：全称量词 (universal quantifier) $\forall$ 读作”对所有”；存在量词 (existential quantifier) $\exists$ 读作”存在”。写法 $(\forall n \in \mathbb{N})\,P(n)$、$(\exists x \in \mathbb{Z})\,P(x)$。当论域 (universe) 明确时可省略：$\exists x\,(x \text{ lays eggs})$。
• 直观解释：量词是”把无数个单句一次性打包”的装置。$(\forall n \in \mathbb{N})(n^2+n+41 \text{ 是质数})$ 这个句子，等价于同时断言 $0^2+0+41$ 是质数、$1^2+1+41$ 是质数、$2^2+2+41$ 是质数……无穷多句。而 $(\exists x \in \mathbb{Z})(x < 2 \wedge x^2 = 4)$ 只是说：在整数里至少找得到一个满足条件的 $x$（取 $x = -2$ 即可，命题为真）。
• 谓词 (predicate)：像”$n^2 + n + 41$ 是质数”这样带自由变量的句子叫谓词或命题式 (propositional formula)：它本身没有真假，但把变量替换成一个具体值后就变成有真假的命题。$n=1$ 时得”$43$ 是质数”（真）；$n=40$ 时得”$1681$ 是质数”（假）。量词的作用就是把谓词”封口”成命题。
• 有限论域可以消掉量词：若论域 $U = \{1,2,3,4\}$，那么

也就是说：存在 = 一堆”或”，全称 = 一堆”与”。这个对应关系是下一讲德摩根定律能”搬”到量词上的根本原因。但注意：在无限论域（如 $\mathbb{N}$）里这招失效 —— 你无法写下无穷长的合取式。

• 嵌套量词不交换（本讲先埋下伏笔）：比较

第一句说”给定任意整数，总能找到比它更大的整数”——真（取 $y = x+1$）。第二句说”存在一个整数比所有整数都大”——假（不存在最大整数）。两句话只差量词顺序，真假相反。本讲记下这个现象，L01 会给出系统处理它的工具（量词否定律）。

整除性 (Divisibility)、奇偶性与有理/无理数

• 整除的定义：对整数 $a, b$，称 $a$ 整除 $b$（记 $a \mid b$）当且仅当存在整数 $q$ 使得 $b = aq$。例如 $2 \mid 10$，因为取 $q = 5$ 得 $10 = 5 \cdot 2$；$7 \mid (-21)$，因为取 $q = -3$ 得 $-21 = 7 \cdot (-3)$。
• 直观解释：$a \mid b$ 的意思是”用 $a$ 去量 $b$，能量尽、不留余数”。注意 $a \mid b$ 是一个关于”存在性”的命题，不是一次除法运算；证明 $a \mid b$ 的标准动作是把那一个整数 $q$ 显式地造出来（或指出它存在）。
• 几个必须精确的点：
  • 记号方向：$a \mid b$ 是”$a$ 整除 $b$”（$a$ 是除数），不是 $b \mid a$。
  • $a \mid b$ 与分数 $b/a$ 是两回事：$6 \mid 0$ 成立（$0 = 6 \cdot 0$），但 $0/6$ 与 “$6/0$” 都不是这里讨论的对象。
  • 关于 $a = 0$：$0 \mid 0$ 成立（$0 = q \cdot 0$ 对任何 $q$ 都成立，比如 $q = 7$），但 $0 \mid b$ 对 $b \neq 0$ 一律不成立。本讲的定理都取 $a \neq 0$ 的情形，避免这个退化 (degenerate) 情况。
  • 整除不能拆到因子上去（本讲最重要的反例之一）：$6 \mid (2 \cdot 3)$ 显然成立（$2 \cdot 3 = 6$），但 $6 \nmid 2$ 且 $6 \nmid 3$。所以”$a \mid bc$ $\Rightarrow$ $a \mid b$ 或 $a \mid c$”是假命题。可是同样的形式在 $a$ 是质数 时会变成真命题 —— 这就是 L05 里欧几里得引理 (Euclid’s Lemma) 的内容，也是 RSA 正确性的基石。
• 质数 (prime)：自然数 $p \ge 2$ 若只能被 $1$ 和它自身整除，则称 $p$ 是质数。
• 奇偶性：$n$ 是偶数当且仅当 $2 \mid n$，即存在 $k \in \mathbb{Z}$ 使 $n = 2k$；$n$ 是奇数当且仅当存在 $k \in \mathbb{Z}$ 使 $n = 2k+1$。注意”奇数”的定义用的是 $2k+1$ 而非”非偶数”——两者等价，但前者在做代数变形时更好用（L02 证明”若 $n$ 奇数则 $n^3$ 奇数”、证明 $\sqrt{2}$ 无理性时都靠这个形式）。
• 有理数 (rational) 与无理数 (irrational)：能写成两个整数之比 $a/b$（$b \neq 0$）的数叫有理数；否则叫无理数。例如 $2/3,\; 3/5,\; 9/16$ 都是有理数；$\sqrt{3}$、$\sqrt{2}$、$\pi$ 是无理数。特别地：$\mathbb{R} \setminus \mathbb{Q}$ 就是全体无理数构成的集合 —— 这是”集合差”记号最漂亮的一次应用。

直接证明 (Direct Proof)

• 定义 / 一般形式：待证命题形如 $(\forall x)\;P(x) \Rightarrow Q(x)$。直接证明的做法是：对任意（generic，即不假任何特殊性质）的 $x$ 假设 $P(x)$ 成立，然后通过一串保持”必然性”的推导，最终得到 $Q(x)$。

  直接证明 (Direct Proof) 的五步流程
  ================================================================

   目标：证明  P ==> Q

   (1) "Assume P."          <-- 假设前件成立（不是假设结论！）
            |
            v
   (2) 展开定义              <-- 把 P 翻译成"存在某个见证对象"的语句
            |                    例： a|b  -->  存在整数 q1 使 b = q1*a
            v
   (3) 代数/逻辑变形          <-- 等值变形、代入、整理
            |
            v
   (4) 凑出 Q 的定义形状      <-- 关键一步：把结果写成 "Q 所要求的形式"
            |                    例： b+c = (q1+q2)*a  -->  形状 b = (整数)*a
            v
   (5) "Therefore Q."        <-- 结论，并说明 Q 的定义已被满足
   ================================================================

• 直观解释：直接证明像从已知条件出发开一条单行道，一路不许掉头、不许分岔，终点必须是结论。它不需要任何”灵光一现”的假设（这与反证法、逆否证明不同），代价是有时路不好找 —— 本讲的三条定理恰好都是”路很清楚”的情形。
• 两个致命的纪律：
  1. 绝不能把待证结论当前提。后面（L02）会看到那个著名的假证明”$-2 = 2$”：假设 $-2 = 2$，两边平方得 $4 = 4$（为真），于是宣称命题成立。错误在于他证的是 $P \Rightarrow \text{True}$，而这不是 $P$。
  2. “任意”必须是真正的任意。证明里不能假设 $a,b,c$ 取任何特定值（例如”令 $a = 3$”）；正因为没有做这种假设，结论才对所有 $a,b,c \in \mathbb{Z}$ 成立 —— 这一步就是量词 $\forall$ 的落地方式，下面的定理 0.1 会明确点出它。

完整证明与推导（核心）

定理 0.1（整除性的可加性）：对任意 $a, b, c \in \mathbb{Z}$，若 $a \mid b$ 且 $a \mid c$，则 $a \mid (b+c)$。

先把它翻译成量词形式：令 $P(x,y)$ 表示”$x \mid y$”。则定理说的是

证明策略：直接证明。理由：待证命题是 $P \Rightarrow Q$ 形式；而且前件 $P$ 本身就是一个”存在性”断言（存在整数 $q_1, q_2$），一旦把这两个见证对象 (witness) 取出来，剩下的就是把 $b+c$ 整理成”某个整数乘以 $a$”的形状 —— 而这只需要初中的分配律。没有任何理由绕道反证或逆否。

逐步推导：

1. 假设前件：设 $a, b, c \in \mathbb{Z}$ 是任意整数，并假设 $a \mid b$ 且 $a \mid c$。
2. 展开定义（依据：整除的定义）：由 $a \mid b$，存在整数 $q_1$ 使 $b = q_1 a$；由 $a \mid c$，存在整数 $q_2$ 使 $c = q_2 a$。
3. 相加（依据：等式两边可相加）：$b + c = q_1 a + q_2 a$。
4. 提取公因子（依据：分配律）：$q_1 a + q_2 a = (q_1 + q_2)\,a$。
5. 验证见证对象的合法性（依据：$\mathbb{Z}$ 对加法封闭）：$q_1, q_2 \in \mathbb{Z}$，故 $q_1 + q_2 \in \mathbb{Z}$。
6. 收尾（依据：整除的定义，取 $q := q_1 + q_2$）：我们已找到整数 $q$ 使 $b + c = q a$，故 $a \mid (b+c)$。$\blacksquare$

量词在哪里？ 证明的第 1 步只说”$a,b,c$ 是任意整数”，从始至终没有指定任何具体数值。正因为对每个 $a,b,c$ 都成立，我们才得到了 $(\forall a,b,c \in \mathbb{Z})$ 的结论。这就是直接证明”免费”处理全称量词的方式：一次推导，覆盖所有实例。

【证明机制解说】：整条证明的”引擎”只有一句话 —— 两个”$a$ 的倍数”相加仍是”$a$ 的倍数”。第 4 步的分配律是唯一的技术动作，第 5 步的闭包检查是最容易被学生省略、也最容易被扣分的一步（没有它，”$q_1+q_2$ 是整数”就只是感觉，不是证明）。请养成习惯：每造出一个新对象，就检查它是否还在允许的集合里。

把这个机制做一次”微观慢放”：取 $a = 7$ 做具体实例，观察证明的每一步在做什么。

注意上表右侧只是用来理解机制，不能写进证明。证明必须对”任意”的 $a,b,c$ 说话；一旦在证明里写下”取 $a=7$”，你证的就不再是定理，而只是一个例子。

推论 0.1（减法版本，同法可证）：对任意 $a, b, c \in \mathbb{Z}$，若 $a \mid b$ 且 $a \mid c$，则 $a \mid (b - c)$。

证明：完全照抄定理 0.1 的推导，只把第 3 步改为 $b - c = q_1 a - q_2 a = (q_1 - q_2)a$；$\mathbb{Z}$ 对减法同样封闭，故 $q_1 - q_2 \in \mathbb{Z}$，于是 $a \mid (b-c)$。$\blacksquare$

推论 0.2（倍数版本）：对任意 $a, b \in \mathbb{Z}$ 与任意 $k \in \mathbb{Z}$，若 $a \mid b$ 则 $a \mid (kb)$。

证明：设 $b = qa$（$q \in \mathbb{Z}$），则 $kb = k(qa) = (kq)a$，且 $kq \in \mathbb{Z}$，故 $a \mid (kb)$。$\blacksquare$

定理 0.1 的逆命题是假的（反例）：把定理 0.1 的箭头掉头，得到”若 $a \mid (b+c)$，则 $a \mid b$ 且 $a \mid c$”。取 $a = 3,\; b = 1,\; c = 2$：$b + c = 3$，确实 $3 \mid 3$；但 $3 \nmid 1$（$1 = 3q$ 无整数解），也不需要用 $c$ 就能反驳。所以“整除性可以拆回两个加数”是错的。同理，取 $a = 2,\; b = 6,\; c = 7$：$2 \mid 6$，$b+c = 13$ 是奇数，$2 \nmid 13$ —— 这说明定理 0.1 的两个前提缺一不可：只保留 $a \mid b$ 而丢掉 $a \mid c$，结论就失效了。

定理 0.2（数字和法判定 $9$ 的倍数）：设 $0 < n < 1000$ 是整数。若 $n$ 的各位数字之和能被 $9$ 整除，则 $n$ 能被 $9$ 整除。

先把它翻译成量词形式：

证明策略：直接证明 + 按位展开 (positional expansion)。难点在于”数字和”和”$n$ 本身”看起来是两样东西，没有明显联系。破局点是：$n = 100a + 10b + c$ 而数字和是 $a+b+c$，两者只差 $99a + 9b$ —— 而 $99$ 和 $9$ 都是 $9$ 的倍数。所以只要把数字和写成 $9k$，再加 $99a+9b$ 就能”凑出”$n$。这是本讲最值得记住的证据变形技巧。

逐步推导：设 $n$ 的十进制写法为 $n = \overline{abc}$，即

（若 $n \ge 100$ 则 $a \neq 0$；若 $n < 100$ 则可取 $a = 0$，此时把 $n$ 看作”补零的三位数”，数字和仍是 $a+b+c$。约定 $n$ 的三位数字记号只是书写上的方便，不是对结论的限制 —— 见本节末尾的推广讨论。）

1. 假设前件：假设 $n$ 的数字和能被 $9$ 整除，即 $9 \mid (a+b+c)$。
2. 展开定义（依据：整除的定义）：存在 $k \in \mathbb{Z}$ 使

1. 两边同时加上 $99a + 9b$（依据：等式两边加同一个数仍是等式）：

1. 左边合并同类项（依据：交换律、结合律）：

1. 右边提取 $9$（依据：分配律）：

1. 合并 3–5 步：$n = 9(k + 11a + b)$。
2. 验证见证对象（依据：$\mathbb{Z}$ 对加法与乘法封闭）：$k, a, b \in \mathbb{Z}$，故 $k + 11a + b \in \mathbb{Z}$。
3. 收尾：存在整数 $q = k + 11a + b$ 使 $n = 9q$，故 $9 \mid n$。$\blacksquare$

三个可手算的算例：

再看一个数字和不能被 $9$ 整除的对照：$372$ 的数字和是 $3+7+2 = 12$，$12 \bmod 9 = 3$，而 $372 \bmod 9 = 3$ —— 两者余数相同（这正是 $n \equiv a+b+c \pmod 9$ 的雏形）。定理只处理”余数为 $0$”的情形。（$372 \div 9 = 41.\overline{3}$，确实不整除。）

【证明机制解说】：本证明的全部秘密在于选择加什么。我们要用数 $a+b+c$（假设它是 $9$ 的倍数）去控制 $100a+10b+c$，二者相差 $99a+9b$。为什么会想到加 $99a+9b$？因为 $100 - 1 = 99$、$10 - 1 = 9$，而 $9 \mid 99$、$9 \mid 9$ —— $10$ 的幂与 $1$ 同余于模 $9$。所以本证明其实是”$10^i \equiv 1 \pmod 9$”这一事实的三位数特例。这个视角会在 L04 模运算里被正式化，并立刻给出对任意位数都成立的推广：

关于条件 $0 < n < 1000$：这个上界不是为了结论成立（结论对一切正整数都对），而只是为了让证明只需三个字母 $a,b,c$ 就能写完。要处理任意位数，就必须用第 1 节的求和记号并把”逐位相加”的过程形式化 —— 那是 L03 归纳法的任务（对位数做归纳）。

定理 0.3（定理 0.2 的逆定理 / Converse）：设 $0 < n < 1000$ 是整数。若 $n$ 能被 $9$ 整除，则 $n$ 的各位数字之和能被 $9$ 整除。

证明策略：仍是直接证明，而且几乎是定理 0.2 的”倒着走”。注意不要误以为”逆定理自动成立”——本讲最后会给出一个逆定理不成立的例子。这里的逆定理之所以能证，是因为定理 0.2 的推导链每一步都是等值变形（两边加同一个数、合并同类项、提取公因子），因此可以反向阅读。凡是”可逆的推导链”，双向都能证；凡是不可逆的（例如两边平方），就只能证单向。

逐步推导：沿用同样的记号 $n = 100a + 10b + c$。

1. 假设前件：假设 $9 \mid n$。
2. 由定义，存在 $l \in \mathbb{Z}$ 使 $n = 9l$，即 $100a + 10b + c = 9l$。
3. 把 $100a + 10b$ 改写成 $99a + 9b + a + b$（依据：$100a = 99a + a$，$10b = 9b + b$）：

1. 移项：$a + b + c = 9l - 99a - 9b$。
2. 提取 $9$：$a + b + c = 9\,(l - 11a - b)$。
3. 验证见证对象：$l, a, b \in \mathbb{Z}$，故 $k := l - 11a - b \in \mathbb{Z}$。
4. 收尾：存在整数 $k$ 使 $a + b + c = 9k$，故 $9 \mid (a+b+c)$。$\blacksquare$

算例（把定理 0.3 走一遍）：取 $n = 981$。已知 $981 = 9 \times 109$，故 $l = 109$。$a=9, b=8, c=1$。则 $k = l - 11a - b = 109 - 99 - 8 = 2$，于是 $a+b+c = 9 \times 2 = 18$。验算：$9 + 8 + 1 = 18$，且 $18 \div 9 = 2$ ✓。

定理 0.2 与 0.3 合起来 = 等价性：

这条”双向都要证”的纪律是本讲的核心教训：要证 $P \iff Q$，就分别证 $P \Rightarrow Q$ 与 $Q \Rightarrow P$，绝不允许用”同理可证”或”反过来也一样”糊过去 —— 因为”反过来”未必成立。

为什么两条证明的推导链完全对称？ 关键在于它们共享同一个恒等式。把三位数写开：

   恒等式 (两个定理的共同引擎)
   ==============================================================
     n  =  100a + 10b + c
        =  (99a + a) + (9b + b) + c          <-- 拆开百位、十位
        =  99a + 9b + (a + b + c)            <-- 把 "数字和" 单独拎出来
        =  9(11a + b) + (a + b + c)          <-- 99a+9b 已是 9 的倍数
   --------------------------------------------------------------
    于是   n = 9*(11a+b) + S ,   其中 S := a + b + c  是数字和
   --------------------------------------------------------------
    定理 0.2 :  S = 9k   ==>  n = 9*(11a+b) + 9k = 9*(11a+b+k)  ==>  9|n
    定理 0.3 :  n = 9l   ==>  9*(11a+b) + S = 9l  ==>  S = 9*(l-11a-b)  ==>  9|S
   ==============================================================
   同一个恒等式，向右读得到定理 0.2，向左读得到定理 0.3。
   "n 与 S 相差一个 9 的倍数"  ==>  n 和 S 要么同时被 9 整除，要么同时不被 9 整除。

这个图示值得记住：两个方向的证明之所以对称，不是因为运气，而是因为中间的变换是可逆的。凡是”$n$ 与 $S$ 只差 $9$ 的倍数”这种结构的命题，双向都会自动成立。反之，像”$x = y \Rightarrow x^2 = y^2$”（平方不可逆）就只能单向。

命题与逆命题为什么不等价（反例集）

一个命题与其逆命题（converse）一般不是同一件事。下面三个反例都做了验算，请逐个核实：

1. 整除的”不可拆”：$6 \mid (2 \times 3)$ 为真，但 $6 \mid 2$ 为假。这里 $P$ 是”$6 \mid 2$ 且 $6 \mid 3$”，$Q$ 是”$6 \mid 6$”；$P \Rightarrow Q$ 真而 $Q \Rightarrow P$ 假。
2. 定理 0.1 的逆：$3 \mid (1+2)$ 为真，但 $3 \mid 1$ 为假。
3. 数字和法则换模数就崩：对 $9$ 有 $9 \mid n \iff 9 \mid \text{数字和}$。但换 $11$ 就不行：$n = 29$ 的数字和是 $2 + 9 = 11$，$11 \mid 11$ 成立，而 $29 \div 11 = 2.6\overline{36}$，$11 \nmid 29$。（在 $1 \le n < 1000$ 中共有 $164$ 个这样的反例。）这条既说明”逆命题不自动成立”，也说明定理的模数 $9$ 是本质的，不是随便挑的。

定理 0.4（集合相等的标准证法：双向包含）：设 $A, B, C$ 是任意集合，则

证明策略：双向包含 (mutual inclusion)。集合相等没有”代数运算”可以直接算，唯一的武器是外延公理给出的等价刻画：

所以我们把它拆成两个命题：（$\subseteq$ 方向） 每个 $x \in A \cup (B \cap C)$ 都属于 $(A \cup B) \cap (A \cup C)$；（$\supseteq$ 方向） 反过来也成立。这种证明叫元素追踪 (element chasing)：固定一个元素 $x$，把”$x$ 属于某集合”翻译成关于”$x \in A,\; x \in B,\; x \in C$”的布尔条件，然后用逻辑等价变形。

逐步推导：

第一部分：$A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$。 取任意 $x \in A \cup (B \cap C)$。（依据：并集定义）于是有两种情形：

• 情形 1：$x \in A$。则 $x \in A \cup B$（并集定义）且 $x \in A \cup C$（并集定义），故 $x \in (A \cup B) \cap (A \cup C)$（交集定义）。
• 情形 2：$x \in B \cap C$。则 $x \in B$ 且 $x \in C$。由 $x \in B$ 得 $x \in A \cup B$；由 $x \in C$ 得 $x \in A \cup C$；故 $x \in (A \cup B) \cap (A \cup C)$。

两种情形都得到目标结论（依据：$A \cup (B\cap C) = \{x \mid x \in A \vee x \in B\cap C\}$，恰好穷尽所有可能），所以该方向成立。

第二部分：$(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$。 取任意 $x \in (A \cup B) \cap (A \cup C)$。则 $x \in A \cup B$ 且 $x \in A \cup C$。分两种情形：

• 情形 1：$x \in A$。则 $x \in A \cup (B \cap C)$，完成。
• 情形 2：$x \notin A$。由 $x \in A \cup B$ 与 $x \notin A$，必有 $x \in B$；由 $x \in A \cup C$ 与 $x \notin A$，必有 $x \in C$。于是 $x \in B \cap C$，从而 $x \in A \cup (B \cap C)$，完成。

（情形 1、2 覆盖一切可能，故该方向成立。）

由两个方向同时成立，依据外延公理得 $A \cup (B\cap C) = (A\cup B)\cap(A\cup C)$。$\blacksquare$

用有限论域把证明”看穿”：取 $A = \{1,2,3\}$，$B = \{2,3,4\}$，$C = \{3,5\}$，论域 $U = \{1,2,3,4,5,6\}$。逐元素验证：

  A = {1,2,3}   B = {2,3,4}   C = {3,5}        B∩C = {3}

    x | x∈A | x∈B | x∈C || x∈B∩C | x∈A∪(B∩C) || x∈A∪B | x∈A∪C | x∈(A∪B)∩(A∪C)
   ---+------+------+-----++-------+-----------+-------+-------+----------------
    1 |  Y   |  N   |  N  ||   N   |     Y     ||   Y   |   Y   |       Y
    2 |  Y   |  Y   |  N  ||   N   |     Y     ||   Y   |   Y   |       Y
    3 |  Y   |  Y   |  Y  ||   Y   |     Y     ||   Y   |   Y   |       Y
    4 |  N   |  Y   |  N  ||   N   |     N     ||   Y   |   N   |       N
    5 |  N   |  N   |  Y  ||   N   |     N     ||   N   |   Y   |       N
    6 |  N   |  N   |  N  ||   N   |     N     ||   N   |   N   |       N

  结论: 两列的 Y/N 完全一致 ==> 两个集合相等  (验证: 左 = {1,2,3}, 右 = {1,2,3})

注意第 4 行是”信息量最大”的一行：$x = 4$ 时 $x \in A \cup B$ 为真但 $x \notin A \cup C$，所以右式为假 —— 这说明第二个方向不是白证的：$(A\cup B)$ 会引入 $B$ 独有的元素，而把它与 $(A \cup C)$ 相交恰好把这些”只属于 $B$”的元素筛掉。同样第 5 行筛掉”只属于 $C$”的元素。$A \cup (B \cap C)$ 与 $(A\cup B)\cap(A\cup C)$ 之所以相等，本质就是”$B$ 与 $C$ 至少一个成立”（$\vee$）与”$B$ 成立 并且 $C$ 成立”（$\wedge$）在分配律下的关系：本证明其实是逻辑分配律 $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$ 的集合版本。L01 会用真值表证明这条逻辑分配律。

【证明机制解说】：双向包含证明的两个方向常常难度不对称。这里 $\subseteq$ 方向是”分情形 + 直接放大”（把 $B\cap C$ 拆成 $B$ 和 $C$，分别送进两个并集），$\supseteq$ 方向则必须用反设（”假设 $x \notin A$”）才能逼出 $x \in B$ 与 $x \in C$。更常用的判据是：$\supseteq$ 方向若直接推不动，就试着否定 $A$ —— 因为 $x \in A \cup B$ 且 $x \notin A$ 是榨出 $x \in B$ 的唯一出路。这个”反设一个条件”的手法在 L02 的逆否证明里会成为主力。

反例（说明”只证一个方向”会闹笑话）：判断”$A \cup (B \cap C) = (A \cup B) \cap C$ 是否成立？”取 $A = \{1,2,3\}$，$B = \{2,3,4\}$，$C = \{3,5\}$。左边 $= \{1,2,3\} \cup \{3\} = \{1,2,3\}$；右边 $= \{1,2,3,4\} \cap \{3,5\} = \{3\}$。二者不等 —— 左边含 $1,2$，右边不含。但注意 $A \cup (B \cap C) = \{1,2,3\} \supseteq \{3\} = $ 右边，所以一个方向居然是真的。假如你只验证了 $\supseteq$，就会错误地宣布相等。这就是”必须双向”的活证据。

小结：集合等式的三种武器

• 元素追踪（最通用）：双向包含，把 $\in$ 翻译成布尔条件。定理 0.4 用的就是它。
• 套用已知逻辑律：若已知逻辑等价式 $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$，则只要把 $P$ 读作”$x \in A$”等，集合等式就”自动”成立。注意这仍然需要说明”两个方向都能走”，只是逻辑律本身已经双向。
• 把集合相等改写成元素条件的等价：外延公理给出的是 $A = B \iff \forall x\,(x \in A \iff x \in B)$。所以最干净的一句话式证明是：对任意 $x$，

\(x \in A \cup (B\cap C) \iff x \in A \vee x \in (B \cap C) \iff x \in A \vee (x \in B \wedge x \in C)\) \(\iff (x \in A \vee x \in B) \wedge (x \in A \vee x \in C) \iff x \in (A\cup B) \wedge x \in (A \cup C) \iff x \in (A\cup B)\cap(A\cup C).\)

这串 $\iff$ 的每一步都是定义或逻辑分配律，每一步都可逆，所以它同时完成了两个包含方向。考试时写这一串足以得分，但初学者建议先老老实实写双向，把元素追踪的手感练出来。

与经典问题的联系

（1）程序正确性与”无限多输入”的验证问题 → L13 停机问题

本讲开篇的两个命题——”程序 $P$ 对所有输入停机”、”程序 $P$ 对所有 $x$ 都输出 $f(x)$”——是程序验证 (program verification) 的雏形。工程上我们做的是”测试”：跑一批输入，看是否通过。这只能排除反例，不能确立全称命题。CS70 后半程会用对角线方法证明更强、也更冷酷的结论：存在根本无法由任何程序判定的命题（停机问题，L13）。而这一切的出发点就是本讲这句话：全称命题的真伪与”跑过多少测试”无关。

（2）”数字和 $\bmod 9$”是校验和 (checksum) 思想的原型

定理 0.2/0.3 的推广形式 $n \equiv \sum_i a_i \pmod 9$ 说明：一个数的全部信息可以被”压缩”成几位数字的和，而模 $9$ 的值不变。这正是校验位 (check digit) 的原理：在数据末尾附上一个由全体数字算出的冗余位，接收方重算一遍就能发现传输错误。真实系统里用得更多的是”加权”版本，例如国际标准书号 ISBN-10 的校验位用模 $11$ 加权和（权重 $10,9,\dots,1$）计算，并把余数 $10$ 记作字符 X；单一数字写错或相邻两位写反，都可以被检出。注意这里的教学价值不在算法细节，而在于本讲建立的建模路径：定义一个”由诸位数字确定、且对 $n$ 的某个模值不变量”，再证明它与 $n$ 的整除性等价 —— 即”定理 0.2 + 定理 0.3 的双向”。

（3）整除性语言 = RSA 的语法基础 → L04–L06

本讲只用到整除的定义 $b = aq$，但整条数论主线都在这个定义上生长：同余 $a \equiv b \pmod m$ 就是 $m \mid (a-b)$；最大公约数 $\gcd(a,b)$ 是”同时整除 $a,b$ 的最大者”；欧几里得算法靠的是 $\gcd(a,b) = \gcd(b, a \bmod b)$（L05）；费马小定理与 RSA 的解密正确性（L06）本质上是在证明”某个整除关系成立”。本讲的定理 0.1（可加性）与推论 0.2（可乘性）就是之后所有整除运算的合法性依据。

（4）集合与量词语言 = 程序规范与数据库查询

前置条件 (precondition) / 后置条件 (postcondition) 是集合语言：$\{x \in \mathbb{Z} \mid x > 0\}$ 就是”输入必须满足的条件”这个集合。数据库的 SELECT ... WHERE 与 EXISTS 子查询，直接对应 $\exists$ 与 $\forall$ 以及本讲的集合运算：UNION 是 $\cup$，INTERSECT 是 $\cap$，MINUS 是 $\setminus$，NOT EXISTS 对应量词否定律。把 SQL 查询翻译成量词命题、再取否定，是发现”为什么这个查询返回了非预期的行”的最快方法。

（5）集合的”对角枚举” → L12 可数性

$\mathbb{N} \times \mathbb{N}$ 可以按对角线排成一列：$(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),\dots$（先按 $a+b$ 递增，同一个 $a+b$ 内按 $a$ 递增）。这个”在二维网格里排成一条线”的技巧，就是 L12 证明 $\mathbb{N} \times \mathbb{N}$ 可数所用的方法；而”幂集 $\vert \mathcal{P}(S)\vert = 2^k$ 严格大于 $\vert S\vert $”这个有限情形的直觉，会在无限情形被强化为康托定理：没有任何集合与自己的幂集等势。

与其他讲次的关联

• L01（Propositional Logic，命题逻辑）：本讲的定理陈述全部采用”$P \Rightarrow Q$”的形式，而证明就是”用逻辑规则把 $P$ 推到 $Q$”。L01 会给出这套规则本身：真值表、德摩根定律、蕴涵的等价形式 $P \Rightarrow Q \equiv \neg P \vee Q$。特别地，本讲在定理 0.4 里隐式用到的逻辑分配律 $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$ 与德摩根定律，L01 会用真值表逐条证明。
• L02（Proof Techniques II，逆否 / 反证 / 分情形 / 鸽笼）：本讲反复强调的”逆命题 $Q \Rightarrow P$ 与原命题 $P \Rightarrow Q$ 不等价”，是 L02 的入场券。正因为不等价，我们才不能靠”反过来”证定理；但 L02 会给出一个合法替代品 —— 逆否 (contrapositive) $\neg Q \Rightarrow \neg P$，它与原命题等价。更巧的是：定理 0.3 的证明链是可逆的，所以它顺带给出了”$\neg$（数字和可被 $9$ 整除）$\Rightarrow \neg$（$n$ 可被 $9$ 整除）”的逆否证明。此外本讲定理 0.4 的 $\supseteq$ 方向已用到”反设 $x \notin A$”的分情形手法，与 L02 的分情形证明同源。
• L03（Induction，归纳法）：本讲定理 0.2 的条件 $0<n<1000$ 只是记号上的方便（只需三位）。要把它推广到”任意位数 $n = \sum_{i=0}^{k-1} a_i 10^i$”，必须对位数 $k$ 做归纳 —— 这正是 L03 的第一个标准范例（对数的位数或对 $n$ 归纳，逐步剥离末位数字）。同样的模式会在 L03 证明”每个大于 $1$ 的自然数都有质因数”（本讲第 3 节提到的引理）时再次出现。
• L04（Modular Arithmetic，模运算）：本讲的按位展开技巧的”正确语言”是同余。$10 \equiv 1 \pmod 9$ 一句话就蕴含了定理 0.2 与 0.3 两件事，而且对任意位数直接成立。L04 还会把”$a \mid b$ $\iff$ $b \equiv 0 \pmod a$”确立为标准转写，让整除命题变成同余命题。
• L05–L06（Euclid/FLT/CRT → RSA）：本讲的反例”$6 \mid (2\cdot3)$ 但 $6 \nmid 2$ 且 $6 \nmid 3$”是理解欧几里得引理的靶子：当 $a$ 换成质数 $p$ 时，”$p \mid bc \Rightarrow p \mid b$ 或 $p \mid c$”才成立。RSA 的正确性证明（$m^{ed} \equiv m$）就依赖这类”从整除因子中把 $p$ 逼出来”的推理。
• L12（Countability，可数性）：本讲”有限集 $\vert S\vert = k \Rightarrow \vert \mathcal{P}(S)\vert = 2^k$”这条计数事实，在无限情形会升格为对”等势 (equinumerous)”的讨论；而 $\mathbb{N} \times \mathbb{N}$ 的对角枚举则是 $\mathbb{Q}$ 可数、$\mathbb{R}$ 不可数（对角线论证）的技术前奏。
• L14–L15（Counting → Probability Foundations）：”构造子集 = 对每个元素做一次独立二选一”这一条，是 L14 乘法法则的原型；而 L15 把随机试验的样本空间定义为一个集合 $\Omega$、事件定义为 $\Omega$ 的子集 $\mathcal{F}$，本讲的 $\cup / \cap / \setminus$ 就直接变成了”或事件 / 与事件 / 补事件”。

关键要点

1. 证明的定义：证明是从公理出发的有限步逻辑推导，每一步都必须有依据（定义、代数运算、已知结果、闭包）。它的全部价值在于用有限手段担保无限多个情形；测试与举例只是证据 (evidence)，永远不是证明。记住反例数字 $1681 = 41^2$：$n^2+n+41$ 在前 $40$ 个自然数上全是质数，仍不是恒质数。
2. 直接证明的模板：Assume P → 展开定义 → 代数变形 → 凑出 $Q$ 的形状 → 检查见证对象仍属合法集合（闭包）→ Therefore Q。永远不要假设你想证的东西，也永远不要偷偷假设具体数值——正是”任意”才换来 $\forall$。
3. 整除证明的两把钥匙：把 $a \mid b$ 翻译成 $b = qa$（”存在一个 $q$”，造出来就算证完）；把 $a \mid (b \pm c)$ 和 $a \mid kb$ 当作标准零件使用（定理 0.1 与推论 0.1、0.2）。整除不能拆到因子：$6 \mid 6$ 不代表 $6 \mid 2$ 或 $6 \mid 3$（换成质数才成立）。
4. 等价命题（$\iff$）必须双向证：定理 0.2（数字和 $\Rightarrow$ $9 \mid n$）与定理 0.3（$9 \mid n$ $\Rightarrow$ 数字和）合起来才给出”$9 \mid n \iff$ 数字和可被 $9$ 整除”。原命题与逆命题不等价：$6 \mid (2\cdot3)$、$3 \mid (1+2)$、$29$ 的数字和可被 $11$ 整除却 $11 \nmid 29$，三个反例都说明这一点。
5. 集合相等 = 双向包含：$A = B \iff (A \subseteq B \wedge B \subseteq A)$。证法是元素追踪：固定任意 $x$，把 $x \in \cdot$ 翻译成布尔条件，再分情形（或反设某个否定条件）推进。只证一个方向是错的（本讲的 $A \cup (B\cap C) \supseteq (A\cup B)\cap C$ 就是”单向真、整体假”的陷阱）。量词方面：$\exists$ 是广义的 $\vee$，$\forall$ 是广义的 $\wedge$，且嵌套量词不可交换。

常见误区与注意事项

1. 把”验证了很多例子”当成证明。 $n^2+n+41$ 在 $n = 0,\dots,39$ 上全部为质数，却在 $n=40$ 崩掉（$1681 = 41^2$）。凡是”$\forall$”开头的命题，举例只能推翻它（一个反例），永远不能确立它。
2. 把逆命题当原命题用。 读到”$a \mid b \Rightarrow a \mid b+c$”就自动使用”$a \mid b+c \Rightarrow a \mid b$”。$3 \mid (1+2)$ 但 $3 \nmid 1$。箭头方向是有信息的，不能想当然掉头。
3. 只证一个包含方向就宣布集合相等。 $A \cup (B \cap C) \subseteq (A \cup B) \cap C$ 在 $A=\{1,2,3\},B=\{2,3,4\},C=\{3,5\}$ 上成立，但两边并不相等（左边有 $1,2$，右边没有）。两个方向都要写，且要写清”由外延公理”收尾。
4. 混淆 $\in$ 与 $\subseteq$。 $\{1\} \subseteq \{1,2,3\}$（左边是子集），但 $\{1\} \in \mathcal{P}(\{1,2,3\})$（左边是元素）。同样地 $\varnothing \neq \{\varnothing\}$：前者 $\vert \varnothing\vert = 0$，后者 $\vert \{\varnothing\}\vert = 1$，且 $\varnothing \in \{\varnothing\}$ 而 $\varnothing \subsetneq \{\varnothing\}$。
5. 忘了检查”见证对象”是否在允许的集合里。 定理 0.1 的第 5 步”$q_1, q_2 \in \mathbb{Z} \Rightarrow q_1+q_2 \in \mathbb{Z}$”、定理 0.2 第 7 步”$k+11a+b \in \mathbb{Z}$”、定理 0.3 第 6 步”$l - 11a - b \in \mathbb{Z}$”——这些看似显然的句子必须写出来，因为”封闭性”是结论成立的必要条件。（$\mathbb{N}$ 对减法不封闭就是一个立刻失效的例子：$0 - 3 \notin \mathbb{N}$。）
6. 否定量词时不翻转、或把蕴涵的否定写错。 $\neg(\forall x\,P(x))$ 是 $\exists x\,\neg P(x)$（不是 $\forall x\,\neg P(x)$）；更常见的错误是把 $\neg(\forall x)(P(x) \Rightarrow Q(x))$ 写成 $(\forall x)(P(x) \Rightarrow \neg Q(x))$，正确形式是 $(\exists x)(P(x) \wedge \neg Q(x))$（”有一个反例 $x$：前提成立而结论不成立”）。L01 第 3 节会专门训练这一点。
7. 用”显然”“易得”跳过关键推导。 特别地，不要在证明中无意引用尚未证明的东西（例如用”$a \mid b \Rightarrow a \mid kb$”却不展开定义），也不要像 L02 那个假证明一样除以零（$x = y \Rightarrow x - y = 0$）或对不等式两边平方（$-2 \le 1$ 但 $4 \not\le 1$）。

思考题（带答案）

Q1.（计算） (a) 取 $n = 837$，用定理 0.2 的按位展开式 $n = 9(k + 11a + b)$ 验证 $9 \mid 837$，写出 $k$ 与最终商 $q$。(b) 取 $n = 372$，说明为什么定理 0.2 不能用来断言 $9 \mid 372$，并给出 $372 \bmod 9$。(c) 判断真假并说明：”若 $11 \mid n$ 的数字和，则 $11 \mid n$（$0<n<1000$）”。

Q2.（证明） (a) 用直接证明证明：对任意 $a, b \in \mathbb{Z}$ 与任意 $k \in \mathbb{Z}$，若 $a \mid b$ 则 $a \mid (kb)$。(b) 证明：对任意 $a, b \in \mathbb{Z}$，若 $a \mid b$ 且 $b \mid a$ 且 $a, b > 0$，则 $a = b$。(c) 在 (b) 中去掉条件 $a, b > 0$，命题还成立吗？

Q3.（集合与反例） (a) 用双向包含证明 $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$。(b) 取 $A=\{1,2,3,4\}, B=\{2,3,4\}, C=\{3,4,5\}$ 逐元素验证。(c) 定理 0.1 的逆命题是否成立？给出反例。