Degree spectra of structures relative to equivalences

P. M. Semukhin ; D. Turetsky ; E. B. Fokina

Algebra i logika, Tome 58 (2019) no. 2, pp. 229-251.

Résumé

A standard way to capture the inherent complexity of the isomorphism type of a countable structure is to consider the set of all Turing degrees relative to which the given structure has a computable isomorphic copy. This set is called the degree spectrum of a structure. Similarly, to characterize the complexity of models of a theory, one may examine the set of all degrees relative to which the theory has a computable model. Such a set of degrees is called the degree spectrum of a theory. We generalize these two notions to arbitrary equivalence relations. For a structure $\mathcal{A}$ and an equivalence relation $E$, the degree spectrum $DgSp(\mathcal{A},E)$ of $\mathcal{A}$ relative to $E$ is defined to be the set of all degrees capable of computing a structure $\mathcal{B}$ that is $E$-equivalent to $\mathcal{A}$. Then the standard degree spectrum of $\mathcal{A}$ is $DgSp(\mathcal{A},\cong)$ and the degree spectrum of the theory of $\mathcal{A}$ is $DgSp(\mathcal{A},\equiv)$. We consider the relations $\equiv_{\Sigma_n}$ ($\mathcal{A} \equiv_{\Sigma_n}\mathcal{B}$ iff the $\Sigma_n$ theories of $\mathcal{A}$ and $\mathcal{B}$ coincide) and study degree spectra with respect to $\equiv_{\Sigma_n}$.

Détail

Keywords: degree spectrum of structure, degree spectrum of theory, degree spectrum of structure relative to equivalence.

Bibliographie

[1] L. J. Richter, “Degrees of structures”, J. Symb. Log., 46:4 (1981), 723–731 | DOI | MR | Zbl

[2] J. F. Knight, “Degrees coded in jumps of orderings”, J. Symb. Log., 51:4 (1986), 1034–1042 | DOI | MR | Zbl

[3] E. B. Fokina, V. Harizanov, A. Melnikov, “Computable model theory”, Turing's Legacy: Developments from Turing's ideas in logic, Lect. Notes Log., 42, ed. R. Downey, Cambridge Univ. Press, Assoc. Symbol. Logic, Cambridge, 2014, 124–194 | MR

[4] I. N. Soskov, “Degree spectra and co-spectra of structures”, God. Sofij. Univ., Fak. Mat. Inform., 96 (2004), 45–68 | MR | Zbl

[5] T. A. Slaman, “Relative to any nonrecursive set”, Proc. Am. Math. Soc., 126:7 (1998), 2117–2122 | DOI | MR | Zbl

[6] S. Wehner, “Enumerations, countable structures and Turing degrees”, Proc. Am. Math. Soc., 126:7 (1998), 2131–2139 | DOI | MR | Zbl

[7] I. Sh. Kalimullin, “Pochti vychislimo perechislimye semeistva mnozhestv”, Matem. sb., 199:10 (2008), 33–40 | DOI

[8] N. Greenberg, A. Montalbán, T. A. Slaman, “Relative to any non-hyperarithmetic set”, J. Math. Log., 13:1 (2013), 1250007, 26 pp. | DOI | MR | Zbl

[9] U. Andrews, J. S. Miller, “Spectra of theories and structures”, Proc. Am. Math. Soc., 143:3 (2015), 1283–1298 | DOI | MR | Zbl

[10] L. Yu, “Degree spectra of equivalence relations”, Proc. 13th Asian logic conf., ALC 2013 (Guangzhou, China, September 16–20, 2013), eds. X. Zhao et al., World Scientific, Hackensack, NJ, 2015, 237–242 | MR | Zbl

[11] E. B. Fokina, D. Rossegger, L. San Mauro, “Bi-embeddability spectra and bases of spectra”, Math. Logic Quart (to appear) | MR

[12] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71—113 | DOI | MR | Zbl

[13] K. de Leeuw, E. F. Moore, C. E. Shannon, N. Shapiro, “Computability by probabilistic machines”, Automata studies, Ann. of Math. Stud., 34, eds. C. E. Shannon, J. McCarthy, Princeton Univ. Press, Princeton, New Jersey, 1956, 183–214 | MR

[14] D. R. Hirschfeldt, W. M. White, “Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures”, Notre Dame J. Formal Logic, 43:1 (2002), 51–64 | DOI | MR | Zbl