Theory spectra and classes of theories

Andrews, Uri; Cai, Mingzhong; Diamondstone, David; Lempp, Steffen; Miller, Joseph

doi:10.1090/tran/6917

Theory spectra and classes of theories
HTML articles powered by AMS MathViewer

by Uri Andrews, Mingzhong Cai, David Diamondstone, Steffen Lempp and Joseph S. Miller PDF

Trans. Amer. Math. Soc. 369 (2017), 6493-6510 Request permission

Abstract:

We analyze the spectra of theories that are $\omega$-stable, theories whose spectra include almost every degree, and theories with uniformly arithmetical $n$-quantifier fragments. We answer a question from Andrews and Miller (2015) by showing that there are $\omega$-stable theories whose spectra are not structure spectra. We show that the spectrum created by Andrews and Knight (2013) is not the spectrum of an $\omega$-stable theory, but is the minimal spectrum of any theory with uniformly arithmetical $n$-quantifier fragments. In addition, we give examples of theory spectra that contain almost every degree, including ones that are known not to be structure spectra.

References

Uri Andrews and Julia F. Knight, Spectra of atomic theories, J. Symbolic Logic 78 (2013), no. 4, 1189–1198. MR 3156519, DOI 10.2178/jsl.7804100
Uri Andrews and Joseph S. Miller, Spectra of theories and structures, Proc. Amer. Math. Soc. 143 (2015), no. 3, 1283–1298. MR 3293742, DOI 10.1090/S0002-9939-2014-12283-0
Solomon Feferman, Arithmetically definable models of formalized arithmetic, Notices Amer. Math. Soc. (1958), no. 5, p. 679.
Noam Greenberg, Antonio Montalbán, and Theodore A. Slaman, Relative to any non-hyperarithmetic set, J. Math. Log. 13 (2013), no. 1, 1250007, 26. MR 3065116, DOI 10.1142/S0219061312500079
Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic 115 (2002), no. 1-3, 71–113. MR 1897023, DOI 10.1016/S0168-0072(01)00087-2
Iskander Kalimullin, Some notes on degree spectra of the structures, Computation and logic in the real world, Lecture Notes in Comput. Sci., vol. 4497, Springer, Berlin, 2007, pp. 389–397. MR 2646249, DOI 10.1007/978-3-540-73001-9_{4}0
I. Sh. Kalimullin, Spectra of degrees of some algebraic structures, Algebra Logika 46 (2007), no. 6, 729–744, 793 (Russian, with Russian summary); English transl., Algebra Logic 46 (2007), no. 6, 399–408. MR 2389421, DOI 10.1007/s10469-007-0039-6
I. Sh. Kalimullin, Restrictions on the spectra of degrees of algebraic structures, Sibirsk. Mat. Zh. 49 (2008), no. 6, 1296–1309 (Russian, with Russian summary); English transl., Sib. Math. J. 49 (2008), no. 6, 1034–1043. MR 2499101, DOI 10.1007/s11202-008-0099-4
Bakhadyr Khoussainov, Andre Nies, and Richard A. Shore, Computable models of theories with few models, Notre Dame J. Formal Logic 38 (1997), no. 2, 165–178. MR 1489408, DOI 10.1305/ndjfl/1039724885
Julia F. Knight, True approximations and models of arithmetic, Models and computability (Leeds, 1997) London Math. Soc. Lecture Note Ser., vol. 259, Cambridge Univ. Press, Cambridge, 1999, pp. 255–278. MR 1721170, DOI 10.1017/CBO9780511565670.011
Angus Macintyre and David Marker, Degrees of recursively saturated models, Trans. Amer. Math. Soc. 282 (1984), no. 2, 539–554. MR 732105, DOI 10.1090/S0002-9947-1984-0732105-5
David Marker, Non $\Sigma _n$ axiomatizable almost strongly minimal theories, J. Symbolic Logic 54 (1989), no. 3, 921–927. MR 1011179, DOI 10.2307/2274752
Robert M. Solovay, Degrees of models of true arithmetic, unpublished manuscript, 1982.