Recursion, proof by
Recursion, proof by
or, as it is more often called, proof by mathematical induction or complete induction, is in its simplest form a proof that every non-negative integer possesses a ceirtain property by showing
that 0 possesses this property, and
that, on the hypothesis that the non-negative integer x possesses this property, then x+1 possesses this property.
(The condition (2) is often expressed, following Frege and Russell, by saying that the property is hereditary in the series of non-negative integers.) The name proof by recursion, or proof by mathematical or complete induction, is also given to various similar but more complex forms.
In Peano’s postulates for arithmetic (see Arithmetic, foundations of) the possibility of proof by recursion is secured by the last postulate, which, indeed, merely states the leading principle of the simplest form of proof by recursion. In the Frege-Russell derivation of arithmetic from logic, the non-negative integers are identified with the inductive cardinal numbers (q.v.), the possibility of proof by recursion being implicit in the definition of inductive. — A.C.