数学归纳法与反证法作为证明题的两大基本方法,用处颇多,比如数列的求和公式,极限、不等式等各种问题的证明,真是数不胜数,但这两种方法本身何以成立?为何假设的结论可以推广到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的解读:
五条皮亚诺公理(包含了数学归纳法公理)其实相当于刻画了自然数的结构,如果想证明结构描述之一,归纳法,其实相当于在问,是否能用更加零碎的工具和材料构建出一个集合,使其满足所有皮亚诺公理?答案是可以的,从集合论入手,皮亚诺公理是作为定理来证明的。集合论描述的对象都是集合,每一个实数都可以是一个集合。那么怎么用集合去构建自然数呢?
首先,集合论的一条公理 ,使得最开始有一个集合,空集。一个十分经典的构建方式是Von Neumann ordinals,即 。因此给定一个集合 n ,不妨定义递进运算。那么期待的自然数集应该具有什么性质呢?
- 首先:
- 其次:
把满足 1和 2 两条性质的集合称为,归纳集(inductive set)。但集合论不允许擅自凭空创造一个集合,因此有了以下公理, 。换句话说,就是用公理明确创建了一个归纳集w 。
但归纳集不一定具有归纳法,举个例子,集合 也是归纳集,归纳法在这个归纳集上并不成立。导致这个问题的原因是,这个归纳集存在两条不相交的链,一条是以0为起点,另一条是以0.5为起点。
尽管如此,可以定义自然数集为, ,其实就是所有归纳集的交集。这个交集是最小归纳集,只有以 0 作为起点这一条链。所有东西准备就绪,接下来就是可以从集合论出发去证明数学归纳法了🤩
数学归纳法定理:如果关于自然数的命题 满足
- 成立
- 成立则 成立,
那么可以得到结论 成立
证明:令 ,可知 。另一方面,不难证明, 是一个归纳集,根据 的定义 。因此, ,证毕。
总结,数学归纳法成立是因为, 是最小归纳集,它只有以0作为起点这一条链。对于上述构建出来的 ,不难证明其满足其余皮亚诺公(定)理。
反证法的证明
不立接去证明命题的结论,而是先提出与结论相反(相排斥)的假设,然后推导出和已经证明的定理或公理、定义、题设等相矛盾的结果.这样就证明了与结论相反的低设不能成立,从而肯定了原来的结论成立。这种问接证明命产的方法叫做反证法。[2]
反证法依据的是逻辑思维规律中的“矛盾律”和“排中律”。[3][4]
- “矛盾律”:在同一思维过程中,两个互相矛盾的命题(与 )不能同时为真;
- “排中律”:两个互相矛盾的命题必有一个是正确的;
假设我们要证明命题:“若人活着,则不需要吃饭。”,根据反证法,我们先
- 反设:假设命题A的否定命题:“若人活着,则需要吃饭”。
- 归谬:我们可以很容易证明是成立的:“吃饭则是唯一能提供营养元素的途径,而营养元素是生存所需的(不证自明的公理),所以活着必须吃饭。”
一般有这四种情形:(1)与已知条件矛盾;(2)与已知的公理、定理、定义矛盾;(3)与假设矛盾;(4)自相矛盾。
- 结论:原命题不成立
我们在通过反证法证明的过程中,得到了与命题相矛盾的判断(),那么根据“矛盾律”,这个矛盾的判断与判断不能同时为真(人活着,不可能既吃饭又不吃饭),必有一假,而已知条件、公理、定理、法则可证明是假的,所以命题必为真;再根据“排中律”,结论与“否定的结论”这一对立的互相否定的判断不能同时为假,必有一真,于是我们得到原结论“若人活着,则不需要吃饭。”必为假。
更“数学”一点儿则要去证明矛盾律与排中律的成立,暂且放在这里,等过两天学到了再接着写。