Degree Spectra of Structures Relative to Equivalences

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} \), ≅) and the degree spectrum of the theory of \( \mathcal{A} \) is DgSp(\( \mathcal{A} \), ≡). We consider the relations \( {\equiv}_{\sum_n} \) (\( \mathcal{A}{\equiv}_{\sum_n}\mathcal{B} \) iff the Σ_n theories of \( \mathcal{A} \) and \( \mathcal{B} \) coincide) and study degree spectra with respect to \( {\equiv}_{\sum_n} \).