Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-04T17:27:25.119Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounding homogenous models

Published online by Cambridge University Press:  12 March 2014

Barbara F. Csima ,
Valentina S. Harizanov ,
Denis R. Hirschfeldt  and
Robert I. Soare
Barbara F. Csima
Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, ON, N2L 3G1, Canada. E-mail: [email protected]
Valentina S. Harizanov
Affiliation:
Department of Mathematics, The George Washington University, Washington, D.C. 20052, USA. E-mail: [email protected]
Denis R. Hirschfeldt
Affiliation:
Department of Mathematics, The University of Chicago, Chicago, Illinois 60637, USA. E-mail: [email protected] E-mail: [email protected]
Robert I. Soare
Affiliation:
Department of Mathematics, The University of Chicago, Chicago, Illinois 60637, USA. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model , i.e., the elementary diagram De () has degree 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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 1 , March 2007 , pp. 305 - 323
Copyright
Copyright © Association for Symbolic Logic 2007

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, Elsevier, Amsterdam, 2000.Google Scholar
[2]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1990.Google Scholar
[3]Csima, B. F., Degree spectra of prime models, this Journal, vol. 69 (2004), pp. 430–412.Google Scholar
[4]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
[5]Ershov, Yu. L. and Goncharov, S. S., Constructive models, Kluwer Academic/Plenum Publishers, Siberian School of Algebra and Logic, 2000, English translation.CrossRefGoogle Scholar
[6]Goncharov, S. S., Strong constructivizability of homogeneous models, Algebra and Logic, vol. 17 (1978), pp. 247–263, English translation.CrossRefGoogle Scholar
[7]Goncharov, S. S., A totally transcendental decidable theory without constructivizable homogeneous models, Algebra and Logic, vol. 19 (1980), pp. 85–93, English translation.CrossRefGoogle Scholar
[8]Goncharov, S. S. and Nurtazin, A. T., Constructive models of complete solvable theories, Algebra and Logic, vol. 12 (1973), pp. 67–77, English translation.CrossRefGoogle Scholar
[9]Harizanov, V. S., Pure computable model theory. Handbook of recursive mathematics (Ershov, Yu. L., Goncharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W. (associate), editors), vol. 1, Elsevier, Amsterdam, 1998, pp. 3–114.Google Scholar
[10]Harizanov, V. S., Computability-theoretic complexity of countable structures, The Bulletin of Symbolic Logic, vol. 8 (2002), pp. 457–477.CrossRefGoogle Scholar
[11]Harrington, L., Recursively presentable prime models, this Journal, vol. 39 (1974), pp. 305–309.Google Scholar
[12]Harris, K., Bounding saturated models, to appear.Google Scholar
[13]Hirschfeldt, D. R., Computable trees, prime models, and relative decidability, Proceedings of the American Mathematical Society, vol. 134 (2006), pp. 1495–1498.Google Scholar
[14]Jockusch, C. G. Jr., Degrees in which the recursive sets are uniformly recursive, Canadian Journal of Mathematics, vol. 24 (1972), pp. 1092–1099.CrossRefGoogle Scholar
[15]Jockusch, C. G. Jr. and Soare, R. I., Degrees of members classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605–616.CrossRefGoogle Scholar
[16]Jockusch, C. G. Jr. and Soare, R. I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[17]Khisamiev, N. G., Strongly constructive models of a decidable theory, Izvestija Akademii Nauk Kazahskoǐ SSR. Serija Fiziko-Matematičeskaja, vol. 1 (1974), pp. 83–84, in Russian.Google Scholar
[18]Knight, J. F., Degrees coded in jumps of orderings, this Journal, vol. 51 (1986), pp. 1034–1042.Google Scholar
[19]Lange, K., A characterization of the 0-basis homogeneous bounding degrees, to appear.Google Scholar
[20]Lange, K., The degree spectra of homogeneous models, to appear.Google Scholar
[21]Lange, K. and Soare, R. I., Computability of homogeneous models, to appear.Google Scholar
[22]Lange, K. and Soare, R. I., The computable content of Vaughtian models, to appear.Google Scholar
[23]MacIntyre, A. and Marker, D., Degrees of recursively saturated models, Transactions of the American Mathematical Society, vol. 282 (1984), pp. 539–554.CrossRefGoogle Scholar
[24]Marker, D., Degrees of models of true arithmetic, Proceedings of the Herbrand symposium, Logic Colloquium '81 (Stern, J., editor), North-Holland, Amsterdam, 1982, pp. 233–242.Google Scholar
[25]Marker, D., Model theory: An introduction, Springer, New York, 2002.Google Scholar
[26]Millar, T. S., Foundations of recursive model theory, Annals of Mathematical Logic, vol. 13 (1978), pp. 45–72.CrossRefGoogle Scholar
[27]Millar, T. S., Homogeneous models and decidability, Pacific Journal of Mathematics, vol. 91 (1980), pp. 407–418.CrossRefGoogle Scholar
[28]Millar, T. S., Pure recursive model theory, Handbook of computability theory (Griffor, E. R., editor), Elsevier, Amsterdam, 1999, pp. 507–532.Google Scholar
[29]Morley, M. D., Decidable models, Israel Journal of Mathematics, vol. 25 (1976), pp. 233–240.CrossRefGoogle Scholar
[30]Morley, M. D. and Keisler, H. J., On the number of homogeneous models of a given power, Israel Journal of Mathematics, vol. 5 (1967), pp. 73–78.Google Scholar
[31]Peretyat'kin, M. G., Criterion for strong constructivizability of a homogeneous model, Algebra and Logic, vol. 17 (1978), pp. 290–301, English translation.CrossRefGoogle Scholar
[32]Scott, D., Algebras of sets binumerable in complete extensions of arithmetic, Recursive function theory (Dekker, J. C. E., editor), Proceedings of Symposia in Pure Mathematics, no. 5, American Mathematical Society, Providence, Rhode Island, 1962, pp. 117–121.Google Scholar
[33]Shoenfield, J. R., Degrees of models, this Journal, vol. 25 (1960), pp. 233–237.Google Scholar
[34]Simpson, S. G., Degrees of unsolvability: a survey of results, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 631–652.Google Scholar
[35]Simpson, S. G., Subsystems of second order arithmetic, Springer, Berlin, 1999.CrossRefGoogle Scholar
[36]Soare, R. I., Recursively enumerable sets and degrees, Springer, Berlin, 1987.CrossRefGoogle Scholar
[37]Soare, R. I., Computability theory and applications, Springer, Berlin, to appear.Google Scholar
[38]Tennenbaum, S., Non-Archimedean models for arithmetic, Notices of the American Mathematical Society, vol. 6 (1959), p. 270.Google Scholar
[39]Vaught, R. L., Denumerable models of complete theories, Proceedings of Symposium on Foundations of Mathematics: Infinitistic Methods, Pergamon Press, London, 1961, pp. 301–321.Google Scholar