Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Theory spectra and classes of theories


Authors: Uri Andrews, Mingzhong Cai, David Diamondstone, Steffen Lempp and Joseph S. Miller
Journal: Trans. Amer. Math. Soc. 369 (2017), 6493-6510
MSC (2010): Primary 03D45, 03C57
DOI: https://doi.org/10.1090/tran/6917
Published electronically: May 16, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Uri Andrews and Julia F. Knight, Spectra of atomic theories, J. Symbolic Logic 78 (2013), no. 4, 1189-1198. MR 3156519
  • [2] Uri Andrews and Joseph S. Miller, Spectra of theories and structures, Proc. Amer. Math. Soc. 143 (2015), no. 3, 1283-1298. MR 3293742, https://doi.org/10.1090/S0002-9939-2014-12283-0
  • [3] Solomon Feferman, Arithmetically definable models of formalized arithmetic, Notices Amer. Math. Soc. (1958), no. 5, p. 679.
  • [4] 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, https://doi.org/10.1142/S0219061312500079
  • [5] 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, https://doi.org/10.1016/S0168-0072(01)00087-2
  • [6] 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, https://doi.org/10.1007/978-3-540-73001-9_40
  • [7] 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, https://doi.org/10.1007/s10469-007-0039-6
  • [8] 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, https://doi.org/10.1007/s11202-008-0099-4
  • [9] 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, https://doi.org/10.1305/ndjfl/1039724885
  • [10] 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, https://doi.org/10.1017/CBO9780511565670.011
  • [11] Angus Macintyre and David Marker, Degrees of recursively saturated models, Trans. Amer. Math. Soc. 282 (1984), no. 2, 539-554. MR 732105, https://doi.org/10.2307/1999251
  • [12] David Marker, Non $ \Sigma _n$ axiomatizable almost strongly minimal theories, J. Symbolic Logic 54 (1989), no. 3, 921-927. MR 1011179, https://doi.org/10.2307/2274752
  • [13] Robert M. Solovay,
    Degrees of models of true arithmetic,
    unpublished manuscript, 1982.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D45, 03C57

Retrieve articles in all journals with MSC (2010): 03D45, 03C57


Additional Information

Uri Andrews
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1325
Email: andrews@math.wisc.edu

Mingzhong Cai
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755
Address at time of publication: Longture Capital, 3-2104 Lujiazui Century Financial Plaza, 799 Yanggao South Road, Pudong, Shanghai 201203, People’s Republic of China
Email: mingzhongcai@gmail.com

David Diamondstone
Affiliation: Google, 1600 Amphitheatre Parkway, Mountain View, California 94043
Email: ddiamondstone@gmail.com

Steffen Lempp
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
Email: lempp@math.wisc.edu

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
Email: jmiller@math.wisc.edu

DOI: https://doi.org/10.1090/tran/6917
Received by editor(s): September 18, 2014
Received by editor(s) in revised form: November 6, 2015
Published electronically: May 16, 2017
Additional Notes: The first author’s research was partly supported by NSF grant DMS-1201338. The second author’s research was partly supported by an AMS Simons Travel Grant and NSF grant DMS-1266214. The fourth author’s research was partially supported by AMS-Simons Foundation Collaboration Grant 209087. The last author’s research was partly supported by NSF grant DMS-1001847.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society