3.3 反证法、存在性与唯一性

第 3.2 节通过直接前进、分情况或证明逆否命题来建立蕴含。另一条路线是：假设希望得到的结论为假，观察这个假设会造成什么。如果它必然导致不可能情况，那么假设只能是错误的。

本节还要区分两个经常被过快合并的说法：

• “至少有一个”是存在性命题；

• “恰好有一个”同时要求存在性与唯一性。

矛盾是一组不可能同时满足的要求

矛盾（contradiction）是在任何赋值下都不可能为真的语句。第 2 章给出的逻辑形式是

在普通数学中，矛盾可能表现为

每一组都同时要求两个不相容条件。

用反证法（proof by contradiction）证明命题 $P$ 时，按照下面的结构：

1. 假设否定命题 $\neg P$ 成立；

2. 把假设与定义、已知事实组合；

3. 推导出矛盾；

4. 得出 $\neg P$ 不可能成立，因此 $P$ 为真。

矛盾必须来自临时假设与有效事实。只写“这产生矛盾”，却不展示哪两个结果不相容，并没有完成证明。

完整例子：不存在既偶又奇的整数

定理。 不存在同时为偶数和奇数的整数。

反设存在某个整数 $n$，它既是偶数又是奇数。

因为 $n$ 是偶数，存在整数 $a$ 使

因为 $n$ 是奇数，存在整数 $b$ 使

两个表达式都等于 $n$，所以

移项得到

因为 $a-b$ 为整数，左侧是偶数；右侧 $1$ 是奇数。一个整数不可能同时为偶数和奇数，所以等式不可能成立。临时假设导致矛盾，因此不存在既偶又奇的整数。

这个证明提到奇偶，看起来可能像循环论证，但它并不是。定义把假设转成了具体的不可能等式：“某个偶数等于 $1$。”

找出真正冲突，而不是堆积假设

反证法应只使用相关假设。加入不必要条件会掩盖真正的不可能原因。

假设同时装入：

• $n$ 是偶数；

• $n$ 是奇数；

• $n>0$；

• $3\mid n$。

前两个条件已经冲突，正数条件和被 $3$ 整除都没有参与推理。删除无关假设会得到更短、更清楚的证明，并暴露真正的冲突核心。

把假设装入压力舱，直到没有整数候选值存活，再逐项删除假设。最有信息量的结果不是条件最多的组合，而是仍能造成不可能的最小活动集合。

存在性要求至少一个见证

存在性命题具有形式

要作构造性证明，需要给出具体见证 $a\in D$，并验证 $P(a)$。

例子。 存在整数 $x$，使

取 $x=3$。它属于整数论域，并且

因此整数解存在。

这里有两项检查：

1. 见证属于声明的论域；

2. 见证满足谓词。

如果论域改成正偶数，即使 $x=3$ 满足等式，它也不是有效见证。

有些存在性证明是非构造性证明（nonconstructive proof）：它说明对象必然存在，却不明确给出对象。反证法有时可以做到这一点。在当前阶段，构造性见证更容易检查，所以只要能够构造，就优先给出见证。

唯一性排除第二个不同见证

存在性证明不会自动带来唯一性。方程

有见证 $x=2$，同时也有解 $x=-2$。给出一个解只能证明存在。

“恰好存在一个 $x$ 使 $P(x)$”记作

符号 $\exists!$ 表示“唯一存在”。完整证明分两部分：

• 存在性：构造或说明至少有一个解；

• 唯一性：假设 $x$、$y$ 都是解，再证明 $x=y$。

存在且唯一的完整证明

定理。 存在唯一实数 $x$ 满足 $3x+2=11$。

存在性。 见证 $x=3$ 满足 $3(3)+2=11$。

唯一性。 假设实数 $x$、$y$ 都满足方程，则

因此

两边同时减 $2$，再除以 $3$，得到

任意两个解都相等，所以不可能存在两个不同解。结合存在性可知，解唯一。

唯一性论证不必重新算出 $3$。它证明所有可能解都会收缩成同一个值。

解锁匠会区分三种状态：没有见证、恰好一个见证、存在多个见证。尝试在 $ax+b=c$ 中令 $a=0$：若 $b\ne c$，没有任何 $x$ 可行；若 $b=c$，每个整数都可行。这个边界说明存在性与唯一性必须使用两个独立检查器。

先判断命题类型，再选择证明任务

定理措辞决定证明责任：

常见错误是证明“至多一个”，却宣布“恰好一个”。空解集也满足“至多一个”，所以只有唯一性、没有存在性是不够的。

通向下一节

到目前为止，这些方法都通过任意对象证明一般性结论。按正整数编号的命题经常具有重复依赖：一个情形成立后，可以支撑下一个情形。第 3.4 节会把这种依赖发展成数学归纳法，再通过强归纳法允许新情形使用全部更早情形。