请输入您要查询的字词:

 

单词 PrincipleOfFiniteInduction
释义

principle of finite induction


The principle of finite induction, also known as mathematical induction, is commonly formulated in two ways. Both are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. The first formulation is known as weak inductionMathworldPlanetmath. It asserts that if a statement P(n) holds for n=0 and if P(n)P(n+1), then P(n) holds for all natural numbersMathworldPlanetmath n. The case n=0 is called the base case or base step and the implicationMathworldPlanetmath P(n)P(n+1) is called the inductive step. In an inductive proof, one uses the term induction hypothesis or inductive hypothesis to refer back to the statement P(n) when one is trying to prove P(n+1) from it.

The second formulation is known as strong or completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath induction. It asserts that if the implication n((m<nP(m))P(n)) is true, then P(n) is true for all natural numbers n. (Here, the quantifiersMathworldPlanetmath range over all natural numbers.) As we have formulated it, strong induction does not require a separate base case. Note that the implication n((m<nP(m))P(n) already entails P(0) since the statement m<0P(m) holds vacuously (there are no natural numbers less that zero).

A moment’s thought will show that the first formulation (weak induction) is equivalent to the following:

Let S be a set natural numbers such that

  1. 1.

    0 belongs to S, and

  2. 2.

    if n belongs to S, so does n+1.

Then S is the set of all natural numbers.

Similarly, strong induction can be stated:

If S is a set of natural numbers such that n belongs to S whenever all numbers less than n belong to S, then S is the set of all natural numbers.

The principle of finite induction can be derived from the fact that every nonempty set of natural numbers has a smallest element. This fact is known as the well-ordering principle for natural numbers. (Note that this is not the same thing as the well-ordering principle, which is equivalent to the axiom of choiceMathworldPlanetmath and has nothing to do with induction.)

Titleprinciple of finite induction
Canonical namePrincipleOfFiniteInduction
Date of creation2013-03-22 11:46:41
Last modified on2013-03-22 11:46:41
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id24
AuthorCWoo (3771)
Entry typeTheoremMathworldPlanetmath
Classificationmsc 03E25
Classificationmsc 00-02
Related topicTransfiniteInduction
Related topicAnExampleOfMathematicalInduction
Related topicInduction
Related topicWellFoundedInduction
Definesinduction hypothesis
Definesinductive hypothesis
Definesbase case
Definesbase step
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 5:18:26