数学归纳法

本页使用了标题或全文手工转换
维基百科,自由的百科全书
(重定向自數學歸納法

数学归纳法(英語:Mathematical Induction,縮寫:MI)是一种数学证明方法,通常被用于证明某个给定命题在整个或者局部自然数范围内成立。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构,例如:集合论中的。这种广义的数学归纳法应用于数学逻辑计算机科学领域,称作结构归纳法

虽然数学归纳法名字中有“归纳”,但是数学归纳法并非逻辑不严谨归纳推理法,它属于完全严谨演绎推理法[1]事實上,所有數學證明都属于演繹推理方法

定义

最简单和常见的数学归纳法是证明当等于任意一个自然数时某命题成立。证明分下面两步:

骨牌一个接一个倒下,就如同一个值到下一个值的过程
  1. 证明 “当时命题成立。”(选择数字1因其作为自然数集合中的最小值)
  2. 证明 “若假设时命题成立,可推導出在时命题成立。(代表任意自然数)”

这种方法的原理在于:首先证明在某个起点值时命题成立,然后证明从一个值到下一个值的过程有效。当这两点都已经证明,那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺骨牌效应也许更容易理解一些。[2][3]例如:你有一列很长的直立着的多米诺骨牌,如果你可以:

  1. 证明 「第一张骨牌会倒。」
  2. 证明 「只要任意一张骨牌倒了,其下一张骨牌也会因為前面的骨牌倒而跟著倒。」

则可下结论:所有的骨牌都会倒下。

例子

例子1

证明下面这个给定公式命题为真

其中为任意自然数。这是用于计算前n个自然数的和的简单公式。

证明

第一步-起始步骤

第一步是验证这个公式在时成立。左边,而右边,所以这个公式在时成立。第一步完成。

第二步-推递步骤

第二步证明假设时公式成立,则可推理公式也成立。 证明步骤如下。

假设时公式成立。即

【等式

然后在等式等号两边分别加上得到 【等式】 这就是时的等式。

现在需要根据等式等式演绎出等式符号形式。(需要注意的是如果给定公式不为真,则做不到)通过因式分解合并(形式变换/字符操纵),等式的右手边

也就是说

这样便证明了从等式成立可推理出等式也成立。证明至此完成,结论:对于任意自然数均成立。

解释

在这个证明中,推理的过程如下:

  1. 首先证明命题成立,即公式时成立。
  2. 然后证明从命题成立可以推演出命题也成立。【此部实际属于演绎推理法。技术方法是基于命题符号形式变换出命题的符号形式】
  3. 根据上两条从命题成立可以推理命题,也就是命题成立。
  4. 继续推理,可以知道命题成立。
  5. 命题成立可以推导出命题也成立。
  6. 不断的重复推導下一命題成立的步驟。(这就是所谓“归纳”推理的地方)
  7. 我们便可以下结论:对于任意自然数命题 成立。

例子2

证明对于Fibonacci数列,定義,且,則

证明

首先,我们先使得的情况成立, 然后,我们假定的情况下的成立的, 然后我们使得的情况也成立,(这是为了表明,如果有任意数k使得其成立,则有其+1也成立) 于是我们得证,即从,到到所有正实数都成立,就像多米诺骨牌的第一块成立而且每一块的下一块都成立()

数学归纳法的变体

在应用中,数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。

从0以外的自然数开始

第一种情况: 如果欲证明的命题并不是针对全部自然数,而只是针对所有大于等于某个数字b的自然数,那么证明的步骤需要做如下修改:

  1. 第一步,证明当时命题成立。
  2. 第二步,证明如果) 成立,那么可以推导出也成立。

用这个方法可以证明诸如“当时,这一类命题。

第二种情况: 如果欲证明的命题针对全部自然数,但仅当大于等于某个数字b时比较容易证明,则可参考如下步骤:

  1. 第一步,证明当时命题成立。
  2. 第二步,证明如果)成立,那么可以推导出也成立。

用这种方法可以证明一些需要通过放缩来证明的不等式。

只針對偶数或只針對奇数

如果我们想证明的命题并不是针对全部自然数,而只是针对所有奇数偶数,那么证明的步骤需要做如下修改:

奇数方面:

  1. 第一步,证明当时命题成立。
  2. 第二步,证明如果成立,那么可以推导出也成立。

偶数方面:

  1. 第一步,证明当或2时命题成立。
  2. 第二步,证明如果成立,那么可以推导出也成立。

或調整命題表述,使之變為對所有正整數成立,例如

證明「對所有正奇數成立」等價於證明「對所有正整數成立」。

遞迴歸納法

又名递降归纳法。数学归纳法并不是只能应用于形如“对任意的”这样的命题。对于形如“对任意的”这样的命题,如果对一般的比较复杂,而比较容易验证,并且我们可以实现从的递推,的话,我们就能应用归纳法得到对于任意的,原命题均成立。

完整归纳法

另一个一般化的方法叫完整归纳法(也称第二数学归纳法或强归纳法),在第二步中我们假定式子不仅当时成立,当小于或等于时也成立。这样可以设计出这样两步:

  1. 证明当时式子成立.
  2. 证明当时成立,那么当时式子也成立.

例如,这种方法被用来证明:

其中 是第斐波纳契数(即黄金分割)。如果我们可以假设式子已经在当时成立,从之后可以直截了当地证明当时式子成立.

这种方法也是第一种形式的特殊化:

  1. 定义是我们将证的式子,
  2. 成立
  3. 成立时成立。

结论:对一切自然数成立。

超限归纳法

最后两步可以用这样一步表示:

证明如果式子在所有的成立,那么式子在当时也成立。

实际上这是数学归纳法的大多数通式,可以知道他不仅对表达自然数的式子有效,而且对于任何在良基集(也就是一个偏序的集合,包括有限降链)中元素的式子也有效(这里""被定义为 当且仅当)。

这种形式的归纳法当运用到序数(以有序的和一些的良基类的形式)时被称为超限归纳法,它在集合论拓扑学和其他领域是一種重要的方法。

要区别用超限归纳法证明的命题的三种情况:

  1. 是一个极小元素,也就是没有一个元素小于
  2. 有一个直接的前辈,比小的元素有一个大的元素
  3. 没有任何前辈,也就是是一个界限序数.

参见数学归纳法的三种形式

形式寫法

使用二階邏輯

二階邏輯可捕捉數學歸納法這概念,表達成如下邏輯式:

是容納一自然數的述詞變元,遍歷所有述詞而非個別數字,為二階量詞(是故此式與二階邏輯有關),則是自然數變元,遍歷所有自然數。

白話解釋此式,此式說:起始步驟與推遞步驟(即歸納假設,蘊涵 ) 兩步成立會導出對任一自然數成立之結論。通常,我們為了證明第二步,會假設成立(歸納假設),再進一步證明。此牽涉到條件證法,將條件句之前件作為假設,假定其正確以便於證明。

使用一階邏輯

若用一階邏輯將數學歸納法公設化,則須採用公設模式,替每一個可能存在的述詞設下針對其的獨立公設。舉例而言,我們僅允許三個一階述詞存在,分別名為 ,則原先以二階邏輯描述的公設可改寫為:

。然而其強度與以二階邏輯描述之邏輯式不同,前者較後者弱。理由為一階邏輯述詞之數量為可數,而二階邏輯量限所迭代的集合為不可數。

此外,二階邏輯所表示的歸納公設綜合其它皮亞諾公設同疇(categorical),且所得之自然數模型無限大。根據勒文海姆-斯科倫定理,用一階邏輯表達的理論若有可數無限大的模型,則其有不可數大的模型,是故無法前頭將所述的模型公設化[4]。亦即,用二階邏輯表達的公設僅允許一群模型彼此同構,而一階邏輯模型則因前述定理,並非每個模型都同構。

使用一階ZFC集合論

一階ZFC集合論不允許述詞被遍歷, 但我們可以藉由遍歷集合,繞過一階邏輯之限制,描述歸納法:

本身是集合,但可視作命題——只要命題在這數下成立,數字就會收入集合。別於皮亞諾公設,將數學歸納法定為公設,ZFC集合論直接定義自然數,使得歸納法本身是定理而非公設。

数学归纳法的合理性

皮亞諾公理視數學歸納法不證自明,設作公理,而於策梅洛-弗兰克尔集合论,數學歸納法可从良序定理推导出来。[5] 需要注意的是数学归纳法只能判定给定命题的,而不能证伪,因为在形式变换这一过程需要一定技巧与灵感抽象概念自然数,可通过抽象的工具去处理。通过有限的步骤处理无限对象如证明质数的无穷。

參見

參考文獻

  1. ^ Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26]. (原始内容存档于2011-05-24) (英语). 
  2. ^ Matt DeVos. Mathematical Induction (PDF). 西門菲莎大學 (英语). 
  3. ^ Gerardo con Diaz. Mathematical Induction (PDF). 哈佛大學. [2019-02-10]. (原始内容 (PDF)存档于2013-05-02) (英语). 
  4. ^ Derek Goldrei. Propositional and predicate calculus: a model of argument. Springer-Verlag London. 2005: 286-287. ISBN 1-85233-921-7 (英语). 
  5. ^ Well Ordering Principle and the Principle of Mathematical Induction (PDF). [2019-02-03]. (原始内容 (PDF)存档于2017-11-19) (英语). 

外部链接