法本无法：证明数学归纳法与反证法本身

数学归纳法与反证法作为证明题的两大基本方法，用处颇多，比如数列的求和公式，极限、不等式等各种问题的证明，真是数不胜数，但这两种方法本身何以成立？为何假设的结论可以推广到N项，为何否命题不成立原命题就立即成立？

这两个方法本身的证明似乎触及了一些本质的问题。今天在这里我就根据查找的一些资料，谈谈自己的一些理解。

数学归纳法的证明

这个方法居然是公理，来自皮亚诺公理^[1]的第五条：

设S⊆N（自然数），且满足2个条件（i）0∈S；（ii）如果∀n∈S，那么n'∈S。则S是包含全体自然数的集合，即S=N。简易表述：若集合S中全是自然数，且满足两个条件：（1）0在集合S中。（2）若任给实数n在集合S中，那么n的后继数n'也在S中，那么S是包含全体自然数的集合。

这个公理本身是可以证明的，需要用到集合论，这里引用下@Vidas的解读：

五条皮亚诺公理（包含了数学归纳法公理）其实相当于刻画了自然数的结构，如果想证明结构描述之一，归纳法，其实相当于在问，是否能用更加零碎的工具和材料构建出一个集合，使其满足所有皮亚诺公理？答案是可以的，从集合论入手，皮亚诺公理是作为定理来证明的。集合论描述的对象都是集合，每一个实数都可以是一个集合。那么怎么用集合去构建自然数呢？

首先，集合论的一条公理 $\exists u\forall x ( x\not\in u)$ ，使得最开始有一个集合，空集。一个十分经典的构建方式是Von Neumann ordinals，即 $0 \gets \emptyset, 1 \gets 0 \cup \{0\}, 2\gets 1 \cup \{1\}, 3\gets 2\cup\{2\},\dots$ 。因此给定一个集合 n ，不妨定义递进运算 $n+1 = n \cup \{n\}$ 。那么期待的自然数集应该具有什么性质呢？

首先: $0 \in S$
其次: $\forall n(n \in S \to n+1\in S)$

把满足 1和 2 两条性质的集合称为，归纳集(inductive set)。但集合论不允许擅自凭空创造一个集合，因此有了以下公理， $\exists w (0\in w\ \wedge \forall x(x\in w\to x+1\in w))$ 。换句话说，就是用公理明确创建了一个归纳集w 。

但归纳集不一定具有归纳法，举个例子，集合 $\{0,0.5,1,1.5,2,2.5,3,3.5,\dots\}$ 也是归纳集，归纳法在这个归纳集上并不成立。导致这个问题的原因是，这个归纳集存在两条不相交的链，一条是以0为起点，另一条是以0.5为起点。

尽管如此，可以定义自然数集为， $\mathbb{N} = \{x \in w \mid \forall v(v \text{ is inductive set} \to x\in v)\}$ ，其实就是所有归纳集的交集。这个交集是最小归纳集，只有以 0 作为起点这一条链。所有东西准备就绪，接下来就是可以从集合论出发去证明数学归纳法了🤩

数学归纳法定理：如果关于自然数的命题 $P$ 满足

$P(0)$ 成立
$P(n)$ 成立则 $P(n+1)$ 成立，

那么可以得到结论 $\forall n\in\mathbb{N}$ $P(n)$ 成立

证明：令 $S = \{n\in \mathbb{N} \mid P(n) \text{为真}\}$ ，可知 $S\subseteq\mathbb{N}$ 。另一方面，不难证明， $S$ 是一个归纳集，根据 $\mathbb{N}$ 的定义 $\mathbb{N} \subseteq S$ 。因此， $S=\mathbb{N}$ ，证毕。

总结，数学归纳法成立是因为， $\mathbb{N}$ 是最小归纳集，它只有以0作为起点这一条链。对于上述构建出来的 $\mathbb{N}$ ，不难证明其满足其余皮亚诺公(定)理。

反证法的证明

不立接去证明命题的结论,而是先提出与结论相反(相排斥)的假设,然后推导出和已经证明的定理或公理、定义、题设等相矛盾的结果.这样就证明了与结论相反的低设不能成立,从而肯定了原来的结论成立。这种问接证明命产的方法叫做反证法。^[2]

反证法依据的是逻辑思维规律中的“矛盾律”和“排中律”。^[3]^[4]

“矛盾律”:在同一思维过程中，两个互相矛盾的命题( $A$ 与 $\neg A$ )不能同时为真;
“排中律”:两个互相矛盾的命题必有一个是正确的;

假设我们要证明命题 $A$ ：“若人活着，则不需要吃饭。”，根据反证法，我们先

反设：假设命题A的否定命题 $\neg A$ ：“若人活着，则需要吃饭”。
归谬：我们可以很容易证明 $\neg A$ 是成立的：“吃饭则是唯一能提供营养元素的途径，而营养元素是生存所需的(不证自明的公理)，所以活着必须吃饭。”

一般有这四种情形：(1)与已知条件矛盾;(2)与已知的公理、定理、定义矛盾;(3)与假设矛盾;(4)自相矛盾。

结论：原命题 $A$ 不成立

我们在通过反证法证明的过程中，得到了与命题相矛盾的判断( $\neg A$ )，那么根据“矛盾律”，这个矛盾的判断与判断不能同时为真(人活着，不可能既吃饭又不吃饭)，必有一假，而已知条件、公理、定理、法则可证明 $A$ 是假的，所以命题 $\neg A$ 必为真；再根据“排中律”，结论与“否定的结论”这一对立的互相否定的判断不能同时为假，必有一真，于是我们得到原结论“若人活着，则不需要吃饭。”必为假。