Fundamentals of generalized recursion theory
type: Item
instance of: scholarly article
title: Fundamentals of generalized recursion theory
zbMATH Open document ID: 0597.03028
author: Melvin Fitting
published in: Studies in Logic and the Foundations of Mathematics
publication date: 1981-01-01T00:00:00Z
review text: 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 Monta…
Mathematics Subject Classification ID: 03D75
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D65
zbMATH DE Number: 3961596
zbMATH Keywords: Smullyan's elementary formal systems
zbMATH Keywords: search computability
zbMATH Keywords: Montague recursion theory
zbMATH Keywords: admissible sets with urelements
zbMATH Keywords: enumeration operator
zbMATH Keywords: inductive and hyperelementary relations
zbMATH Keywords: inductive definitions
zbMATH Keywords: admissible ordinals
MaRDI profile type: Publication
Recommended article: General Recursion Theory
Recommended article: GENERALIZATIONS OF THE RECURSION THEOREM
Recommended article: Q3325711
Recommended article: Q4274278
Recommended article: Recursion theory
Recommended article: Q4273953
Recommended article: Q4398473
Recommended article: Higher Recursion Theory
Recommended article: Q4040890
description: scientific article; zbMATH DE number 3961596