Geodesic
A note on decidable categoricity and index sets
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1013-1026

Voir la notice de l'article provenant de la source Math-Net.Ru

A structure $S$ is decidably categorical if $S$ has a decidable copy, and for any decidable copies $A$ and $B$ of $S$, there is a computable isomorphism from $A$ onto $B$. Goncharov and Marchuk proved that the index set of decidably categorical graphs is $\Sigma^0_{\omega+2}$ complete. In this paper, we isolate two familiar classes of structures $K$ such that the index set for decidably categorical members of $K$ has a relatively low complexity in the arithmetical hierarchy. We prove that the index set of decidably categorical real closed fields is $\Sigma^0_3$ complete. We obtain a complete characterization of decidably categorical equivalence structures. We prove that decidably presentable equivalence structures have a $\Sigma^0_4$ complete index set. A similar result is obtained for decidably categorical equivalence structures.
Keywords: decidable categoricity, autostability relative to strong constructivizations, index set, real closed field, strong constructivization, decidable structure.
Mots-clés : equivalence structure 
@article{SEMR_2020_17_a22,
     author = {N. Bazhenov and M. Marchuk},
     title = {A note on decidable categoricity and index sets},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1013--1026},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a22/}
}
TY  - JOUR
AU  - N. Bazhenov
AU  - M. Marchuk
TI  - A note on decidable categoricity and index sets
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 1013
EP  - 1026
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a22/
LA  - en
ID  - SEMR_2020_17_a22
ER  - 
%0 Journal Article
%A N. Bazhenov
%A M. Marchuk
%T A note on decidable categoricity and index sets
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 1013-1026
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a22/
%G en
%F SEMR_2020_17_a22
N. Bazhenov; M. Marchuk. A note on decidable categoricity and index sets. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1013-1026. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a22/