Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T20:47:09.273Z Has data issue: false hasContentIssue false
  • English
  • Français

The degree spectra of homogeneous models

Published online by Cambridge University Press:  12 March 2014

Karen Lange
Karen Lange*
Affiliation:
Department of Mathematics, 5734 University Avenue, The University of Chicago, Chicago, IL 60637-1546, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 has a d-basis if the types realized in are all computable and the Turing degree d can list -indices for all types realized in . We say has a d-decidable copy if there exists a model ≅ such that the elementary diagram of is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous with a 0-basis but no decidable copy.

We prove that any homogeneous with a 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 is a homogeneous model with a 0-basis, we show has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous with a 0-basis has a d-decidable copy. We show that the nonlow2 degrees are 0-homogeneous bounding.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 3 , September 2008 , pp. 1009 - 1028
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ash, C. J. and Knight, J. F., Computable structures and the hyperarithmetical hierarchy, 1st ed., Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland, Amsterdam, 2000.Google Scholar
[2]Chang, C. C. and Keisler, H. J., Model theory, 3rd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland, Amsterdam, 1990, [1st ed. 1973, 2nd ed. 1977].Google Scholar
[3]Csima, B. F., Degree spectra of prime models, this Journal, vol. 69 (2004), pp. 430–442.Google Scholar
[4]Csima, B. F., Harizanov, V. S., Hirschfeldt, D. R., and Soare, R. I., Bounding homogeneous models, this Journal, vol. 72 (2007), pp. 305–323.Google Scholar
[5]Csima, B. F., Hirschfeldt, D. R., Knight, J. F., and Soare, R. I., Bounding prime models, this Journal, vol. 69 (2004), pp. 1117–1142.Google Scholar
[6]Epstein, R., Computably enumerable degrees of Vaught's models, submitted.Google Scholar
[7]Goncharov, S. S., Strong constructivizability of homogeneous models, Algebra i Logika, vol. 17 (1978), pp. 363–388, 490, in Russian [translated in: Algebra and Logic, vol. 17 (1978), pp. 247-263].Google Scholar
[8]Goncharov, S. S. and Nurtazin, A. T., Constructive models of complete decidable theories. Algebra i Logika, vol. 12 (1973), pp. 125–142, 243, [translated in: Algebra and Logic, vol. 12 (1973), pp. 67-77].Google Scholar
[9]Harizanov, V. S., Pure computable model theory, Handbook of recursive mathematics (Ershov, Yu. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 138–139, North-Holland, Amsterdam, 1998, pp. 3–114.Google Scholar
[10]Harrington, L., Recursively presentable prime models, this Journal, vol. 39 (1974), pp. 305–309.Google Scholar
[11]Harris, K., Bounding saturated models, in preparation.Google Scholar
[12]Hirshfeldt, D. R., Computable trees, prime models, and relative decidability, Proceedings of the American Mathematical Society, vol. 134, 2006, pp. 1495–1498.CrossRefGoogle Scholar
[13]Hirschfeldt, D. R., Shore, R. A., and Slaman, T. A., The atomic model theorem, submitted.Google Scholar
[14]Knight, J. F., Degrees coded in jumps of orderings, this Journal, vol. 51 (1986), pp. 1034–1042.Google Scholar
[15]Lange, K. M., A characterization of the 0-basis homogeneous bounding degrees, in preparation.Google Scholar
[16]Lange, K. M., Reverse mathematics of homogeneous models, in preparation.Google Scholar
[17]Lange, K. M. and Soare, R. I., Computability of homogeneous models, Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 1, pp. 143–170.CrossRefGoogle Scholar
[18]Marker, D., Model theory: an introduction, Graduate Texts in Mathematics, vol. 277, New York, 2002.Google Scholar
[19]Millar, T. S., Foundations of recursive model theory, Annals of Mathematical Logic, vol. 13 (1978), pp. 45–72.CrossRefGoogle Scholar
[20]Millar, T. S., Homogeneous models and decidability, Pacific Journal of Mathematics, vol. 91 (1980), pp. 407–418.CrossRefGoogle Scholar
[21]Millar, T. S., Type structure complexity and decidability, Transactions of the American Mathematical Society, vol. 271 (1982), pp. 73–81.CrossRefGoogle Scholar
[22]Morley, M., Decidable models, Israel Journal of Mathematics, vol. 25 (1976), pp. 233–240.CrossRefGoogle Scholar
[23]Peretyat'kin, M. G., A criterion for strong constructivizability of a homogeneous model, Algebra i Logika, vol. 17 (1978), pp. 436–454, 491, in Russian, [translated in: Algebra and Logic, vol. 19 (1980), pp. 202–229].Google Scholar
[24]Soare, R. I., Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Springer-Verlag, Heidelberg, 1987.CrossRefGoogle Scholar
[25]Soare, R. I., Computability theory and applications, Springer-Verlag, Heidelberg, in preparation.Google Scholar
[26]Tusupov, D. A., Numerations of homogeneous models of decidable complete theories with a computable family of types, Theory of algorithms and its applications (Remeslennikov, V. N., editor), Computable Systems, vol. 129.Google Scholar
[27]Vaught, R. L., Denumerable models of complete theories, Infinitistic Methods (Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959), Pergamon Press, 1961, pp. 301–321.Google Scholar