Mancosu, P., Generalizing classical and effective model theory in theories of operations and classes, Annas of Pure and Applied Logic 52 249-308 . In this paper I propose a family of theories of operations and classes with the aim of developing abstract versions of model-theoretic results. The systems are closely related to those introduced and already used by Feferman for developing his program of ‘explicit mathematics’. The theories in question are two-sorted, with one kind of variable for individuals and the (...) other for classes. The individual variables range over a domain closed under pairing and containing, among other things, natural numbers and operations.All the theories used assume a common group of axioms that insure that the individuals in the domain satisfy the conditions for a partial combinatory algebra with pairing. We also assume a class of natural numbers and a class induction axiom on . Finally there are various class existence axioms. I work mainly with three theories, FMT0, FMT and FMTΩ, which differ from each other both in their class existence axioms as well as in some further applicative axioms.These theories have various interpretations in which every object is explicitly presented by some means of definition as well as classical, or ‘standard’, set-theoretical interpretation. The systems are formulated in a flexible general language which can be used to prove abstract theorems of mathematics , thereby generalizing recursive, hyperarithmetic and admissible versions of classical mathematics.The aim of my work is to give an abstract development of portions of model theory in the afore-mentioned theories, in a way to look as much as possible like classical mathematics. Thus, FMT0 generalizes portions of countable and recursive model theory; FMT further generalizes portions of countable and hyperarithmetical model theory and finally FMTΩ provides a generalization of the classical L-completeness theorem and of an admissible version of L-completeness due to Bruce and Keisler. This continues the development of the program mentioned above, originating with Feferman. (shrink)

Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model A has a d-basis if the types realized in A are all computable and the Turing degree d can list $\Delta _{0}^{0}$ -indices for all types realized in A. We say A has a d-decidable copy if there exists a model B ≅ A such that the elementary (...) diagram of B is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous A with a 0-basis but no decidable copy. We prove that any homogeneous A with a 0'-basis has a low decidable copy. This implies Csima's analogous result for prime models. In the case where all types of the theory T are computable and A is a homogeneous model with a 0-basis, we show A has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous A with a 0-basis has a d-decidable copy. We show that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-homogeneous bounding. (shrink)

We construct a computable ℵ0-categorical structure whose first order theory is computably equivalent to the true first order theory of arithmetic.

In the last five years there have been a number of results about the computable content of the prime, saturated, or homogeneous models of a complete decidable theory T in the spirit of Vaught's "Denumerable models of complete theories" combined with computability methods for degrees d ≤ 0′. First we recast older results by Goncharov, Peretyat'kin, and Millar in a more modern framework which we then apply. Then we survey recent results by Lange, "The degree spectra of homogeneous models," which (...) generalize the older results and which include positive results on when a certain homogeneous model of T has an isomorphic copy of a given Turing degree. We then survey Lange's "A characterization of the 0-basis homogeneous bounding degrees" for negative results about when does not have such copies, generalizing negative results by Goncharov, Peretyat'kin, and Millar. Finally, we explain recent results by Csima, Harizanov, Hirschfeldt, and Soare, "Bounding homogeneous models," about degrees d that are homogeneous bounding and explain their relation to the PA degrees. (shrink)

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This led (...) to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures. (shrink)

We prove that there is a structure, indeed a linear ordering, whose degree spectrum is the set of all non-hyperarithmetic degrees. We also show that degree spectra can distinguish measure from category.

We build an א₁-categorical but not א₀-categorical theory whose only computably presentable model is the saturated one. As a tool, we introduce a notion related to limitwise monotonic functions.

We outline the Hrushovsk-Sokolović proof of Vaught's Conjecture for differentially closed fields, focusing on the use of dimensions to code graphs.

The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...) single CD theory T such that every homogeneous model of T has a PA degree. (shrink)

In this paper we investigate computable models of -categorical theories and Ehrenfeucht theories. For instance, we give an example of an -categorical but not -categorical theory such that all the countable models of except its prime model have computable presentations. We also show that there exists an -categorical but not -categorical theory such that all the countable models of except the saturated model, have computable presentations.