chapter  6
23 Pages

Recursive Relations and-Recursive Functions

The study of primitive recursive functions has lead, in Theorem 5.3, to a description of classes R of relations for which the class F (R ) of functions is closed under primitive recursion. What is important about this description is that (in the conditions (RD0)-{RD4)) no reference to recursion had to mentioned in its hypotheses, and only such descriptions can be susceptible to a formulation by formulas of my ( 1st order) languages as required to arrive at results about representability. What is unsatisfactory about these results is their hypothesis that R be closed under superposition with func­ tions from F (R ), a situation for which I have not given a single example, such that in particular it is not clear whether there are any classes R to which my insights may be applied. It is the purpose of the present Chapter to provide such examples, and to do so in a perspicuous manner.