×

Prime models of computably enumerable degree. (English) Zbl 1155.03017

Summary: We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree \(\mathbf d\) if \(\mathbf d\) is the degree of its elementary diagram. We show that if a CAD theory \(T\) has a prime model of c.e. degree \(\mathbf c\), then \(T\) has a prime model of strictly lower c.e. degree \(\mathbf b\), where, in addition, \(\mathbf b\) is low (\(\mathbf b^\prime =\mathbf 0^\prime \)). This extends Csima’s result that every CAD theory has a low prime model. We also prove a density result for c.e. degrees of prime models. In particular, if \(\mathbf c\) and \(\mathbf d\) are c.e. degrees with \(\mathbf d < \mathbf c\) and \(\mathbf c\) not low\(_2\) \((\mathbf c^{\prime \prime } > \mathbf 0^{\prime \prime})\), then for any CAD theory \(T\), there exists a c.e. degree \(\mathbf b\) with \(\mathbf d < \mathbf b < \mathbf c\) such that \(T\) has a prime model of degree \(\mathbf b\), where \(\mathbf b\) can be chosen so that \(\mathbf b^\prime\) is any degree c.e. in \(\mathbf c\) with \(\mathbf d^\prime \leq \mathbf b^\prime \). As a corollary, we show that for any degree \(\mathbf c\) with \(\mathbf 0 <\mathbf c <\mathbf 0^\prime\), every CAD theory has a prime model of low c.e. degree incomparable with \(\mathbf c\). We show also that every CAD theory has prime models of low c.e. degree that form a minimal pair, extending another result of Csima. We then discuss how these results apply to homogeneous models.

MSC:

03C57 Computable structure theory, computable model theory
03D25 Recursively (computably) enumerable sets and degrees
Full Text: DOI

References:

[1] DOI: 10.1007/BF02219289 · Zbl 0282.02018 · doi:10.1007/BF02219289
[2] Algebra i Logika 17 pp 363– (1978)
[3] Bounding prime models 69 pp 1117– (2004)
[4] Degree spectra of prime models 69 pp 430– (2004)
[5] DOI: 10.1002/malq.19660120125 · Zbl 0181.30504 · doi:10.1002/malq.19660120125
[6] Recursively presentable prime models 39 pp 305– (1974)
[7] The degree spectra of homogeneous models 73 pp 1009– (2008) · Zbl 1160.03014
[8] Degrees coded in jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038
[9] Proceedings of the American Mathematical Society 134 pp 1495– (2006)
[10] Set theory of the continuum pp 39– (1992)
[11] Proceedings of the London Mathematical Society 16 pp 537– (1966)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.