Spectra of theories and structures

Andrews, Uri; Miller, Joseph

doi:10.1090/S0002-9939-2014-12283-0

Spectra of theories and structures
HTML articles powered by AMS MathViewer

by Uri Andrews and Joseph S. Miller PDF

Proc. Amer. Math. Soc. 143 (2015), 1283-1298 Request permission

Abstract:

We introduce the notion of a degree spectrum of a complete theory to be the set of Turing degrees that contain a copy of some model of the theory. We generate examples showing that not all degree spectra of theories are degree spectra of structures and vice versa. To this end, we give a new necessary condition on the degree spectrum of a structure, specifically showing that the set of PA degrees and the upward closure of the set of 1-random degrees are not degree spectra of structures but are degree spectra of theories.

References

Uri Andrews, Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller, Theory spectra and classes of theories. To appear.
A. El-Sayed Ahmed, A. Kamal, and Aydah Ahmadi, Some characterizations in some Möbius invariant spaces, J. Comput. Anal. Appl. 16 (2014), no. 1, 126–132. MR 3156159
Barbara F. Csima and Iskander S. Kalimullin, Degree spectra and immunity properties, MLQ Math. Log. Q. 56 (2010), no. 1, 67–77. MR 2598838, DOI 10.1002/malq.200910001
K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro, Computability by probabilistic machines, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 183–212. MR 0079550
David Diamondstone, Noam Greenberg, and Daniel Turetsky, Natural large degree spectra, Computability 2 (2013), no. 1, 1–8. MR 3123249, DOI 10.3233/com-13008
Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
Yuri L. Ershov, Definability and computability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1996. MR 1393198
Solomon Feferman, Arithmetically definable models of formalized arithmetic, Not. Amer. Math. Soc. 5 (1958), p. 679.
Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller, and Reed Solomon, Enumerations in computable structure theory, Ann. Pure Appl. Logic 136 (2005), no. 3, 219–246. MR 2169684, DOI 10.1016/j.apal.2005.02.001
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
Wilfrid Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. MR 1462612
Julia F. Knight, Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), no. 4, 1034–1042. MR 865929, DOI 10.2307/2273915
Antonín Kučera. Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$. In Recursion theory week (Oberwolfach, 1984), volume 1141 of Lecture Notes in Math., pages 245–259. Springer, Berlin, 1985.
John M. Macintyre, Transfinite extensions of Friedberg’s completeness criterion, J. Symbolic Logic 42 (1977), no. 1, 1–10. MR 491099, DOI 10.2307/2272313
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
Linda Jean Richter. Degrees of unsolvability of models. PhD thesis, 1977. Ph.D. Thesis, University of Illinois at Urbana-Champaign.
Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
Juichi Shinoda and Theodore A. Slaman, Recursive in a generic real, J. Symbolic Logic 65 (2000), no. 1, 164–172. MR 1782112, DOI 10.2307/2586529
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Ivan N. Soskov, Degree spectra and co-spectra of structures, Annuaire Univ. Sofia Fac. Math. Inform. 96 (2004), 45–68. MR 2068290
Stephan Wehner, Enumerations, countable structures and Turing degrees, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2131–2139. MR 1443415, DOI 10.1090/S0002-9939-98-04314-7