A COMPUTABLE @0-CATEGORICAL STRUCTURE WHOSE THEORY COMPUTES TRUE ARITHMETIC
Bakhadyr Khoussainov, Antonio Montalb An · 2008
If a structureB is isomorphic to a computable structureA thenA is called a computable presentation of B. We often identify computable and computably presentable structures. If there exists an algorithm that decides the full diagram of a structure A then A is called a decidable structure. Clearly, decidable structures are computable but the opposite is not always true. Each computable structure is countable. Therefore, in this paper we restrict ourselves to countable structures. One of the major themes in computable model theory investigates computable models of theories. Let T be a deductively closed consistent theory. If T is decidable then the Henkin’s construction can be carried out eectively for T . Therefore, a complete theory T has a decidable model if and only if T is decidable. For complete decidable theories T the class of all decidable models of T has been well studied starting in the 70s. See for example the results by Goncharov [GN73] [Gon78], Millar [Mil78] [Mil81], Morley [Mor76], Harrington [Har74], and Peretyatkin [Per78]. These results investigate decidability of specic models of T such as prime models, saturated models, and homogeneous models. Roughly, prime models are the smallest models since they can be embedded into all models of T , and saturated models are the largest models since all (countable) models of T can be embedded into saturated models. Prime and saturated models are unique up to isomorphism, and homogeneous models are characterized by