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.