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

 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, Montalbá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 206I 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

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}