RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
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 Logika, 2015, Volume 54, Number 4, Pages 520–528 (Mi al708)  

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

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).


DOI: https://doi.org/10.17377/alglog.2015.54.407

Full text: PDF file (147 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Algebra and Logic, 2015, 54:4, 336–341

Bibliographic databases:

Document Type: Article
UDC: 510.53
Received: 12.09.2015

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://www.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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000365784700007}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84957967781}


Linking options:
  • http://mi.mathnet.ru/eng/al708
  • http://mi.mathnet.ru/eng/al/v54/i4/p520

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:69
    References:11
    First page:8

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018