Abstract:
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}$.
Keywords:degree spectrum of structure, degree spectrum of theory, degree
spectrum of structure relative to equivalence.