Recursion, definition by
Recursion, definition by
A method of introducing, or “defining,” functions from non-negative integers to non-negative integers, which, in its simplest form, consists in giving a pair of equations which specify the value of the function when the argument (or a particular one of the arguments) is 0, and supply a method of calculating the value of the function when the argument (that particular one of the arguments) is x+l, from the value of the function when the argument (that particular one of the arguments) is x. Thus a monadic function f is said to be defined by primitive recursion in terms of a dyadic function g — the function g being previously known or given — by the pair of equations,
f(0) = A,
f(S(x)) = g(x, f(x)),
where A denotes some particular non-negative integer, and S denotes the successor function (so that S(x) is the same as x+l), and x is a variable (the second equation being intended to hold for all non-negative integers x). Similarly the dyadic function f is said to be defined by primitive recursion in terms of a triadic function g and a monadic function h by the pair of equations,
f(a, 0) = h(a),
f(a, S(x)) = g(a, x, f(a,x)),
the equations being intended to hold for all non-negative integers a and x. Likewise for functions f of more than two variables. — As an example of definition by primitive recursion we may take the “definition” of addition (i.e., of the dyadic function plus) employed by Peano in the development of arithmetic from his postulates (see the article Arithmetic, foundations of)
a+0 = a,
a+S(x) = S(a+x).
This comes under the general form of definition by primitive recursion, just given, with h and g taken to be such functions that h(a) = a and g(a, x, y) = S(y). Another example is Peano’s introduction of multiplication by the pair of equations
aX0 = 0,
aXS(x) = (aXx)+a.
Here addition is taken as previously defined, and h(a) = 0, g(a, x, y) = y + a.
More general kinds of definition by recursion allow sets of recursion equations of various forms, the essential requirement being that the equations specify the value of the function being introduced (or the values of the functions being introduced), for any given set of arguments, either absolutely, or in terms of the value (values) for preceding sets of arguments. The word preceding here may refer to the natural order or order of magnitude of the non-negative integers, or it may refer to some other method of ordering arguments or sets of arguments, but the method of ordering shall be such that infinite descending sequences ot sets of arguments (in which each set of arguments is preceded by the next set) are impossible.
The notion of definition by recursion may be extended to functions whose ranges consist of only a portion of the non-negative integers (in the case of monadic functions) or of only a portion of the ordered sets of n non-negative integers (in the case of n-adic functions); also to functions for which the range of the dependent variable may consist wholly or partly of other things than non-negative integers (in particular, propositional functions — properties, relations — of integers may receive definition by recursion).
The employment of definition by recursion in the development of arithmetic from Peano’s postulates, or in the Frege-Russell derivation of arithmetic from logic, requires justification, which most naturallv takes the form of finding a method of replacing a definition by recursion by a nominal definition, or a contextual definition, serving the same purpose. In particular it is possible, by a method due to Dedekind or by any one of a number of modifications of it, to prove the existence of a function f satisfying the conditions expressed by an admissible set of recursion equations, and f may then be given a definition employing descriptions as the function f such that the recursion equations, with suitable quantifiers prefixed, hold. See the paper of Kalmar cited below.
See also the article Recursiveness. — A.C.
L. Kalmar, On the possibility of definition by recursion, Acta Scientiarum Mathematicarum (Szeged), vol. 9 (1940), pp. 227-232.