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

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

首先,集合论的一条公理 ux(x∉u)\exists u\forall x ( x\not\in u) ,使得最开始有一个集合,空集。一个十分经典的构建方式是Von Neumann ordinals,即0,10{0},21{1},32{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. 首先:0S0 \in S
  2. 其次:n(nSn+1S)\forall n(n \in S \to n+1\in S)

把满足 1和 2 两条性质的集合称为,归纳集(inductive set)。但集合论不允许擅自凭空创造一个集合,因此有了以下公理, w(0w x(xwx+1w))\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={xwv(v is inductive setxv)}\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) 成立,

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


证明:令 S={nNP(n)为真}S = \{n\in \mathbb{N} \mid P(n) \text{为真}\} ,可知SNS\subseteq\mathbb{N} 。另一方面,不难证明,SS 是一个归纳集,根据 N\mathbb{N} 的定义NS\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 ↩︎