scientific article; zbMATH DE number 1302876
atomic diagramdegrees of isomorphic copiesdegrees of modelsdynamic storage allocationjump degreemodels for highly non-recursive theoriesmodels of arithmeticrecursive modelsTuring degreeworkers
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Computable structure theory, computable model theory (03C57) Models of arithmetic and set theory (03C62) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45)
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].
- Sufficiency conditions for theories with recursive models
- Coding and definability in computable structures
- Weak truth table degrees of structures
- Degrees of freedom and model search
- Effectively existentially-atomic structures
- Enumeration reducibility and computable structure theory
- Degrees of Recursively Saturated Models
- Degrees of models
- Invariance in ℰ* and ℰ_{Π}
- Degrees of Indiscernibles in Decidable Models
- scientific article; zbMATH DE number 4012589 (Why is no real title available?)
- Some elementary degree-theoretic reasons why structures need similarity types
- Boolean algebras, Stone spaces, and the iterated Turing jump
- Sequences of n-diagrams
- Measuring complexities of classes of structures
- The property ``arithmetic-is-recursive on a cone
- A fixed point for the jump operator on structures
- scientific article; zbMATH DE number 2222018 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249362)
