Bounding homogeneous models. (English) Zbl 1116.03027
Summary: A Turing degree \({\mathbf d}\) is homogeneous bounding if every complete decidable (CD) theory has a \({\mathbf d}\)-decidable homogeneous model \({\mathcal A}\), i.e., the elementary diagram \(D^e({\mathcal A})\) has degree \({\mathbf d}\). It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a single CD theory \(T\) such that every homogeneous model of \(T\) has a PA degree.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D28 | Other Turing degree structures |
| 03F30 | First-order arithmetic and fragments |
Keywords:
complete decidable theory; homogeneous bounding degree; Turing degree; PA degree; homogeneous modelReferences:
| [1] | Handbook of recursive mathematics 1 pp 3–114– (1998) |
| [2] | Transactions of the American Mathematical Society 282 pp 539–554– (1984) |
| [3] | Algebra and Logic 12 pp 67–77– (1973) |
| [4] | Notices of the American Mathematical Society 6 pp 270– (1959) |
| [5] | Algebra and Logic 19 pp 85–93– (1980) |
| [6] | Computability theory and applications · Zbl 0783.68002 |
| [7] | Algebra and Logic 17 pp 247–263– (1978) |
| [8] | Recursively enumerable sets and degrees (1987) |
| [9] | Constructive models (2000) |
| [10] | Subsystems of second order arithmetic (1999) · Zbl 0909.03048 |
| [11] | Bounding prime models 69 pp 1117–1142– (2004) |
| [12] | Handbook of mathematical logic pp 631–652– (1977) |
| [13] | Degree spectra of prime models 69 pp 430–412– (2004) |
| [14] | Degrees of models 25 pp 233–237– (1960) |
| [15] | Model theory (1990) |
| [16] | Recursive function theory pp 117–121– (1962) |
| [17] | Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001 |
| [18] | Algebra and Logic 17 pp 290–301– (1978) |
| [19] | Israel Journal of Mathematics 5 pp 73–78– (1967) |
| [20] | Degrees coded in jumps of orderings 51 pp 1034–1042– (1986) |
| [21] | Izvestija Akademii Nauk Kazahskoǐ SSR. Serija Fiziko-Matematičeskaja 1 pp 83–84– (1974) |
| [22] | Transactions of the American Mathematical Society 173 pp 33–56– (1972) |
| [23] | Pacific Journal of Mathematics 40 pp 605–616– (1972) |
| [24] | Canadian Journal of Mathematics 24 pp 1092–1099– (1972) · Zbl 0254.31006 |
| [25] | Proceedings of the American Mathematical Society 134 pp 1495–1498– (2006) |
| [26] | Recursively presentable prime models 39 pp 305–309– (1974) |
| [27] | The Bulletin of Symbolic Logic 8 pp 457–477– (2002) |
| [28] | Israel Journal of Mathematics 25 pp 233–240– (1976) |
| [29] | Handbook of computability theory pp 507–532– (1999) |
| [30] | Pacific Journal of Mathematics 91 pp 407–418– (1980) |
| [31] | Annals of Mathematical Logic 13 pp 45–72– (1978) |
| [32] | Model theory: An introduction (2002) · Zbl 1003.03034 |
| [33] | Proceedings of the Herbrand symposium, Logic Colloquium ’81 pp 233–242– (1982) |
| [34] | Proceedings of Symposium on Foundations of Mathematics: Infinitistic Methods pp 301–321– (1961) |
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.
