×

A characterization of the \(0\)-basis homogeneous bounding degrees. (English) Zbl 1213.03045

A countable model \(\mathcal A\) has a \(\mathbf 0\)-basis if the types realized in \(\mathcal A\) are uniformly computable, and \(\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. Let \(\mathbf d \leq\mathbf 0'\) be any low\(_{2}\) degree. In the paper under review, the author proves that there exists a homogeneous model \(\mathcal A\) with a \(\mathbf 0\)-basis without a \(\mathbf d\)-decidable copy. This result extends a result by Goncharov, Millar and Peretyat’kin. The author also obtains an exact characterization of the \(\mathbf 0\)-basis homogeneous bounding \(\Delta _{2}^{0}\) degrees. (A degree \(\mathbf d\) is \(\mathbf 0\)-basis homogeneous bounding if any homogeneous \(\mathcal A\) with a \(\mathbf 0\)-basis has a \(\mathbf d\)-decidable copy.)

MSC:

03C57 Computable structure theory, computable model theory
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Computability theory and applications · Zbl 0783.68002
[2] DOI: 10.1090/S0002-9947-09-04847-8 · Zbl 1184.03005
[3] Handbook of recursive mathematics 138 pp 3– (1998)
[4] Algebra i Logika 17 pp 363– (1978)
[5] Prime models of computably enumerable degree 73 pp 1373– (2008)
[6] Bounding prime models 69 pp 1117– (2004)
[7] Bounding homogeneous models 72 pp 305– (2007)
[8] Degree spectra of prime models 69 pp 430– (2004)
[9] Model theory 73 (1990)
[10] Computable structures and the hyperarithmetical hierarchy 144 (2000) · Zbl 0960.03001
[11] Algebra i Logika 17 pp 436– (1978)
[12] DOI: 10.2140/pjm.1980.91.407 · Zbl 0467.03007
[13] DOI: 10.1016/0003-4843(78)90030-X · Zbl 0432.03018
[14] Model theory: An introduction 217 (2002)
[15] DOI: 10.1305/ndjfl/1172787551 · Zbl 1123.03027
[16] The degree spectra of homogeneous models 73 pp 1009– (2008) · Zbl 1160.03014
[17] Degrees coded in jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038
[18] DOI: 10.4153/CJM-1972-113-9 · Zbl 0221.02029
[19] Proceedings of the American Mathematical Society 134 pp 1495– (2006)
[20] Recursively enumerable sets and degrees; A study of computable functions and computably generated sets (1987) · Zbl 0667.03030
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.