证明诊断、依赖关系与唯一性

1. 检查依赖关系，而不只看最后一行

审查一份证明时，可以依次问：

1. 量化的对象是什么，定义域与量词次序是什么？
2. 哪些事实是已知假设，哪些是待证结论？
3. 所构造的每个表达式是否在所述定义域上存在？
4. 每一步推论是否由先前已建立的事实推出？
5. 得到候选对象后，是否将其代回以证明存在性？
6. 声称唯一时，怎样才算同一对象：完全相等、不计次序的因子，还是同一个等价类？

反例否定命题；找到第一个无效推论则诊断证明。二者都重要，但回答不同问题。正确命题也可能有错误证明；发现论证有误，本身并不使结论为假。

例题：奇偶性证明中的循环。 为证明“若 $n^2$ 为偶数，则 $n$ 为偶数”，学生写：“令 $n=2k$，则 $n^2=4k^2$，所以结论成立。”第一行假设了待证结论：尚未证明平方为偶数的任意整数等于某个整数的两倍。该计算实际证明的是反向命题：$n$ 为偶数蕴含其平方为偶数。

正确修复可用逆否命题：若 $n$ 为奇数，则对某整数 $k$ 有 $n=2k+1$，故 $n^2=2(2k^2+2k)+1$ 为奇数。因此平方为偶数时，$n$ 不可能为奇数。这里的表示来自已给假设，而非所需结论。

例题：求候选值不等于构造解。 从 $ax=b$ 形式上相除得到 $x=b/a$，但只有 $a\ne0$ 时才得到候选值；代回后才能证明它是解。为证唯一性，若 $ax=ay=b$，相减得 $a(x-y)=0$，再消去非零的 $a$。若 $a=0$，结论分两种：$b\ne0$ 时无解，$b=0$ 时每个实数都是解。没有说明就除以 $a$ 会漏掉这两种情况。

2. 见证对象的依赖关系是数学内容

在实数范围内，$\forall x\exists y:y>x$ 允许见证对象 $y=x+1$ 依赖 $x$，却不能证明 $\exists y\forall x:y>x$。审查时可画箭头，表示后续选择允许依赖哪些先前选择。存在量词的见证对象可以使用已选输入，不能使用只在其后才量化的变量。

稍不直观的例子。 令 $A=(0,1]$；对每个正整数 $n$，当 $x=1/n$ 时定义 $f_n(x)=n$，其他处为零。每个固定的 $n$ 对应的函数都被 $n$ 所界。每个固定的 $x$ 对应的数列 $f_n(x)$ 随 $n$ 变化也有界：至多一项非零。但不存在对所有 $n$ 和 $x$ 都有效的共同界，因为 $f_n(1/n)=n$。

因此 $\forall n\exists M_n\forall x:|f_n(x)|\le M_n$ 与 $\forall x\exists M_x\forall n:|f_n(x)|\le M_x$ 都成立，而 $\exists M\forall n\forall x:|f_n(x)|\le M$ 不成立。若取上确界时没有证明它有限，就掩盖了缺失的一致界。这个逻辑例子没有假设，也不需要连续性。

3. 归纳法需要每一个递推步骤

考虑错误断言：“每个有限非空实数集合的元素都相等。”一个所谓的归纳证明说：单元素情形成立；对一个 $(n+1)$ 元集合，删除一元素得到 $n$ 个相等元素，再删除另一个得到另外 $n$ 个相等元素，利用两组重叠可使两个公共值相同。

当 $n\ge2$ 时，两个 $n$ 元子集确实重叠；但关键的第一步 $n=1$ 中，一个两元素集合的两个单元素子集没有交集，无法用共同元素连接它们的值。故没有对每个所需的 $n\ge1$ 证明归纳蕴涵。反例 $\{0,1\}$ 证实断言为假，而空交集指出具体失效的步骤。

这不同于强归纳：在归纳步骤中假设所有较小情形成立是合法的，但仍须有效的基础情形及覆盖每个下一指标的证明。递归构造必须下降到已建立的基础情形；只说“更小”而不说明递减的正整数，不能证明终止。

4. 质因数分解的规范化

这里取 $\mathbb N=\{0,1,2,\ldots\}$。

定理

除法算法

设 $a,b\in\mathbb Z$ 且 $b\ne0$。则存在唯一整数 $q,r$ 使得

$$a=bq+r,\qquad 0\le r\lt|b|.$$

$q$ 称为商，$r$ 称为余数。

条件 $0\le r\lt|b|$ 不是附加装饰，而是唯一性的核心。例如

$$17=5\cdot3+2$$

符合除法算法；但

$$17=5\cdot2+7$$

不符合，因为余数 $7$ 不小于 $5$。

先证明存在性。设 $a\ge0$、$b>0$，考虑

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}.$$

因为 $a\in S$，良序原理给出最小成员 $r=a-bq$。若 $r\ge b$， 则 $r-b=a-b(q+1)$ 是更小的非负成员，矛盾。因此 $0\le r\lt b$。 若 $a\lt0$、$b>0$，则 $A=a+(-a)b=(-a)(b-1)$ 非负。 用已证情形写成 $A=bQ+r$，整理得 $a=b(Q+a)+r$，余数范围不变。 若 $b\lt0$，先用正除数 $B=|b|$，再把商 $Q$ 换成 $-Q$。 所有符号情形都不需要负余数。

再证明唯一性。设 $a=bq+r=bq'+r'$，两个余数都在规定范围内。 于是 $b(q-q')=r'-r$，但 $|r'-r|\lt|b|$。$b$ 的非零整数倍 绝对值至少是 $|b|$，故 $r'=r$。再由 $b\ne0$ 得 $q'=q$。 严格上界保证唯一性；仅要求余数非负并不足够。

定理

最大公因数的一步不变性

若 $a=bq+r$，则

$$\gcd(a,b)=\gcd(b,r).$$

证明: 保留整个共同因数集合

目标是证明两个最大公因数相等。先证明更强的中间命题，论证会更直接： 整数 $h$ 同时整除 $a,b$，当且仅当它同时整除 $b,r$。 正向用 $r=a-bq$，反向用 $a=bq+r$，两者都用整数线性组合的整除性质。

输入不同时为零时，两个因数集合相同，所以最大元素相同。若 $a=b=0$， 则 $r=0$，两边按约定都是 $0$。这个恒等式本身不要求余数范围； 余数范围的作用是保证算法向前推进。

概念视角算法

不变量与递减计算

每次替换 $(a,b)\mapsto(b,r)$，最大公因数保持不变，余数则变小。 两者各有作用：不变性保证最后答案就是原本的最大公因数，严格递减则保证 计算会结束。先取输入的绝对值，把较大的正数放在前面；若另一输入是零， 立即停止。其余每次带余除法都使用正除数。

算法必然停止，因为余数形成严格递减的非负整数列：

$$r_1>r_2>r_3>\cdots\ge0.$$

非负整数不可能无限地严格递减。

倒代也可整理成向前更新的系数。对正输入设 $r_0=a$、$r_1=b$， 保存 $r_k=s_ka+t_kb$，初始系数为 $(s_0,t_0)=(1,0)$、 $(s_1,t_1)=(0,1)$。若 $r_{k+2}=r_k-q_{k+1}r_{k+1}$，则

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

代入两个已知线性组合即可证明更新式。系数始终是整数，最后非零余数那一行 便给出最大公因数所需的系数。

定理

Bézout 恒等式

对任意整数 $a,b$，存在整数 $x,y$ 使得

$$\gcd(a,b)=ax+by.$$

对带符号的非零输入，先用 $|a|,|b|$ 计算，再把原本符号吸收到系数中。 若一项为零，用 $|a|=a\operatorname{sgn}(a)$ 或 $b$ 的对应等式； 若两项皆零，取 $x=y=0$。这样便证明恒等式的全部情形。

输入不同时为零时，最大公因数也是最小的正整数线性组合。恒等式保证它 确实是一个组合；其他正组合都是它的正倍数，不可能更小。若输入是 $(0,0)$， 则没有正组合。

定理

Euclid 引理

设 $p$ 是质数。若 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$。

若 $p\nmid a$，则 $\gcd(a,p)=1$，所以存在整数 $m,n$ 使

$$am+pn=1.$$

两边乘以 $b$ 得

$$abm+pbn=b.$$

因为 $p\mid ab$，左边两项都被 $p$ 整除，所以 $p\mid b$。

定理

算术基本定理

每个大于 $1$ 的正整数都可以写成质数乘积，而且这个乘积在不计因子次序下唯一。

存在性仍然来自最小反例法。若存在最小的、大于 $1$ 且不能写成质数乘积的整数，它不可能是质数，因此可分解成两个更小的因数；但这两个较小因数已经可以分解成质数乘积，矛盾。

唯一性使用 Euclid 引理。若

$$p_1p_2\cdots p_r=q_1q_2\cdots q_s,$$

则 $p_1$ 整除右边乘积，所以 $p_1$ 必整除某个质因数 $q_j$，从而 $p_1=q_j$。消去后重复同样论证。

反复使用 Euclid 引理，可以从整除有限乘积推到整除其中一个因子。 消去过程不能只耗尽一边的质数：否则 $1$ 会等于非空质数乘积，而该乘积 大于 $1$。因此两边因子数相同，计入重数后的因子也相同。

对负的非零整数，先提出总因子 $-1$，再分解其正的绝对值。一对应空的质数乘积，零没有这种质因数分解；这些边界情形须明确处理。

5. 最简有理数表示的唯一性

设整数 $a,c$ 和正整数 $b,d$ 满足 $a/b=c/d$ 与 $\gcd(a,b)=\gcd(c,d)=1$，则 $a=c$ 且 $b=d$。

证明。 交叉相乘得 $ad=bc$。由 $\gcd(a,b)=1$，Bézout 恒等式给出整数 $u,v$ 使 $ua+vb=1$。两边乘以 $d$ 得 $d=uad+vbd=ubc+vbd$，说明 $b\mid d$。交换两个分数同理得到 $d\mid b$。两个分母均为正，所以它们相等；交叉乘积等式再给出分子相等。此论证包含分子为零的情形：互素性迫使其正分母为一。

存在性是另一项证明。从任意分母非零的整数分数出发，先把分母变为正，再用正的最大公因数同时除分子和分母。因最大公因数整除两者，所得商仍是整数，值不变，也不再有公因数。完成此构造后，唯一性定理才使“最简分数”有确切含义。

分级证明练习

1. 正向与逆向。 对整数 $n$，证明 $n$ 为奇数当且仅当 $n^2\equiv1\pmod8$。
2. 修复。 在实数范围诊断“若 $ab=ac$，除以 $a$ 得 $b=c$”。陈述并证明正确的定理，分类例外情形。
3. 一致界。 对上述函数 $f_n$，写出存在共同界的否定，并按所需量词次序构造见证。
4. 存在与唯一。 解释为什么质因数唯一性论证本身不能证明每个 $n\ge2$ 都存在质因数分解，并完整给出强归纳的存在性论证。
5. 规范化。 若分母允许为负，最简分数的唯一性哪里失效？陈述并证明适当的修正唯一性描述。
6. 单侧逆。 若 $f\circ g$ 是 $Y$ 上的恒等映射，证明 $f$ 映满 $Y$ 且 $g$ 单射。$f$ 必须单射吗？$g$ 必须映满其另一个已声明集合吗？给出验证过的反例。

完整解答

1. 若 $n=2k+1$，则 $n^2=4k(k+1)+1$。相邻整数 $k,k+1$ 之一为偶数，因此 $8\mid4k(k+1)$ 且 $n^2\equiv1$。反过来，该同余式使 $n^2$ 为奇数。偶整数的平方为偶数，故 $n$ 不能为偶数，只能是奇数。两个方向均已证明。
2. 相除需要 $a\ne0$；在该假设下乘以 $1/a$ 得 $b=c$。若 $a=0$，前提变为 $0=0$，对 $b,c$ 没有限制；例如 $b=0,c=1$ 否定无条件断言。第一个无效步骤是除以未经验证为非零的数。
3. 否定式是 $\forall M>0\exists n\ge1\exists x\in(0,1]:|f_n(x)|>M$。给定 $M$，取整数 $n>M$，再取 $x=1/n$，于是 $|f_n(x)|=n>M$。整数依赖所给的界，点依赖该整数；不需要同一个固定点击败所有界。
4. 唯一性从两个已给分解出发，不能构造出其中任何一个。存在性以 $n=2$ 为基础，它本身是质数。假设从二到 $n-1$ 的每个整数均为质数乘积。若 $n$ 是质数即完成；否则有 $n=ab$，其中 $2\le a,b<n$。归纳假设给出二者的质数分解，合并即得到 $n$ 的分解。每次递归使用更小的正整数，强归纳证明所有情形。
5. 即使分子、分母互素，$a/b=(-a)/(-b)$ 仍给出两种符号选择，例如 $1/2=(-1)/(-2)$。把两个分母规范化为正后，由定理得到唯一的规范对。因此不规定符号时，两对要么相等，要么同时取负。反之，同时取负总保持分数值和互素性，故这正是全部歧义。
6. 对任意 $y\in Y$，有 $y=f(g(y))$，故 $f$ 映满。若 $g(y_1)=g(y_2)$，作用 $f$ 得 $y_1=y_2$，所以 $g$ 单射。其他结论不一定成立：令 $f:\mathbb R\to[0,\infty)$ 为 $f(x)=x^2$，令 $g:[0,\infty)\to\mathbb R$ 为 $g(y)=\sqrt y$。则 $f\circ g$ 是恒等映射，但 $f(1)=f(-1)$，且 $g$ 从不取负值。因此 $f$ 不单射，$g$ 不映满 $\mathbb R$。

总结与术语

循环论证假设了它要证明的结论。依赖关系记录一次选择可以使用哪些先前数据。规范化消除允许的歧义，例如因子次序或分母符号。不计次序的唯一性不同于有序列表唯一性。应定位第一个无效推论，再修复确切缺失的条件或构造；有说服力的最后一行不能取代这些步骤。