Recursion theory on orderings. I. a model theoretic setting

Journal of Symbolic Logic 44 (3):383-402 (1979)
  Copy   BIBTEX


In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. In all of these models, the algebraic closure of a set is nontrivial., is given in §1, however in vector spaces, cl is just the subspace generated byS, in Boolean algebras, cl is just the subalgebra generated byS, and in algebraically closed fields, cl is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings.



    Upload a copy of this work     Papers currently archived: 74,181

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
Recursion Theory on Orderings. II.J. B. Remmel - 1980 - Journal of Symbolic Logic 45 (2):317-333.
Compactness and Independence in Non First Order Frameworks.Itay Ben-Yaacov - 2005 - Bulletin of Symbolic Logic 11 (1):28-50.
Recursion-Theoretic Hierarchies.Peter G. Hinman - 1978 - Berlin, Germany: Springer Verlag.
Quantum Hypercomputation—Hype or Computation?Amit Hagar & Alex Korolev - 2007 - Philosophy of Science 74 (3):347-363.
A Recursion Principle for Linear Orderings.Juha Oikkonen - 1992 - Journal of Symbolic Logic 57 (1):82-96.


Added to PP

31 (#373,273)

6 months
1 (#413,813)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Given.John N. Crossley - 1982 - Studia Logica 41 (2-3):131 - 139.
Recursion Theory on Algebraic Structures with Independent Sets.J. B. Remmel - 1980 - Annals of Mathematical Logic 18 (2):153.

Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Creative Sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Creative Sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.
Recursively Enumerable Vector Spaces.G. Metakides - 1977 - Annals of Mathematical Logic 11 (2):147.

View all 6 references / Add more references