User:Wvbailey/History of recursion

What recursive definition is

Notion has to do with natural numbers 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)

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]