数学归纳法与反证法作为证明题的两大基本方法，用处颇多，比如数列的求和公式，极限、不等式等各种问题的证明，真是数不胜数，但这两种方法本身何以成立？为何假设的结论可以推广到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的解读：

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

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

  1. 首先:0∈S0 \in S
  2. 其次:∀n(n∈S→n+1∈S)\forall n(n \in S \to n+1\in S)

把满足 1和 2 两条性质的集合称为，归纳集(inductive set)。但集合论不允许擅自凭空创造一个集合，因此有了以下公理， ∃w(0∈w ∧∀x(x∈w→x+1∈w))\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,… }\{0,0.5,1,1.5,2,2.5,3,3.5,\dots\} 也是归纳集，归纳法在这个归纳集上并不成立。导致这个问题的原因是，这个归纳集存在两条不相交的链，一条是以0为起点，另一条是以0.5为起点。

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

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

  1. P(0)P(0) 成立
  2. P(n)P(n) 成立则 P(n+1)P(n+1) 成立，

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

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

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

反证法的证明

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

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

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

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

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

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

  1. 结论：原命题AA不成立

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

更“数学”一点儿则要去证明矛盾律与排中律的成立，暂且放在这里，等过两天学到了再接着写。

  1. 可以证明1+1=2的那个NB公理 ↩︎

  2. 庄春莲.浅谈反证法[J].黑河教育,1995,0(2):33-34 ↩︎

  3. 高慧明.反证法——数学思想方法系列讲座(10)[J].湖北教育,2019,0(11):26-27 ↩︎

  4. 李玉洁.浅谈反证法证题[J].天津教育,1995(6):43-44 ↩︎