×

The degree spectra of homogeneous models. (English) Zbl 1160.03014

Summary: Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model \(\mathcal A\) has a \({\mathbf d}\)-basis if the types realized in \(\mathcal A\) are all computable and the Turing degree \({\mathbf d}\) can list \(\Delta _{0}^{0}\)-indices for all types realized in \(\mathcal A\). We say \(\mathcal A\) has a \({\mathbf d}\)-decidable copy if there exists a model \(\mathcal B\cong \mathcal A\) such that the elementary diagram of \(\mathcal B\) is \({\mathbf d}\)-computable. Goncharov, Millar, and Peretyat’kin independently showed there exists a homogeneous \(\mathcal A\) with a \({\mathbf 0}\)-basis but no decidable copy.
We prove that any homogeneous \(\mathcal A\) with a \({\mathbf 0}'\)-basis has a low decidable copy. This implies Csima’s analogous result for prime models. In the case where all types of the theory \(T\) are computable and \(\mathcal A\) is a homogeneous model with a \({\mathbf 0}\)-basis, we show \(\mathcal A\) has copies decidable in every nonzero degree. A degree \({\mathbf d}\) is \({\mathbf 0}\)-homogeneous bounding if any automorphically nontrivial homogeneous \(\mathcal A\) with a \({\mathbf 0}\)-basis has a \({\mathbf d}\)-decidable copy. We show that the nonlow\(_{2}\) \(\Delta _{2}^{0}\) degrees are \({\mathbf 0}\)-homogeneous bounding.

MSC:

03C57 Computable structure theory, computable model theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1007/BF02757002 · Zbl 0361.02067
[2] Algebra i Logika 17 pp 491– (1978)
[3] DOI: 10.2140/pjm.1980.91.407 · Zbl 0467.03007
[4] Handbook of recursive mathematics 138–139 pp 3– (1998)
[5] Algebra i Logika 12 pp 243– (1973)
[6] Algebra i Logika 17 pp 490– (1978)
[7] Bounding prime models 69 pp 1117– (2004)
[8] Bounding homogeneous models 72 pp 305– (2007)
[9] Degree spectra of prime models 69 pp 430– (2004)
[10] Model theory 73 (1990)
[11] Computable structures and the hyperarithmetical hierarchy 144 (2000) · Zbl 0960.03001
[12] DOI: 10.1016/0003-4843(78)90030-X · Zbl 0432.03018
[13] Model theory: an introduction 277 (2002)
[14] DOI: 10.1305/ndjfl/1172787551 · Zbl 1123.03027
[15] Degrees coded in jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038
[16] Proceedings of the American Mathematical Society 134 pp 1495– (2006)
[17] Recursively presentable prime models 39 pp 305– (1974)
[18] Infinitistic Methods (Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959) pp 301– (1961)
[19] Theory of algorithms and its applications 129
[20] Computability theory and applications · Zbl 0783.68002
[21] Recursively enumerable sets and degrees: A study of computable functions and computably generated sets (1987) · Zbl 0667.03030
[22] DOI: 10.1090/S0002-9947-1982-0648078-8
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.