[FOM] "Recursive"

Alasdair Urquhart urquhart at cs.toronto.edu
Mon Sep 25 13:58:36 EDT 2006

Dedekind in Section 126 of his "Was sind und was sollen
die Zahlen?" already gives a clear description of
definition by recursion, but doesn't pick out the
class of primitive recursive functions.
Skolem in his "Foundations of Elementary Arithmetic"
of 1923 gives a formulation of what is now called
primitive recursive arithmetic (in a free variable
formalism), though he doesn't formally define the
family of functions (it is implicit in
his paper).

The first person to have singled out the family
explicitly may have been Hilbert in 1925 in
"On the infinite"; Ackermann's article of 1928
"On Hilbert's Construction of the Real Numbers"
singles out the same class.  The class was
therefore one that was well known in the Hilbert
school at the time, though Goedel's definition
of 1931 was apparently the first completely
formal specification of the family of primitive
recursive functions.

All of the above references are translated in
"From Frege to Goedel", except for the monograph
of Dedekind.

Alasdair Urquhart

More information about the FOM mailing list