RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2019 Volume 58, Number 2, Pages 229–251 (Mi al892)

This article is cited in 3 papers

Degree spectra of structures relative to equivalences

P. M. Semukhina, D. Turetskyb, E. B. Fokinac

a Dep. Comp. Sci., Univ. Oxford, Oxford, UNITED KINGDOM
b School Math. Stat., Univ. Wellington, Wellington, NEW ZEALAND
c Inst. Discr. Math. Geom., Vienna Univ. of Tech., Wiedner Hauptstraße 8-10/104, 1040 Vienna, AUSTRIA

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.

UDC: 510.5

Received: 10.01.2017
Revised: 09.07.2019

DOI: 10.33048/alglog.2019.58.206


 English version:
Algebra and Logic, 2019, 58:2, 158–172

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024