Mathematical induction
10 quotes
Biography
Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true.
"Few contemporaries were as profoundly read in the history of mathematics as was De Morgan. No subject was too insignificant to receive his attention. ...In [his] article "Induction (Mathematics)," first printed in 1838, occurs, apparently for the first time, the name "mathematical induction"; it was adopted and popularized by I. Todhunter in his Algebra. The term "induction" had been used by John Wallis in 1656, in his Arithmetica infinitorum; he used the induction known to natural science. In 1686 Jacob Bernoulli criticised him for using a process which was not binding logically and then advanced in place of it the proof from n to n + 1. This is one of the several origins of the process of mathematical induction. From Wallis to De Morgan, the term "induction" was used occasionally in mathematics, and in a double sense, (1) to indicate incomplete inductions of the kind known in natural science, (2) for the proof from n to n + 1. De Morgan's "mathematical induction" assigns a distinct name for the latter process. The Germans employ more commonly the name "vollständige Induktion," which became current among them after the use of it by R. Dedekind in his Was sind und was sollen die Zahlen, 1887."
"One who extended the theory of equations somewhat further than Vieta was Albert Girard... Like Vieta this ingenious author applied algebra to geometry, and was the first who understood the use of negative roots in the solution of geometric problems. He spoke of imaginary quantities; inferred by induction that every equation has as many roots as there are units in the number expressing its degree; and first showed how to express the sums of their powers in terms of the coefficients.<!--p.166-->"
"A more modern attempt to explain the fruitfulness of mathematical reasoning is that of Poincaré, who finds it all due to the principle of mathematical induction. This principle of mathematical induction is undoubtedly of wide application, though there are many regions even in arithmetic where it is difficult to see its application, e.g., the science of prime numbers, a science dealing entirely with non-recurring individuals. But the important thing to observe is that this principle of mathematical induction is entirely different from the induction that prevails in the physical sciences."
"It is absolutely certain that if a proposition is established by mathematical induction, it will never be disproved, i.e., if a general proposition is true of n + 1 whenever it is true of n, and also of 1, then no possible number can arise of which this proposition is not true, for the principle of mathematical induction is used in defining all finite integers. Whether, therefore, we agree with Russell and call the principle of mathematical induction a definition, or concede to Poincaré that it is a special axiom, a synthetic proposition a priori, the fact remains that reasoning from it is a purely deductive procedure."
"We can not... escape the conclusion that the rule of reasoning by recurrence is irreducible to the principle of contradiction. ...Neither can this rule come to us from experience... This rule, inaccessible to analytic demonstration and to experience, is the veritable type of the synthetic a priori judgment. On the other hand, we can not think of seeing in it a convention, as in some of the postulates of geometry. ...it is only the affirmation of the power of the mind which knows itself capable of conceiving the indefinite repetition of the same act when once this act is possible. The mind has a direct intuition of this power, and experience can only give occasion for using it and thereby becoming conscious of it."
"But, one will say, if raw experience can not legitimatize reasoning by recurrence, is it so of experiment aided by induction? We see successively that a theorem is true of the number 1, of the number 2, of the number 3 and so on; the law is evident, we say, and it has the same warranty as every physical law based on observations, whose number is very great but limited. But there is an essential difference. Induction applied to the physical sciences is always uncertain, because it rests on the belief in a general order of the universe, an order outside of us. Mathematical induction, that is, demonstration by recurrence, on the contrary, imposes itself necessarily, because it is only the affirmation of a property of the mind itself."
"We could call it "proof from n to n + 1" or still simpler "passage to the next integer." Unfortunately, the accepted technical term is "mathematical induction." This name results from a random circumstance. ...Now, in many cases... the assertion is found experimentally, and so the proof appears as a mathematical complement to induction; this explains the name."
"Dedekind proves mathematical induction, while Peano regards it as an axiom. This gives Dedekind an apparent superiority, which must be examined. ...not because of any logical superiority, it seems simpler to begin with mathematical induction. And it should be observed that, in Peano's method, it is only when theorems are to be proved concerning any number that mathematical induction is required. The elementary Arithmetic of our childhood, which discusses only particular numbers, is wholly independent of mathematical induction; though to prove that this is so for every particular number would itself require mathematical induction. In Dedekind's method, on the other hand, propositions concerning particular numbers, like general propositions, demand the consideration of chains. Thus there is, in Peano's method, a distinct advantage of simplicity, and a clearer separation between the particular and the general propositions of Arithmetic. But from a purely logical point of view, the two methods seem equally sound; and it is to be remembered that, with the logical theory of cardinals, both Peano's and Dedekind's axioms become demonstrable."
"Mathematical induction, which is purely ordinal... may be stated as follows: A series generated by a one-one relation, and having a first term, is such that any property, belonging to the first term and to the successor of any possessor of the property, belongs to every term of the series."
"The use of mathematical induction in demonstrations was, in the past, something of a mystery. There seemed no reasonable doubt that it was a valid method of proof, but no one quite knew why it was valid. Some believed it to be really a case of induction, in the sense in which that word is used in logic. Poincaré considered it to be a principle of the utmost importance, by means of which an infinite number of syllogisms could be condensed into one argument. We now know that all such views are mistaken, and that mathematical induction is a definition, not a principle."