[FOM] "Recursive"

praatika@mappi.helsinki.fi praatika at mappi.helsinki.fi
Mon Sep 25 02:57:43 EDT 2006

Dear Lucius

Recursive definitions of addition and multiplication were, of course, used 
already by Dedekind in 1888. 
Hilbert used the expression ”rekurrente” in 1905, and in 1923 the 
word ”Rekursion”. Skolem (1923) in turn demanded for a recursive mode of 
thinking in the foundations of mathematics. He also proved the (primitive) 
recursiveness of many familiar functions. 

In his paper on the infinite, Hilbert (1926) extended the extension of the 
term and considered more general forms of recursion (with many variables). 
Ackermann (1928) proved that this leads indeed to functions which are not 
(in modern terms) primitive recursive (p.r.). 

In his incompleteness paper, Gödel (1931) defined exactly functions for 
which he used the label "rekursiv"; these are the p.r. functions. Rozsa 
Peter (1934) suggested the name "primitive recursive". 

Gödel was corresponding with Herbrand in 1931. The latter suggested a 
definition of general recursive functions. Gödel develeped the suggestion 
and presented his own definition in his Princeton lectures in 1934. Kleene 
(1936) streamlined it further; he also started to use Peter's "primitive 
recursive" for the narrower class of functions. 

I guess that it was Kleene's Introduction to Metamathematics (1952) that 
made the terminology so widespread.

All the Best, Panu

Panu Raatikainen
Ph.D., Academy Research Fellow,
Docent in Theoretical Philosophy
Department of Philosophy 
University of Helsinki

E-mail: panu.raatikainen at helsinki.fi

Lainaus Lucius Schoenbaum <ltsbaum at gmail.com>:

> Hi All,
> I was wondering if anyone knows whether Gödel was the one (in Gödel  
> 1931) to coin the definition of (what became) primitive recursive  
> which I find in Boolos, Burgess, Jeffrey (2002) and in Cori & Lascar  
> (2001), which I assume must still be widely accepted by way of  
> Kleene?  I am curious about the history of this notion.
> Thanks,
> Lucius Schoenbaum
> -
> Lucius T. Schoenbaum
> 706-206-9121
> ltsbaum at gmail.com
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom

More information about the FOM mailing list