Degree spectra of structures relative to equivalences
P. M. Semukhin, D. Turetsky, Ekaterina Fokina · Algebra i logika · 2019
A standard way to capture the inherent complexity of the isomorphism type of a countable structure is to consider the collection of all Turing degrees relative to which a given structure has a computable isomorphic copy.This set is called the degree spectrum of structure.Similarly, to characterize the complexity of models of a theory, one may consider the collection of all degrees relative to which the theory has a computable model.In this case we get the spectrum of the theory.In this paper we generalize these two notions to arbitrary equivalence relations.For a structure A and an equivalence relation E, we define the degree spectrum DgSp(A, E) of A relative to E to be the set of all degrees capable of computing a structure B that is E-equivalent to A. Then the standard degree spectrum of A is DgSp(A, ∼ =) and the degree spectrum of the theory of A is DgSp(A, ≡).We consider the relations ≡ Σn (A ≡ Σn B iff the Σ n theories of A and B coincide) and study degree spectra with respect to ≡ Σn .