Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)


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
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

PII: S 0002-9939(2013)11505-4
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.