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, 2015, Volume 54, Number 4, Pages 520–528
DOI: https://doi.org/10.17377/alglog.2015.54.407
(Mi al708)
 

This article is cited in 11 scientific papers (total in 11 papers)

Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations

E. B. Fokinaa, S. S. Goncharovbc, V. Harizanovd, O. V. Kudinovbc, D. Turetskye

a Vienna University of Technology, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrase 8-10/104, 1040, Vienna, Austria
b Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia
c Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
d George Washington Univ, Washington, DC, 20052, USA
e Kurt Gödel Research Center for Mathematical Logic, University of Vienna, Währinger Strase 25, 1090, Vienna, Austria
References:
Abstract: We say that a structure is categorical relative to $n$-decidable presentations (or autostable relative to $n$-constructivizations) if any two $n$-decidable copies of the structure are computably isomorphic. For $n=0$, we have the classical definition of a computably categorical (autostable) structure. Downey, Kach, Lempp, Lewis, Montalbán, and Turetsky proved that there is no simple syntactic characterization of computable categoricity. More formally, they showed that the index set of computably categorical structures is $\Pi^1_1$-complete.
We study index sets of $n$-decidable structures that are categorical relative to $m$-decidable presentations, for various $m,n\in\omega$. If $m\ge n\ge0$, then the index set is again $\Pi^1_1$-complete, i.e., there is no nice description of the class of $n$-decidable structures that are categorical relative to $m$-decidable presentations. In the case $m=n-1\ge0$, the index set is $\Pi^0_4$-complete, while if $0\le m\le n-2$, the index set is $\Sigma^0_3$-complete.
Keywords: index set, structure categorical relative to $n$-decidable presentations, $n$-decidable structure categorical relative to $m$-decidable presentations.
Funding agency Grant number
Austrian Science Fund V 206
I 1238
Russian Foundation for Basic Research 13-01-91001-АНФ_а
Ministry of Education and Science of the Russian Federation НШ-860.2014.1
Supported by Austrian Science Fund FWF (projects V 206 and I 1238).
Supported by RFBR (project No. 13-01-91001-ANF_a) and by the Grants Council (under RF President) for State Aid of Leading Scientific Schools (grant NSh-860.2014.1).
Received: 12.09.2015
English version:
Algebra and Logic, 2015, Volume 54, Issue 4, Pages 336–341
DOI: https://doi.org/10.1007/s10469-015-9353-6
Bibliographic databases:
Document Type: Article
UDC: 510.53
Language: Russian
Citation: E. B. Fokina, S. S. Goncharov, V. Harizanov, O. V. Kudinov, D. Turetsky, “Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations”, Algebra Logika, 54:4 (2015), 520–528; Algebra and Logic, 54:4 (2015), 336–341
Citation in format AMSBIB
\Bibitem{FokGonHar15}
\by E.~B.~Fokina, S.~S.~Goncharov, V.~Harizanov, O.~V.~Kudinov, D.~Turetsky
\paper Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations
\jour Algebra Logika
\yr 2015
\vol 54
\issue 4
\pages 520--528
\mathnet{http://mi.mathnet.ru/al708}
\crossref{https://doi.org/10.17377/alglog.2015.54.407}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3468414}
\transl
\jour Algebra and Logic
\yr 2015
\vol 54
\issue 4
\pages 336--341
\crossref{https://doi.org/10.1007/s10469-015-9353-6}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000365784700007}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84957967781}
Linking options:
  • https://www.mathnet.ru/eng/al708
  • https://www.mathnet.ru/eng/al/v54/i4/p520
  • This publication is cited in the following 11 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и логика Algebra and Logic
    Statistics & downloads:
    Abstract page:277
    Full-text PDF :46
    References:46
    First page:8
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024