×

Bounding prime models. (English) Zbl 1071.03021

Summary: A set \(X\) is prime bounding if for every complete atomic decidable (CAD) theory \(T\) there is a prime model \(\mathfrak A\) of \(T\) decidable in \(X\). It is easy to see that \(X = 0'\) is prime bounding. Denisov claimed that every \(X <_{\text{T}} 0'\) is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets \(X\leq_{\text{T}} 0'\) are exactly the sets which are not \(\text{low}_2\). Recall that \(X\) is \(\text{low}_2\) if \(X''\leq_{\text{T}} 0''\). To prove that a \(\text{low}_2\) set \(X\) is not prime bounding we use a \(0'\)-computable listing of the array of sets \(\{Y : Y \leq_{\text{T}} X\}\) to build a CAD theory \(T\) which diagonalizes against all potential \(X\)-decidable prime models \(\mathfrak A\) of \(T\). To prove that any non-\(\text{low}_2\) \(X\) is indeed prime bounding, we fix a function \(f \leq_{\text{T}} X\) that is not dominated by a certain \(0'\)-computable function that picks out generators of principal types. Given a CAD theory \(T\), we use \(f\) to eventually find, for every formula \(\varphi(\overline x)\) consistent with \(T\), a principal type which contains it, and hence to build an \(X\)-decidable prime model of \(T\). We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory.

MSC:

03C57 Computable structure theory, computable model theory
Full Text: DOI

References:

[1] Zeitschrift für mathematische Logik unddie Grundlagen der Mathematik 12 pp 295–310– (1966)
[2] Recursively enumerable sets and degrees: A study of computable functions and computably generated sets (1987) · Zbl 0667.03030
[3] Degrees coded in jumps of orderings 51 pp 1034–1042– (1986)
[4] Handbook of recursive mathematics 138–139 pp 3–114– (1998)
[5] Algebra and Logic 12 pp 67–77– (1973)
[6] Siberian Mathematics Journal 18 pp 707–716– (1978)
[7] Algebra and Logic 28 pp 405–418– (1989)
[8] Degree spectra of prime models 69 pp 430–442– (2004)
[9] Order 14 pp 107–124– (1998)
[10] Model theory 73 (1990)
[11] Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001
[12] Notre Dame Journal of Formal Logic 38 pp 165–178– (1997)
[13] Handbook of recursive mathematics 138–139 pp 1177–1231– (1998)
[14] Siberian Mathematics Journal 27 pp 572–585– (1986)
[15] Izvestiya Akademiya Nauk Kazakhstan SSR, Seriya Fiziko-Matematicheskaya pp 51–55– (1981)
[16] Infinite Abelian groups (1954) · Zbl 0057.01901
[17] Transactions of the American Mathematical Society 173 pp 33–56– (1972)
[18] Canadian Journal of Mathematics 24 pp 1092–1099– (1972) · Zbl 0254.31006
[19] Proceedings of the American Mathematical Society 129 pp 3079–3083– (2001) · Zbl 0974.03040
[20] Recursively presentable prime models 39 pp 305–309– (1974)
[21] The Bulletin of Symbolic Logic 8 pp 457–477– (2002)
[22] Saturated model theory (1972)
[23] Notre Dame Journal of Formal Logic 40 pp 307–314– (1999)
[24] Omitting types, type spectrums, and decidability 48 pp 171–181– (1983)
[25] Annals of Mathematical Logic 13 pp 45–72– (1978)
[26] Handbook of recursive mathematics 138–139 pp 289–309– (1998)
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.