Mathematical induction

A method of proving mathematical results based on the principle of mathematical induction: An assertion $A(x)$, depending on a natural number $x$, is regarded as proved if $A(1)$ has been proved and if for any natural number $n$ the assumption that $A(n)$ is true implies that $A(n+1)$ is also true.

The proof of $A(1)$ is the first step (or base) of the induction and the proof of $A(n+1)$ from the assumed truth of $A(n)$ is called the induction step. Here $n$ is called the induction parameter and the assumption of $A(n)$ for the proof of $A(n+1)$ is called the induction assumption or induction hypothesis. The principle of mathematical induction is also the basis for inductive definition. The simplest example of such a definition is the definition of the property: "to be a word of length $n$ over a given alphabet $\{a_1,\ldots,a_k\}$".

The base of the induction is: Each symbol of the alphabet is a word of length 1. The induction step is: If $E$ is a word of length $n$, then each word $Ea_i$, where $1\leq i\leq k$, is a word of length $(n+1)$. Induction can also start at the zero-th step.

It often happens that $A(1)$ and $A(n+1)$ can be proved by similar arguments. In these cases it is convenient to use the following equivalent form of the principle of mathematical induction. If $A(1)$ is true and if for each natural number $n$ from the assumption: $A(x)$ is true for any natural number $x<n$, it follows that $A(x)$ is also true for $x=n$, then $A(x)$ is true for any natural number $x$. In this form the principle of mathematical induction can be applied for proving assertions $A(x)$ in which the parameter $x$ runs through any well-ordered set of a transfinite type (transfinite induction). As simple examples of transfinite induction one has induction over a parameter running through the set of all words over a given alphabet with the lexicographic ordering, and induction over the construction formulas in a given logico-mathematical calculus.

Sometimes, for the inductive proof of an assertion $A(n)$ one has to inductively prove, simultaneously with $A(n)$, a whole series of other results without which the induction for $A(n)$ cannot be carried out. In formal arithmetic one can also give results $A(n)$ for which, within the limits of the calculus considered, an induction can not be carried out without the addition of new auxiliary results depending on $n$ (see [3]). In these cases one has to deal with the proof of a number of assertions by compound mathematical induction. All these statements could formally be united into one conjunction; however, in practice this would only complicate the discussion and the possibility of informal sensible references to specific induction assumptions would disappear.

In some concrete mathematical investigations the number of notions and results defined and proved by compound induction has reached three figures (see [4]). In this case, because of the presence in induction of a large number of cross references to the induction assumptions, for a concise (informal) understanding of any (even very simple) definition or results for a large value of the induction parameter, the reader must be familiar with the content of all induction ideas and properties of these ideas for small values of the induction parameter. Apparently, the only logically correct outcome of this circle of problems is the axiomatic presentation of all these systems of ideas. Thus, a great number of ideas defined by compound mathematical induction lead to the need for an application of the axiomatic method in inductive definitions and proofs. This is a visual example of the necessity of the axiomatic method for the solution of concrete mathematical problems, and not just for questions relating to the foundations of mathematics.

References

[1]	D. Hilbert, P. Bernays, "Grundlagen der Mathematik" , 1–2 , Springer (1968–1970)
[2]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[3]	L.L. [L.L. Tsinman] Cinman, "On the role of the principle of induction in a formal arithmetic system" Math. USSR Sb. , 6 : 1 (1968) pp. 65–95 Mat. Sb. , 77 : 1 (1968) pp. 71–104
[4]	S.I. Adyan, "The Burnside problem and identities in groups" , Springer (1979) (Translated from Russian)

Comments

In the article above, the natural numbers are $1,2,\ldots$ (i.e. excluding $0$).

References

[a1]	S. Maclane, G. Birkhoff, "Algebra" , Macmillan (1967)