Fundamentals of generalized recursion theory (Q1078561)

Among the various ways of extending recursion theory to arbitrary structures, this book presents the simplest way, using generalizations by the author of R. M. Smullyan's elementary formal systems. Given any first-order structure \({\mathfrak A}=<A,R_ 1,...,R_ k>\), a relation S on A is said to be recursively enumerable over \({\mathfrak A}\) if it is generated inductively by a finite set of axioms which give instructions for adding n-tuples of elements of A to boxes corresponding to the relation S and possibly to some auxiliary relations. Boxes corresponding to \(R_ 1,...,R_ k\) are given, as are individual constants for all the elements of A. Each instruction says that if certain specified m-tuples (finite in number) are in certain boxes, then some other n-tuple may be added to some box (a box corresponding to S or an auxiliary relation, not one of \(R_ 1,...,R_ k)\). The instruction Sxx (with empty ''if'' clause) defines the identity relation \(x=x\) on A, and for each a in A the instruction Sa defines the 1-place relation \(x=a\), so these relations are recursively enumerable over \({\mathfrak A}\). (The author mentions, but does not follow up, the possibility of allowing individual constants for only some members of A.) When \({\mathfrak A}\) consists of the natural numbers with the successor relation, the usual recursively enumerable relations are obtained. Other choices of \({\mathfrak A}\) yield equivalences with search computability [\textit{Y. N. Moschovakis}, Trans. Am. Math. Soc. 138, 427-504 (1969; Zbl 0218.02038)], and with the special cases of Montague recursion theory [\textit{R. Montague}, Logic, methodology and philosophy of science III, Proc. 3rd Int. Congr. Amsterdam 1967, 63-86 (1968; Zbl 0247.02040)] and the theory of admissible sets with urelements [\textit{J. Barwise}, Admissible sets and structures (1975; Zbl 0316.02047)] obtained by considering the hereditarily finite sets over a first-order structure. \(\{\) What the author calls the Montague theory, with which he suggests that ''one might feel a certain discomfort'', is actually the set-theoretic Barwise theory rather than the higher-order Montague theory.\(\}\) Given a set E of axioms that generates S inductively over \(<A,R_ 1,...,R_ k>\) we can vary \(R_ 1,...,R_ k\) keeping E fixed to produce various output relations S; the operation \((R_ 1,...,R_ k)\mapsto S\) associated with E is an example of a so-called enumeration operator. Enumeration operators (mostly unary: \(R_ k\mapsto S\) with \(R_ 1,...,R_{k-1}\) fixed) are a main theme of the book. In chapter 10 they are generalized to effective type n operators \((n=2,3,...)\) to produce a higher-type recursion theory over an arbitrary first-order model. The connection with the existing theory of type n functionals (based on functions rather than relations as the basic objects) remains to be worked out. Richer generalized recursion theories are obtained by allowing certain infinitary instructions for adding n-tuples of elements of A to boxes. Allowing \(\forall\)-rules (''if (x,y)\(\in B\) for all x then add y to C'') gives what the author calls the \(\omega\)-recursively enumerable relations over \({\mathfrak A}\). Their theory coincides with the theory of inductive and hyperelementary relations [\textit{Y. N. Moschovakis}, Elementary induction on abstract structures (1974; Zbl 0307.02003)] when the latter theory is refined to allow the given relations \(R_ 1,...,R_ k\) to be used only positively in inductive definitions. The \(\omega\)-enumeration operators corresponding to such instructions are studied. Infinitary instructions of a more special kind are introduced in Chapter 9 to bring recursion theory on admissible sets with urelements and on admissible ordinals within the scope of the author's approach. We have omitted mention of many directions in which the author develops his theory (inclining toward an abstract, axiomatic, and category-theoretic exposition); suffice it to say that the power, economy and versatility of the theory are amply demonstrated.