The Complexity of intrinsically r.e. subsets of existentially decidable models

Publisher: Cambridge University Press

E-ISSN: 1943-5886|55|3|1213-1232

ISSN: 0022-4812

Source: The Journal of Symbolic Logic, Vol.55, Iss.3, 1990-09, pp. : 1213-1232

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Recursive model theory involves the study of relationships between recursion theory and model theory. One direction this often takes is to study the effectiveness of various aspects of model theory. This paper examines such questions by examining some properties of recursive models; that is, models whose basic relations, functions, and constants are all uniformly recursive (and whose universe is the set of natural numbers). Somewhat more precisely: