No label defined (Q4249362)

The languages to be considered here are recursive, and the structures have universe \(\omega\). Theories, atomic and complete diagrams of structures, etc., are all identified with subsets of \(\omega\) through Gödel numbering. The Turing degree of a set \(X\) will be denoted by \(\deg(X)\). We shall often identify a structure \({\mathcal A}\) with its atomic diagram, \(D({\mathcal A})\). Thus, we may write \(\deg({\mathcal A})\) for \(\deg(D({\mathcal A}))\), and we say that \({\mathcal A}\) is recursive if \(D({\mathcal A})\) is recursive. It is natural to ask questions such as the following: (1) What are the degrees of isomorphic copies of a particular structure? (2) What are the degrees of models of a particular theory? We consider the set of degrees of isomorphic copies of a given structure. Let \[ DI({\mathcal A})= \{\deg({\mathcal B}):{\mathcal B}\cong{\mathcal A}\}. \] For most structures \({\mathcal A}\), \(DI({\mathcal A})\) is closed upwards. Thus, if \(T\) is a consistent theory, and the models of \(T\) are like most structures, the set of degrees of models of \(T\) will be closed upwards. For a complete, consistent theory \(T\), the Henkin construction yields a model \({\mathcal A}\) which is recursive in \(T\) -- even the complete diagram, \(D^c({\mathcal A})\), is recursive in \(T\). However, for some theories \(T\), there are models of degree well below \(\deg(T)\). Constructing such models, and determining which degrees are possible, can be delicate. Some general facts about \(DI({\mathcal A})\) are stated in Section 1. In Section 2, there is a discussion of structures having ``\(\alpha\)-th jump degree'', where \(\alpha\) is a recursive ordinal. Many of the results on jumps involve structures \({\mathcal A}\) which encode a set \(S\) in a special way, so that, for example, \[ \begin{aligned} DI({\mathcal A}) & = \{\deg(X): S\text{ is r.e. relative to }X\},\quad\text{or}\\ DI({\mathcal A}) &= \{\deg(X): S\text{ is }\Sigma^0_\alpha\text{ relative to }X\}.\end{aligned} \] In Section 3 there are some results on degrees of models of arithmetic, including the result of Harrington for which he introduced the method of ``workers'', and results of Solovay characterizing the degrees of models of various completions of PA. In Section 4, there are some results on existence of recursive models, including a result of Lerman and Schmerl on models of \(\aleph_0\)-categorical theories. For some results, the proof is sketched, possibly in a special case, or there is a hint about the main ingredients of the proof. For other results, the proof is not described at all. For the entire collection see [Zbl 0905.03001].