|
This article is cited in 3 scientific papers (total 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.
Received: 10.01.2017 Revised: 09.07.2019
Citation:
P. M. Semukhin, D. Turetsky, E. B. Fokina, “Degree spectra of structures relative to equivalences”, Algebra Logika, 58:2 (2019), 229–251; Algebra and Logic, 58:2 (2019), 158–172
Linking options:
https://www.mathnet.ru/eng/al892 https://www.mathnet.ru/eng/al/v58/i2/p229
|
|