Degree spectra of structures relative to equivalences

Journal article

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 A and an equivalence relation E, the degree spectrum DgSp(A, E) of A relative to E is defined 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≡∑nB iff the Σn theories of A and B coincide) and study degree spectra with respect to ≡∑n.

Authors: Semukhin, P; Turetsky, D; Fokina, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Verlag
• Journal: Algebra and Logic
• Volume: 58
• Issue: 2
• Pages: 158–172
• Publication date: 2019-07-20
• Acceptance date: 2019-07-09
• DOI: 10.1007/s10469-019-09534-2
• ISSN: 1573-8302, 0002-5232
• Keywords: FFR