zbMATH — the first resource for mathematics

Degree spectra of prime models. (English) Zbl 1069.03025
Summary: We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic theory has a prime model whose elementary diagram is low. We combine the construction used in the proof with other constructions to show that complete decidable atomic theories have low prime models with added properties.
If we have a complete decidable atomic theory with all types of the theory computable, we show that for every degree \(\mathbf d\) with \({\mathbf 0} < {\mathbf d} \leq {\mathbf 0}'\), there is a prime model with elementary diagram of degree \(\mathbf d\). Indeed, this is a corollary of the fact that if \(T\) is a complete decidable theory and \(L\) is a computable set of c.e. partial types of \(T\), then for any \(\Delta^0_2\) degree \({\mathbf d} > 0\), \(T\) has a \(\mathbf d\)-decidable model omitting the nonprincipal types listed by \(L\).

03C57 Computable structure theory, computable model theory
03B25 Decidability of theories and sets of sentences
03D28 Other Turing degree structures
03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] DOI: 10.1007/BF01980232 · Zbl 0715.03016 · doi:10.1007/BF01980232
[2] Siberian Mathematical Journal 18 pp 707– (1977)
[3] DOI: 10.1007/BFb0095661 · doi:10.1007/BFb0095661
[4] Model theory 73 (1990)
[5] DOI: 10.1090/S0002-9939-98-04314-7 · Zbl 0906.03044 · doi:10.1090/S0002-9939-98-04314-7
[6] Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets (1987) · Zbl 0667.03030
[7] DOI: 10.1090/S0002-9939-98-04307-X · Zbl 0894.03017 · doi:10.1090/S0002-9939-98-04307-X
[8] The -spectrum of a linear order 66 pp 470– (2001)
[9] Omitting types, type spectrums, and decidability 48 pp 171– (1983)
[10] Model theory (2002)
[11] DOI: 10.1016/0003-4843(78)90030-X · Zbl 0432.03018 · doi:10.1016/0003-4843(78)90030-X
[12] Degrees coded in jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038
[13] Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014
[14] Handbook of recursive mathematics 138 pp 3– (1998)
[15] Bounding prime models · Zbl 1071.03021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.