大家好，我是 Senko。 本文将解读“所有的马都是同色”悖论。
使用数学归纳法这个证明技巧，竟能“证明”全世界的马都是同一种颜色。现实中当然没有这回事。那么，这份“证明”错在哪里？
伪证明
数学归纳法分两步进行证明。
奠基步骤：证明 n = 1 时命题成立 归纳步骤：假设 n = k 时成立，证明 n = k+1 时也成立
这两步都完成后，命题就像推倒多米诺骨牌一样，对所有自然数成立。
那么，我们来用归纳法证明“在任意 n 匹马的集合中，所有马都是同色”。
奠基步骤（n = 1）：只有 1 匹马的集合里，所有马（就那 1 匹）当然同色。成立。
归纳步骤：假设“任意 k 匹马的集合中所有马同色”。
考虑 k+1 匹马，记为马 1、马 2、……、马 k、马 k+1。
前 k 匹（马 1～马 k）根据归纳假设全部同色。 后 k 匹（马 2～马 k+1）根据归纳假设也全部同色。
两组在“马 2～马 k”这部分重叠。于是，前一组的颜色 ＝ 重叠部分的颜色 ＝ 后一组的颜色，k+1 匹马全部同色得证。
综上，由归纳法，对一切自然数 n 成立——所有的马都是同色。
……真的吗？
证明的破绽
这个证明的错误藏在从 n = 1 到 n = 2 的过渡里。
考虑 k = 1 的情形：k+1 = 2 匹马，即马 1 和马 2。
按归纳步骤的逻辑：
- 前 k 匹（只有马 1）同色。没错，只有 1 匹嘛。
- 后 k 匹（只有马 2）同色。没错，也只有 1 匹。
可是，两组的“重叠部分”是……空的。
只含马 1 的组和只含马 2 的组，没有任何共同的马。于是，“经由重叠部分推出两组同色”的逻辑不成立。
归纳步骤的证明只在 k ≥ 2 时有效。k = 1 时（n = 1 → n = 2 的过渡）逻辑崩塌，多米诺的第一张牌倒不下去，归纳法宣告失败。
为什么这个悖论有教育意义
这个悖论常出现在数学教学中，就是为了强调归纳步骤必须“对所有 k”成立的重要性。
归纳法是强大的证明手段，但若不确认归纳步骤在与奠基步骤直接衔接的那一环也成立，伪证明就会趁虚而入。
学习数学归纳法时养成自问“归纳步骤真的对所有 k 都成立吗？”的习惯——它是绝佳的反面教材。
归纳法究竟在哪里坏掉了
把证明的漏洞再仔细追一遍。这段论证的弱点只在从1匹迈向2匹的那唯一一处。
按马的匹数看证明成不成立
| 过渡 | 两组的重叠 | 论证成不成立 |
|---|---|---|
| 1匹 → 2匹 | 重叠为0匹 | 不成立 |
| 2匹 → 3匹 | 重叠为1匹 | 成立 |
| 3匹 → 4匹 | 重叠为2匹 | 成立 |
| n匹 → n+1匹（n为2以上） | 重叠为n−1匹 | 成立 |
证明里造出了“去掉第一匹的组”与“去掉最后一匹的组”，再拿它们的重叠当作桥梁。
可当马只有2匹时，前者只剩第二匹，后者只剩第一匹。共有的马一匹也没有，把颜色系起来的根据就消失了。
有意思的是，3匹以上时这段论证完全正确。“若2匹同色，则多少匹都同色”这个主张本身是成立的。坏掉的只有出发的那一级，往后的链条并无问题。
说到底，这个伪证明的结构是：地基只偏了一毫米，上面的楼就整个塌了。
别的有名伪证明
同样地，乍看正确的错误证明还有好几个为人所知。
| 伪证明 | 主张 | 埋进去的错误 |
|---|---|---|
| 1＝2的证明 | 所有的数都相等 | 中途做了除以零 |
| 一切三角形都是等腰 | 任意三角形有两边相等 | 无视了辅助线交点落在图外的情形 |
| 无穷级数的重排 | 和既可以是0也可以是1 | 擅自重排了条件收敛的级数 |
| 所有的马都同色 | 全部同色 | 归纳法的出发点接不上下一级 |
共通的是，错误被收拢在一处，此外全都完全正确。整体看下来没有别扭之处，于是指认哪里不对就变得很难。
用归纳法时的检查清单
把能从这个悖论里抽出来的实践性注意点整理一下。
- 确认出发点：只显示n为1时成立，就不要满足
- 实际迈出第一步：从1到2的过渡，不用一般论，要具体确认一遍
- 数一数用了哪些条件：查一查论证里有没有“至少需要n−1个”这类隐含前提
- 拿小数字试一试：在2和3附近逐个验算结论是否真的正确
尤其第二条管用，因为用一般的n写出的式子看着正确，代入小的值却可能垮掉。
不限于数学证明，写成一般论的步骤在端点情形垮掉，我想在程序设计里也是常事。只有在数组元素为0个或1个时才出故障的缺陷，正是同一个形状。
是谁想出来的
这个伪证明，一般认为是由匈牙利出身的数学家乔治·波利亚传开的。
波利亚在1954年的著作《数学与猜想》等书中，面向一般读者讲解了数学推理该怎么推进。他所看重的不是把正确的证明背下来，而是自己看穿推理在哪里坏掉的能力。
这个关于马的故事，正是作为这类教材被端出来的。结论明显是错的，读者必定会去找漏洞；而找的结果，就是用身体记住了归纳法的出发点有多要紧。
顺带一提，也有说法称它原本不是马，而是“所有女性的发色都相同”。细节随流传而异，结构则相同。
与正确证明的分辨法
我想这个伪证明教给我们的，是归纳法的两个部分各自承担着不同的角色。
- 基底步骤：显示在出发点上成立。这里要确认它为真
- 归纳步骤：显示若n成立则n+1也成立。这里造出链条
许多人把注意力集中在归纳步骤的证明上，对基底步骤常以“这不是明摆着吗”一带而过。
可实际容易坏掉的，是基底步骤与归纳步骤的接缝处。基底步骤本身正确，归纳步骤的论证却可能没法从那个出发点开始。
马的例子正是如此：1匹时同色是正确的，2匹以上的论证也正确，可整体却不成立。“两边都对却接不上”这种状态是可能存在的。
读数学证明时，归纳步骤的论证是不是真的能从基底步骤的下一级开始用，我想至少该具体确认一次。
读证明时，人的目光总往归纳步骤上跑；我自己则是先去怀疑出发点。坏掉的多半是那一侧。
归纳法相关的悖论
以下是与所有的马都是同色同样涉及归纳推理陷阱的相关悖论。
结语
本文解读了“所有的马都是同色”悖论。
看似完美的证明里，潜藏着仅仅一步的疏漏——这个悖论教给我们数学严谨性的分量。
想返回悖论列表的读者请点击下方链接。
我们下一篇文章见。
📚 系列：世界经典悖论（76/81）
读者也常看这些
