Algebra i logika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra Logika:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra i logika, 2019, Volume 58, Number 2, Pages 229–251
DOI: https://doi.org/10.33048/alglog.2019.58.206
(Mi al892)
 

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
Full-text PDF (407 kB) Citations (3)
References:
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.
Funding agency Grant number
Austrian Science Fund I 1238
P 27527
Supported by the Austrian Science Fund FWF, project No. I 1238. Supported by the Austrian Science Fund FWF, project No. P 27527.
Received: 10.01.2017
Revised: 09.07.2019
English version:
Algebra and Logic, 2019, Volume 58, Issue 2, Pages 158–172
DOI: https://doi.org/10.1007/s10469-019-09534-2
Bibliographic databases:
Document Type: Article
UDC: 510.5
Language: Russian
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
Citation in format AMSBIB
\Bibitem{SemTurFok19}
\by P.~M.~Semukhin, D.~Turetsky, E.~B.~Fokina
\paper Degree spectra of structures relative to equivalences
\jour Algebra Logika
\yr 2019
\vol 58
\issue 2
\pages 229--251
\mathnet{http://mi.mathnet.ru/al892}
\crossref{https://doi.org/10.33048/alglog.2019.58.206}
\transl
\jour Algebra and Logic
\yr 2019
\vol 58
\issue 2
\pages 158--172
\crossref{https://doi.org/10.1007/s10469-019-09534-2}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000479251100006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85069454534}
Linking options:
  • https://www.mathnet.ru/eng/al892
  • https://www.mathnet.ru/eng/al/v58/i2/p229
  • This publication is cited in the following 3 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и логика Algebra and Logic
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024