{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:22:09Z","timestamp":1747545729701},"reference-count":7,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":8593,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1990,9]]},"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:<\/jats:p>Let be a model whose universe is N, and let (\u03b8<\/jats:italic>())i<\/jats:italic><\/jats:sub> be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive<\/jats:italic> if {\u3008, i<\/jats:italic>\u3009: satisfies (\u03b8<\/jats:italic>())i<\/jats:italic><\/jats:sub>, in } is a recursive subset of N. (Here and throughout the paper, \u3008 \u3009 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (\u03d5<\/jats:italic>())i<\/jats:italic><\/jats:sub> be an effective enumeration of all existential formulas of the language of . Then is existentially decidable<\/jats:italic> if {\u3008, i<\/jats:italic>\u3009: satisfies (\u03d5<\/jats:italic>())i<\/jats:italic><\/jats:sub> in } is a recursive subset of N.<\/jats:p>It is clear that if is recursive and is a model isomorphic to , then may lose many of the recursive properties of . In the simplest example, could easily fail to be a recursive model. But even if we require that be a recursive model, it could still fail to retain other recursive properties of . An example of the sort of property which can be studied in this vein is the following notion, introduced by Ash and Nerode in [2].<\/jats:p>","DOI":"10.2307\/2274483","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:36:50Z","timestamp":1146955010000},"page":"1213-1232","source":"Crossref","is-referenced-by-count":8,"title":["The Complexity of intrinsically r.e. subsets of existentially decidable models"],"prefix":"10.1017","volume":"55","author":[{"given":"John","family":"Chisholm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200025652_ref007","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200025652_ref005","unstructured":"Manasse Mark Steven , Techniques and counterexamples in almost categorical recursive model theory, Ph.D. dissertation, University of Wisconsin, Madison, Wisconsin, 1982."},{"key":"S0022481200025652_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669456"},{"key":"S0022481200025652_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90048-5"},{"key":"S0022481200025652_ref002","first-page":"26","volume-title":"Aspects of recursive algebra","author":"Ash","year":"1981"},{"key":"S0022481200025652_ref004","volume-title":"Model theory for infinite logic","author":"Keisler","year":"1971"},{"key":"S0022481200025652_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF01463352"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200025652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T20:25:42Z","timestamp":1558211142000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200025652\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,9]]},"references-count":7,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,9]]}},"alternative-id":["S0022481200025652"],"URL":"https:\/\/doi.org\/10.2307\/2274483","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,9]]}}}