General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Algebra Logika:

Personal entry:
Save password
Forgotten password?

Algebra Logika, 2015, Volume 54, Number 4, Pages 520–528 (Mi al708)  

This article is cited in 3 scientific papers (total in 3 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

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


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

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

Bibliographic databases:

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
\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
\jour Algebra and Logic
\yr 2015
\vol 54
\issue 4
\pages 336--341

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. N. Bazhenov, “Autostability spectra for decidable structures”, Math. Struct. Comput. Sci., 28:3, SI (2018), 392–411  crossref  mathscinet  isi  scopus
    2. M. Harrison-Trainor, “There is no classification of the decidably presentable structures”, J. Math. Log., 18:2 (2018), UNSP 1850010  crossref  mathscinet  isi  scopus
    3. N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, K. M. Ng, “Automatic and polynomial-time algebraic structures”, J. Symb. Log., 84:4 (2019), 1630–1669  crossref  mathscinet  zmath  isi  scopus
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:137
    Full text:20
    First page:8

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