Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


The degrees of categorical theories with recursive models

Author: Uri Andrews
Journal: Proc. Amer. Math. Soc. 141 (2013), 2501-2514
MSC (2010): Primary 03C98, 03D99
Published electronically: February 26, 2013
MathSciNet review: 3043030
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that even for categorical theories, recursiveness of the models guarantees no information regarding the complexity of the theory. In particular, we show that every tt-degree reducible to $ 0^{(\omega )}$ contains both $ \aleph _1$-categorical and $ \aleph _0$-categorical theories in finite languages, all of whose countable models have recursive presentations.

References [Enhancements On Off] (What's this?)

  • 1. Uri Andrews, A new spectrum of recursive models using an amalgamation construction,
    J. Symbolic Logic 76 (2011), 883-896. MR 2849250
  • 2. Uri Andrews and Alice Medvedev, Recursive spectra of strongly minimal theories satisfying the Zilber trichotomy, To appear in Trans. Amer. Math. Soc.
  • 3. C. J. Ash and J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842 (2001k:03090)
  • 4. Ekaterina Fokina, Arithmetic Turing degrees and categorical theories of computable models, Mathematical logic in Asia, World Sci. Publ., Hackensack, NJ, 2006, pp. 58-69. MR 2294286 (2008f:03058)
  • 5. Sergei S. Goncharov and Bakhadyr Khoussainov, Complexity of theories of computable categorical models, Algebra Logika 43 (2004), no. 6, 650-665, 758-759. MR 2135386 (2005m:03066)
  • 6. Sergey S. Goncharov, Valentina S. Harizanov, Michael C. Laskowski, Steffen Lempp, and Charles F. D. McCoy, Trivial, strongly minimal theories are model complete after naming constants, Proc. Amer. Math. Soc. 131 (2003), no. 12, 3901-3912 (electronic). MR 1999939 (2004g:03054)
  • 7. Leo Harrington, Recursively presentable prime models, J. Symbolic Logic 39 (1974), 305-309. MR 0351804 (50:4292)
  • 8. Wilfrid Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. MR 1462612 (98i:03041)
  • 9. Ehud Hrushovski, A new strongly minimal set, Ann. Pure Appl. Logic 62 (1993), no. 2, 147-166, Stability in model theory, III (Trento, 1991). MR 1226304 (94d:03064)
  • 10. Nazif G. Khisamiev, Strongly constructive models of a decidable theory, Izv. Akad. Nauk Kazah. SSR Ser. Fiz.-Mat. (1974), no. 1, 83-84, 94. MR 0354344 (50:6824)
  • 11. Bakhadyr Khoussainov and Antonio Montalbán, A computable $ \aleph _0$-categorical structure whose theory computes true arithmetic, J. Symbolic Logic 75 (2010), no. 2, 728-740. MR 2648162 (2011g:03083)
  • 12. Julia F. Knight, Nonarithmetical $ \aleph _0$-categorical theories with recursive models, J. Symbolic Logic 59 (1994), no. 1, 106-112. MR 1264967 (95a:03045)
  • 13. David Marker, Model theory. An introduction, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. MR 1924282 (2003e:03060)
  • 14. Bruno Poizat, MM. Borel, Tits, Zil$ '$ber et le Général Nonsense, J. Symbolic Logic 53 (1988), no. 1, 124-131. MR 929379 (89c:03060)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03C98, 03D99

Retrieve articles in all journals with MSC (2010): 03C98, 03D99

Additional Information

Uri Andrews
Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706

Received by editor(s): August 8, 2011
Received by editor(s) in revised form: October 11, 2011
Published electronically: February 26, 2013
Communicated by: Julia Knight
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society