User:Wvbailey/History of recursion

What recursive definition is

Notion has to do with natural numbers 1, 2, ... and, for most authors after Peano the number 0. As such need [axiomatic proof, evidence] that there exists only one sequence of natural numbers, and that these entities are "orderly".

There can be more than one type of "recursion"; the one commonly used for primitive recursion is that of Goedel 1931 [cf van Heijenoort 1967:493].

From Kleene 1952:

"Proof by induction, as a method of proving a theorm T(y) for all natural numbers y, correspondins immediately to this mode of generating the numbers (§ 7) [establishing 0 and its successors]. Definition by induction (not to be confused with 'inductive definition',...), is also called recursive definition, is the analogous method a number-theoretic function φ(y) or predicate P(y). First φ(0) or P(0) (the value of the function or predicate for 0 as argument) is given. Then, for any natural number y, φ(y') or P(y') (the next value after that for y) is expressed interms of y and φ(y) or P(y) (the value for y). Analogously, we can conclude that under these circumstances the value φ(y) or P(y) of the function or predicate is defined for every natural number y. For the two parts of the definition enable us, as we generate any natural number y, at the samed time to determine the value φ(y') or P(y')." (Kleene 1952:217)

Dedekind 1888

van Heijenoort 1967:493 introduction to Wilhelm Ackermann's 1928 On Hilbert's construction of the real numbers:

"The notion of primitive recursive function appeared, in Dedekind 1888, as a natural generalization of the recursive defintions of addition and multiplication.

The numbers in parentheses refer to the "articles" in his essay (1889) Essays on the Theory of Numbers translated into English (1909) by Behman:

"As such main points I mention here the sharp distinction between finite and infinite (64), the notion of the number [Anzahl] of things (161), the proof that the form of argument known as complete induction (or the inference from n to n+1) is really conclusive (59), (60), (80), and that therefore the definition by induction (or recursion) is determinate and consistent (126)". (Dedekind 1909:33)

Assimilation into Formalism by Hilbert 1925, 1927,

In his 1925:

"Clearly, the elementary means that we have at our disposal for forming functions are substitution (that is, replacement of an argument by a new variable or function) and recursion (according to the schema of the derivation of the function value for n+1 from that for n). ¶ One might think that these two processes, substitution and recursion, would have to be supplemented with other elementary methods of definition . . . ¶ It turns out, however, that any such definition can be represented as a special case of the use of substitutions and recursions. The method of search for the recursions required is in essence equivalent to that reflection by which one recognizes that the procedure use for the given definition is finitary." (Hilbert (1925) On the Infinite in van Heijenoort 1967:385-386)

He goes on, however, to introduce "recursions [that] would not be oridinary, stepwise ones; rather; we would be led to a manifold simultaneous recursion, that is, a recursion on different variables at once, and a resolution of it into ordinary, stepwise recursions would be possible only if we make use of the notion of function variable; the function φ_a(a, a) is an instance of a function, of the number-theoretic variable a, that cannot be defined by substitutions and ordinary, step-wise recursions alone if we admit only number-theoretic variables⁹ (⁹This assertion was proved by W. ackermann [ [1928] ]." (Hilbert (1925) On the Infinite in van Heijenoort 1967:386).

In his 1928 address The Foundations of Mathematics Hilbert presents two "Axioms of number":

16. a'≠ 0;

17. (A(0) & (a)(A(a) --> A(a'))) --> A(b) (principle of mathematical induction.

Here a' denotes the number following a, and the integers 1, 2, 3, . . . can be written in the form 0', 0, 0', . . . .

He then proposes "need[ed] explicit definitions, whitch introduce the notions of mathematics and have the character of axioms, as well as certain recursion axioms, which result form a general recursion schema". He defines variables, and substitution of logical formulas into "propositional variables". Then in particular,

"The recursion associated with the number-theoretic variable n is defined when we indicate what value it has for n = 0 and how the value for n' is obtained from that for n. The generalization of ordinary recursion is transfinite recursion; it rests upon the general priniciple that the value of the function for a value of the variable is determined by means of the preceding values of the function."(van Heijenoort 1967:468. This is repeated almost verbatim at Hilbert 1925 On the Infinite in van Heijenoort 1967:386).

He continues by defining functions of functions, contemporary usage is "composition": [This is messy, see footnote p. 385 re

Φ(f) ~ (a)Z(a) --> Z(f(a))); here Z(a) is an variable [atomic] proposition, a is a natural number, f(a) is a function with natural number a as argument

Ψ(g) ~ (f)(Φ(f) --> Z(g(f)))

"we can now characterize what is to be understood by explicit definitions and by recursion axioms . . . the recursion axioms are formula systems that are modeled upon the recursive procedure. (all quotes from Hilbert 1927) the Foundations of Mathematics in van Heijenoort 1967:467-469

Skolem 1925

Shows that modifying the "inducive schema" (van Heijenoort's "schema A of primitive recursion) to include " "course-of-values" recursion does not actually enlarge the class of functions obtained. (van Heijenoort's commentary before Ackermann (1928) On Hilbert's construction of the real numbers.

Goedel 1931

"Schema A is Goedel's schema of primitive recursion (1931; [see van Heijenoort 1967:602ff]), and it is the schema generally adopted today. Ackermann uses another schema, that of Hilbert (1925; [see van Heijenoort 1967:389]),

(1') f(x, 0) = g(x)

(2') f(x, n+1) = h(x, n, f(y, n))

where h is a function obtained by composition from the intial functions (0, the successor function, the identity functions), previously obtained recursive functions, and the function f(y) but not of n; the argument places marked by y do not actually occur in the function f; the argument places marked by y have been ocupied by functions of the kind just prescribed. The equivalence of schemas A and A' was proved by Péter (1934; see also 1932)." [quote modified, simplified: footnote ^a in van Heijenoort 1967:493]