The degrees of categorical theories with recursive models
HTML articles powered by AMS MathViewer
- by Uri Andrews PDF
- Proc. Amer. Math. Soc. 141 (2013), 2501-2514 Request permission
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
- Uri Andrews, A new spectrum of recursive models using an amalgamation construction, J. Symbolic Logic 76 (2011), no. 3, 883–896. MR 2849250, DOI 10.2178/jsl/1309952525
- Uri Andrews and Alice Medvedev, Recursive spectra of strongly minimal theories satisfying the Zilber trichotomy, To appear in Trans. Amer. Math. Soc.
- C. J. Ash and J. 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
- E. 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
- S. S. Goncharov and B. Khusainov, Complexity of theories of computable categorical models, Algebra Logika 43 (2004), no. 6, 650–665, 758–759 (Russian, with Russian summary); English transl., Algebra Logic 43 (2004), no. 6, 365–373. MR 2135386, DOI 10.1023/B:ALLO.0000048826.92325.02
- 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. MR 1999939, DOI 10.1090/S0002-9939-03-06951-X
- Leo Harrington, Recursively presentable prime models, J. Symbolic Logic 39 (1974), 305–309. MR 351804, DOI 10.2307/2272643
- Wilfrid Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. MR 1462612
- 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, DOI 10.1016/0168-0072(93)90171-9
- N. G. Hisamiev, Strongly constructive models of a decidable theory, Izv. Akad. Nauk Kazah. SSR Ser. Fiz.-Mat. 1 (1974), 83–84, 94 (Russian). MR 0354344
- 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, DOI 10.2178/jsl/1268917501
- Julia F. Knight, Nonarithmetical $\aleph _0$-categorical theories with recursive models, J. Symbolic Logic 59 (1994), no. 1, 106–112. MR 1264967, DOI 10.2307/2275253
- David Marker, Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. An introduction. MR 1924282
- Bruno Poizat, MM. Borel, Tits, Zil′ber et le Général Nonsense, J. Symbolic Logic 53 (1988), no. 1, 124–131 (French). MR 929379, DOI 10.2307/2274432
Additional Information
- Uri Andrews
- Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706
- Email: andrews@math.wisc.edu
- 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
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 141 (2013), 2501-2514
- MSC (2010): Primary 03C98, 03D99
- DOI: https://doi.org/10.1090/S0002-9939-2013-11505-4
- MathSciNet review: 3043030