Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-19T04:49:07.340Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  12 March 2014

John Chisholm*
Affiliation:
Department of Mathematics, Western Illinois University, Macomb, Illinois 61455

Extract

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:

Let be a model whose universe is N, and let (θ())i be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive if {〈, i〉: satisfies (θ())i, in } is a recursive subset of N. (Here and throughout the paper, 〈 〉 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (ϕ())i be an effective enumeration of all existential formulas of the language of . Then is existentially decidable if {〈, i〉: satisfies (ϕ())i in } is a recursive subset of N.

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].

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable