The degrees of categorical theories with recursive models

Andrews, Uri

doi:10.1090/S0002-9939-2013-11505-4

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