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/

[1] Yu. L. Ershov, “Constructive models”, Selected Questions of Algebra and Logic, eds. Yu. L. Ershov, M. I. Kargapolov, Yu. I. Merzlyakov, D. M. Smirnov, A. I. Shirshov, Nauka, Novosibirsk, 1973, 111–130 (In Russian) | MR

[2] M. Morley, “Decidable models”, Isr. J. Math., 25:3–4 (1976), 233–240 | DOI | MR | Zbl

[3] S. S. Goncharo, A. T. Nurtazin, “Constructive models of complete solvable theories”, Algebra Logic, 12:2 (1973), 67–77 | DOI | MR

[4] L. Harrington, “Recursively presentable prime models”, J. Symb. Log., 39:2 (1974), 305–309 | DOI | MR | Zbl

[5] S. S. Goncharov, “Strong constructivizability of homogeneous models”, Algebra Logic, 17:4 (1978), 247–263 | DOI | MR

[6] M. G. Peretyat'kin, “Criterion for strong constructivizability of a homogeneous model”, Algebra Logic, 17:4 (1978), 290–301 | DOI | MR

[7] V. S. Harizanov, “Pure computable model theory”, Handbook of Recursive Mathematics, v. 1, Stud. Logic Found. Math., 138, eds. Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, Elsevier Science B. V., Amsterdam, 1998, 3–114 | DOI | MR | Zbl

[8] P. Cholak, C. McCoy, “Effective prime uniqueness”, Proc. Am. Math. Soc., 145:12 (2017), 5363–5379 | DOI | MR | Zbl

[9] S. S. Goncharov, “On autostability of almost prime models relative to strong constructivizations”, Russ. Math. Surv., 65:5 (2010), 901–935 | DOI | MR | Zbl

[10] D. R. Hirschfeldt, K. Lange, R. A. Shore, Induction, bounding, weak combinatorial principles, and the homogeneous model theorem, Mem. Am. Math. Soc., 249, 2017, iii+101 pp. | MR

[11] A. T. Nurtazin, “Strong and weak constructivization and computable families”, Algebra Logic, 13:3 (1974), 177–184 | DOI | MR

[12] S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations”, Algebra Logic, 54:2 (2015), 108–126 | DOI | MR | Zbl

[13] R. G. Downey, A. M. Kach, S. Lempp, A. Lewis-Pye, A. Montalbán, D. Turetsky, “The complexity of computable categoricity”, Adv. Math., 268 (2015), 423–466 | DOI | MR | Zbl

[14] S. S. Goncharov, V. D. Dzgoev, “Autostability of models”, Algebra Logic, 19:1 (1980), 28–37 | DOI | MR | Zbl

[15] S. S. Goncharov, N. A. Bazhenov, M.I. Marchuk, “Index set of linear orderings that are autostable relative to strong constructivizations”, J. Math. Sci., New York, 221:6 (2017), 840–848 | DOI | MR

[16] D. Cenzer, V. Harizanov, J. B. Remmel, “$\Sigma^0_1$ and $\Pi^0_1$ equivalence structures”, Ann. Pure Appl. Logic, 162:7 (2011), 490–503 | DOI | MR | Zbl

[17] C. J. Ash, J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Logic Found. Math., 144, Elsevier Science B. V., Amsterdam, 2000 | MR | Zbl

[18] Yu. L. Ershov, S. S. Goncharov, Constructive models, Consultants Bureau, New York, 2000 | MR | Zbl

[19] C. C. Chang, H. J. Keisler, Model theory, North-Holland, Amsterdam, 1973 | MR | Zbl

[20] S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations”, Algebra Logic, 54:6 (2016), 428–439 | DOI | MR | Zbl

[21] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of Boolean algebras autostable relative to strong constructivizations”, Siberian Math. J., 56:3 (2015), 393–404 | DOI | MR | Zbl

[22] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of the groups autostable relative to strong constructivizations”, Siberian Math. J., 58:1 (2017), 72–77 | DOI | MR | Zbl

[23] M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations”, Algebra Logic, 55:4 (2016), 306–314 | DOI | MR | Zbl

[24] S. Lang, Algebra, Graduate Texts in Mathematics, 211, Revised third edition, Springer-Verlag, New York, 2002 | MR | Zbl

[25] N. Jacobson, Lectures in abstract algebra, v. III, Theory of fields and Galois theory, D. Van Nostrand Co., Inc., Princeton, N.J.–Toronto, Ont.–London–New York, 1964 | MR | Zbl

[26] R. Miller, V. Ocasio González, “Degree spectra of real closed fields”, Arch. Math. Logic, 58:3–4 (2019), 387–411 | DOI | MR | Zbl

[27] W. Calvert, V. S. Harizanov, J. F. Knight, S. Miller, “Index sets of computable structures”, Algebra Logic, 45:5 (2006), 306–325 | DOI | MR | Zbl

[28] V. A. Ocasio, Computability in the class of real closed fields, Ph.D. Thesis, University of Notre Dame, 2014 | MR

[29] W. Calvert, “The isomorphism problem for classes of computable fields”, Arch. Math. Logic, 43:3 (2004), 327–336 | DOI | MR | Zbl

[30] W. Calvert, D. Cenzer, V. Harizanov, A. Morozov, “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic, 141:1–2 (2006), 61–78 | DOI | MR | Zbl

[31] S. S. Goncharov, “Degrees of autostability relative to strong constructivizations”, Proc. Steklov Inst. Math., 274:1 (2011), 105–115 | DOI | MR | Zbl

[32] N. Bazhenov, “Autostability spectra for decidable structures”, Math. Struct. Comput. Sci., 28:3 (2018), 392–411 | DOI | MR

[33] 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 | DOI | MR | Zbl

[34] S. S. Goncharov, R. Miller, V. Harizanov, “Turing degrees of complete formulas of almost prime models”, Algebra Logic, 58:3 (2019), 282–287 | DOI | Zbl

[35] N. A. Bazhenov, M. Harrison-Trainor, “Constructing decidable graphs from decidable structures”, Algebra Logic, 58:5 (2019), 369–382 | DOI | MR | Zbl

[36] N. Bazhenov, S. Goncharov, A. Melnikov, “Decompositions of decidable abelian groups”, Int. J. Algebra Comput., 30:1 (2020), 49–90 | DOI | MR | Zbl

[37] S. S. Goncharov, J. F. Knight, “Computable structure and non-structure theorems”, Algebra Logic, 41:6 (2002), 351–373 | DOI | MR | Zbl

[38] E. B. Fokina, “Index sets of decidable models”, Siberian Math. J., 48:5 (2007), 939–948 | DOI | MR | Zbl

[39] Yu. L. Ershov, Decidability problems and constructive models, Nauka, M., 1980 (In Russian) | MR

[40] A. G. Melnikov, “Computable abelian groups”, Bull. Symb. Log., 20:3 (2014), 315–356 | DOI | MR | Zbl

[41] W. Szmielew, “Elementary properties of Abelian groups”, Fund. Math., 41 (1955), 203–271 | DOI | MR | Zbl