1.4 证明方法四式：直接、反证、构造、存在性

1.4 证明方法四式：直接、反证、构造、存在性

本节摘要：直接证明从前提一路推到结论；反证法假设结论不真再导出矛盾；构造证明直接造出满足要求的对象；存在性证明（含抽屉原理式的非构造证明）只保证对象存在而不给出实例。本节把四种模式放在对比框架下，各配一个完整案例——从命题、证明、代码复算到变式——并给出"什么命题配什么证法"的选择经验。

同一个目标，四条登山道

四年前我带一个学生准备数学竞赛，他最大的困惑不是"想不到结论"，而是"证明写了一半发现自己在绕圈"。复盘下来，问题几乎总是证法与命题形态错配：明明是"不存在"型命题，却硬走直接证明，越证越虚。证明方法的选择其实有规律可循，先上对比表：

案例一：反证法的教科书样本——根号二是无理数

命题：不存在两个正整数 p、q 使得 p 除以 q 的平方等于 2。反证路线：假设存在且约到最简，则 p 的平方是偶数，故 p 是偶数，写 p 等于 2k；代回得 q 的平方也是偶数，故 q 也是偶数——与最简分数矛盾。证明只有五行，但每一行都值得细看：矛盾必须打在假设内部（最简性被推翻），而不是打在常识上。用连分数还能看到这个数的"无理结构"：

from fractions import Fraction

# 数值侧证：用更高精度逼近，误差单调缩小但永不为零
best = None
for q in range(1, 2000):
    p = round((2 * q * q) ** 0.5)
    err = abs(p * p - 2 * q * q)
    if best is None or err < best[0]:
        best = (err, Fraction(p, q))
print(best)   # 最优逼近误差降到 1，但精确等式 p*p = 2*q*q 永远差着这个台阶
# 佩尔方程视角：p*p - 2*q*q = ±1 的解有无穷组，恰好刻画了这些最佳逼近
​

变式：同样的反证骨架可以证"素数无穷"——假设素数只有有限个，把它们全乘起来加一，新数不被任何一个列出素数整除，矛盾。注意这个证明经常被误称为构造证明，其实它是反证法；真正构造性的无穷素数证明要晚得多（欧拉对调和级数发散的观察提供了另一条路线）。

案例二：构造证明——用中国剩余定理造同余解

命题：对两两互素的模数，任意给定余数，必存在整数同时满足全部同余条件。构造证明不满足于"知道有解"，而是给出显式构造：对每个模数求其它模数乘积的逆元，加权求和。这正是 RSA 等密码系统底层的构造（详见第 4 章数论一节）。直接用代码实现这个构造：

from sympy.ntheory.modular import crt

# 求 x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
moduli, remainders = [3, 5, 7], [2, 3, 2]
x, M = crt(moduli, remainders)
print(x, M)        # 输出 23 105：23 除 3 余 2、除 5 余 3、除 7 余 2
# 手工构造：x = 2*35*inv(35,3) + 3*21*inv(21,5) + 2*15*inv(15,7)
# 其中 inv(a,m) 是 a 模 m 的逆元，全部可由扩展欧几里得算法求出
​

构造证明的工程优势立竿见影：证明即算法。验证 23 满足条件只需三次取模运算，与"存在性证明 + 搜索"相比是量级的差距。

案例三：非构造存在性——抽屉原理的一次降维打击

命题：任意 13 个人中，必有两个人的生日在同一个月。抽屉原理：12 个月是抽屉，13 个生日是物品，物品多于抽屉必有共柜。证明没有指出哪两个人同月，但结论不可动摇。它的力量在反直觉场景才充分释放——"任意 6 个人中必有 3 人两两认识或两两陌生"（拉姆齐数的下界），证明只依赖染色分类讨论，完全不给出具体是哪三人。概率法是非构造存在性的升级版：证明"随机选取命中目标的概率为正"，从而确认目标存在——通信理论里的优秀码存在性、图论里的拉姆齐下界，大量依赖此法。

import random
from itertools import combinations

def birthday_pair_exists(months):
    # 抽屉原理的数值体验：13 人必有两人同月
    seen = set()
    for m in months:
        if m in seen:
            return True
        seen.add(m)
    return False

trials = 10000
hits = sum(birthday_pair_exists([random.randint(1, 12) for _ in range(13)])
           for _ in range(trials))
print(hits / trials)   # 输出 1.0：一万次随机实验无一例外，与原理的必然性一致
​

选择证法的经验法则

读完三个案例，可以提炼几条配对经验。"不存在 / 无理 / 唯一"型命题优先考虑反证法，因为否定结论往往给出更强的可推前提；"存在且要使用"型命题走构造路线，证明副产品是可运行的对象；"存在即可、对象难寻"走抽屉或概率法；若 A 则 B 且 A 信息量大，直接证明最稳。最后一条建议来自惨痛教训：写证明前先用小例子数值验证结论本身——证明一个假命题是数学里最徒劳的工作，而反例往往在 n 等于 2 或 3 时就藏不住。

⚠️ 高频错误：反证法里推出的"矛盾"必须是与假设或已知公理冲突，"与常识不符""太荒谬了"都不是逻辑矛盾。

本节要点回顾

• 四式各有领地：直接证明走前提到结论、反证法消化否定信息、构造证明产出可用对象、存在性证明确认对象在场；
• 根号二无理是反证法的最小完整样本，矛盾点落在最简分数性质上；
• 中国剩余定理的构造证明同时给出算法，是"证明即程序"的典型；
• 抽屉原理与概率法提供了不指认对象的廉价存在性，适合组合与图论；
• 动笔前先用小案例数值验证命题真伪，是成本最低的自查。

至此，第一章的逻辑装备全部到位。下一章开始处理数学的名词本身：数如何一层层构造出来，又如何在群、环、域的框架下显出结构。