Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations
Algebra i logika, Tome 54 (2015) no. 4, pp. 520-528
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{AL_2015_54_4_a6,
author = {E. B. Fokina and S. S. Goncharov and V. Harizanov and O. V. Kudinov and D. Turetsky},
title = {Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations},
journal = {Algebra i logika},
pages = {520--528},
publisher = {mathdoc},
volume = {54},
number = {4},
year = {2015},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/}
}
TY - JOUR AU - E. B. Fokina AU - S. S. Goncharov AU - V. Harizanov AU - O. V. Kudinov AU - D. Turetsky TI - Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations JO - Algebra i logika PY - 2015 SP - 520 EP - 528 VL - 54 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/ LA - ru ID - AL_2015_54_4_a6 ER -
%0 Journal Article %A E. B. Fokina %A S. S. Goncharov %A V. Harizanov %A O. V. Kudinov %A D. Turetsky %T Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations %J Algebra i logika %D 2015 %P 520-528 %V 54 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/ %G ru %F AL_2015_54_4_a6
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 i logika, Tome 54 (2015) no. 4, pp. 520-528. http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/