Characterizations for computable structures
Richard A. Shore, Walker M. White · 2000
A major theme in computable model theory is the study of necessary and sufficient conditions for the existence of certain types of computable structures. These characterizations may either be syntactic, as in the work of Millar [36], or semantic, as in the work of Goncharov [16]. Presented in this dissertation is a general framework for proving syntactic characterizations for the existence of computable models of various theories. This framework is used to show that an axiomatizable ∀2 theory has a computable, existentially closed model if and only if it has an existentially conservative 1-completion for which the set of universal theorems is decidable. Several other uses of this framework are given; one answers an open question of Baldwin and Kueker [4] in the classical model theory of existentially closed, algebraically prime models. Semantic characterizations of computable structures are also investigated. By analyzing the computational complexity of various classes of computable structures, it is shown that various model theoretic properties have no essentially simpler characterization. For example, it is shown that the classes of computable homogeneous structures, computable atomic structures, and computable computably saturated structures are all P0w+2 -complete. Other results include the fact that the class of hyperarithmetically categorical structures is P11 -complete, and that the set of computably categorical structures is P04 -hard.