请输入您要查询的字词:

 

单词 Induction
释义

induction


InductionMathworldPlanetmath is the name given to a certain kind of proof, and also toa (related) way of defining a function.For a proof, the statement tobe proved has a suitably ordered set of cases.Some cases (usually one, but possibly zero or more than one), are provedseparately, and the other cases are deduced from those.The deductionMathworldPlanetmathPlanetmath goes by contradictionMathworldPlanetmathPlanetmath, as we shall see.For a function, its domain is suitably ordered.The function is first defined on some (usually nonempty)subset of its domain, and is then defined at other pointsx in terms of its values at points y such that y<x.

1 Elementary proof by induction

Proof by induction is a varietyMathworldPlanetmathPlanetmath of proof by contradictionMathworldPlanetmath, relying,in the elementary cases, on the fact that every non-empty set ofnatural numbers has a least element.Suppose we want to prove a statement F(n) which involves a naturalnumberMathworldPlanetmath n.It is enough to prove:

1) If n, and F(m) is true for allm such that m<n, then F(n) is true.

or, what is the same thing,

2) If F(n) is false, then F(m) is false for some m<n.

To see why, assume that F(n) is false for some n.Then there is a smallest ksuch that F(k) is false.Then, by hypothesisMathworldPlanetmath, F(n) is true for all n<k.By (1), F(k) is true, which is a contradiction.

(If we don’t regard induction as a kind of proof by contradiction, then wehave to think of it as supplying some kind of sequenceMathworldPlanetmathPlanetmath of proofs, ofunlimited length.That’s not very satisfactory, particularly for transfiniteinductionsMathworldPlanetmath, which we will get to below.)

Usually the initial case of n=0, and sometimes a few cases, needto be proved separately, as in the following example.Write Bn=k=0nk2.We claim

Bn=n33+n22+n6 for all n

Let us try to apply (1). We have the inductive hypothesis (as it is called)

Bm=m33+m22+m6 for all m<n

which tells us something if n>0. In particular, setting m=n-1,

Bn-1=(n-1)33+(n-1)22+n-16

Now we just add n2 to each side, and verify that the right side becomesn33+n22+n6.This proves (1) for nonzero n.But if n=0, the inductive hypothesis is vacuously truePlanetmathPlanetmath, but of no use.So we need to prove F(0) separately, which in this case is trivial.

Textbooks sometimes distinguish between weak andstrong (or completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath) inductive proofs.A proof that relies on the inductive hypothesis (1) is said to goby strong induction. But in the sum-of-squares formulaMathworldPlanetmathPlanetmath above,we needed only the hypothesis F(n-1), not F(m) for all m<n.For another example, a proof about the Fibonacci sequenceMathworldPlanetmath mightuse just F(n-2) and F(n-1).An argument using only F(n-1) is referred to as weak induction.

2 Definition of a function by induction

Let’s begin with an example, the function ,nan, where a is some integer >0.The inductive definition reads

a0=1
an=a(an-1) for all n>0

Formally, such a definition requires some justification, which runs roughlyas follows.Let T be the set of m for which the followingdefinition “has no problem”.

a0=1
an=a(an-1) for 0<nm

We now have a finite sequence fm on the interval [0,m], foreach mT.We verify that any fl and fm have the same valuesthroughout the intersectionMathworldPlanetmathPlanetmath of their two domains.Thus we can define a single function on the union of thevarious domains.Now suppose T, and let k be the least element of-T.That means that the definition has a problem when m=kbut not when m<k.We soon get a contradiction, so we deduce T=.That means that the union of those domains is all of , i.e.the function an is defined, unambiguously, throughout .

Another inductively defined function is the Fibonacci sequence, q.v.

We have been speaking of the inductive definition of a function,rather than just a sequence (a function on ), because thenotions extend with little change to transfinite inductions.An illustration par excellence of inductive proofs anddefinitions is Conway’s theory of surreal numbersMathworldPlanetmath.The numbers and their algebraicMathworldPlanetmath laws of composition are definedentirely by inductions which have no special starting cases.

3 Minor variations of the method

The reader can figure out what is meant by “induction starting at k”,where k is not necessarily zero.Likewise, the term “downward induction” is self-explanatory.

A common variation of the method is proof by induction on afunction of the index n.Rather than spell it out formally, let me just give an example.Let n be a positive integer having no prime factorsMathworldPlanetmathPlanetmath of the form 4m+3.Then n=a2+b2 for some integers a and b.The usual textbook proof uses induction on a function ofn, namely the number of prime factors of n.The induction starts at 1 (i.e. either n=2or prime n=4m+1), which in thisinstance is the only part of the proof that is not quite easy.

4 Well-ordered sets

An ordered set (S,) is said to be well-ordered if any nonempty subsetof S has a least element.The criterion (1), and its proof, hold without change for any well-orderedset S in place of (which is a well-ordered set).But notice that it won’t be enough to prove that F(n) implies F(n+1)(where n+1 denotes the least element >n, if it exists).The reason is, given an element m, there may existelements <m but no element k such that m=k+1.Then the induction from n to n+1 will fail to “reach” m.For more on this topic, look for “limit ordinalsMathworldPlanetmath”.

Informally, any variety of induction whichworks for ordered sets S in which a segmentSx={yS|y<x} may be infiniteMathworldPlanetmath, is called “transfinite induction”.

5 Noetherian induction

An ordered set S, or its order, is called NoetherianPlanetmathPlanetmathPlanetmath if any non-emptysubset of S has a maximal elementMathworldPlanetmath.Several equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath definitions arepossible, such as the “ascending chain conditionMathworldPlanetmathPlanetmathPlanetmath”:any strictly increasing sequence of elements of S is finite.The following result is easily proved by contradiction.

Principle of Noetherian induction: Let (S,) bea set with a Noetherian order, and let T be a subset of S havingthis property: if xS is such that the condition y>x impliesyT, then xT. Then T=S.

So, to prove something “F(x)” about every element x of a Noetherian set,it is enough to prove that “F(z) for all z>y” implies “F(y)”.This time the induction is going downward, but of course that is only amatter of notation.The opposite of a Noetherian order, i.e. an order in which any strictlydecreasing sequence is finite, is also in use; it is called a partialwell-order, or an ordered set having no infinite antichainMathworldPlanetmath.

The standard example of a Noetherian ordered set is the set of idealsin a Noetherian ring.But the notion has various other uses, in topologyas well as algebraPlanetmathPlanetmath.For a nontrivial example of a proof by Noetherianinduction, look up the Hilbert basis theoremMathworldPlanetmath.

6 Inductive ordered sets

An ordered set (S,) is said to be inductive if any totally orderedPlanetmathPlanetmath subsetof S has an upper bound in S.Since the empty setMathworldPlanetmath is totally ordered,any inductive ordered set is non-empty.We have this important result:

Zorn’s lemma: Any inductive ordered set has a maximal element.

Zorn’s lemma is widely used in existence proofsMathworldPlanetmath, rather than in proofsof a property F(x) of an arbitrary element x of an ordered set.Let me sketch one typical application.We claim that every vector space has a basis.First, we prove that if a free subset F, of a vector space V,is a maximal free subset (with respect to the order relation), then it is a basis.Next, to see that the set of free subsets is inductive, it is enoughto verify that the union of any totally ordered set of free subsetsis free, because that union is an upper bound on the totally ordered set.Last, we apply Zorn’s lemma to conclude that V has a maximal freesubset.

随便看

 

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

 

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