×

On decidable categoricity and almost prime models. (English) Zbl 1446.03069

Summary: The complexity of isomorphisms for computable and decidable structures plays an important role in computable model theory. The first author [Proc. Steklov Inst. Math. 274, 105–115 (2011; Zbl 1294.03025); translation from Tr. Mat. Inst. Steklova 274, 119–129 (2011)] defined the degree of decidable categoricity of a decidable model \(\mathcal{M}\) to be the least Turing degree, if it exists, which is capable of computing isomorphisms between arbitrary decidable copies of \(\mathcal{M} \). If this degree is \(\mathbf{0} \), we say that the structure \(\mathcal{M}\) is decidably categorical. Goncharov established that every computably enumerable degree is the degree of categoricity of a prime model, and Bazhenov showed that there is a prime model with no degree of categoricity. Here we investigate the degrees of categoricity of various prime models with added constants, also called almost prime models. We relate the degree of decidable categoricity of an almost prime model \(\mathcal{M}\) to the Turing degree of the set \(C(\mathcal{M})\) of complete formulas. We also investigate uniform decidable categoricity, characterizing it by primality of \(\mathcal{M}\) and Turing reducibility of \(C(\mathcal{M})\) to the theory of \(\mathcal{M} \).

MSC:

03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D45 Theory of numerations, effectively presented structures

Citations:

Zbl 1294.03025
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Anderson, B.; Csima, B., Degrees that are not degrees of categoricity, Notre Dame J. Form. Log., 57, 389 (2016)
[2] Bazhenov, N. A., Degrees of categoricity for superatomic Boolean algebras, Algebra Log., 52, 179 (2013)
[3] Bazhenov, N. A., \( \Delta_2^0\) -categoricity of Boolean algebras, J. Math. Sci., 203, 444 (2014)
[4] Bazhenov, N. A., Autostability spectra for Boolean algebras, Algebra Log., 53, 502 (2015)
[5] N. Bazhenov, “Prime model with no degree of autostability relative to strong constructivization,” in Evolving Computability, A. Beckmann, V. Mitrana, and M. Soskova, eds., Lecture Notes in Comput. Sci. 9136 (Springer, Berlin, 2015), 117.
[6] Bazhenov, N. A., Degrees of autostability relative to strong constructivizations for Boolean algebras, Algebra Log., 55, 87 (2016)
[7] Bazhenov, N. A., Degrees of autostability for linear orders and linearly ordered Abelian groups, Algebra Log., 55, 257 (2016)
[8] Bazhenov, N. A.; Kalimullin, I. Sh.; Yamaleev, M., Degrees of categoricity and spectral dimension, J. Symbol. Log., 83, 103 (2018)
[9] Bazhenov, N.; Goncharov, S.; Melnikov, A., Decompositions of decidable abelian groups, Internat. J. Algebra Comput., 30, 49 (2020)
[10] N.A. Bazhenov, and M.I. Marchuk, Degrees of categoricity for prime and homogeneous models, in: Sailing Routes in the World of Computation, F. Manea, R.G. Miller, and D. Nowotka, eds., Lecture Notes in Comput. Sci. 10936 (Springer, Berlin, 2018), 40.
[11] Bazhenov, N. A.; Marchuk, M. I., Degrees of autostability relative to strong constructivizations, Siberian Math. J., 59, 565 (2018)
[12] Cenzer, D.; Harizanov, V.; Remmel, J., Computability-theoretic properties of injection structures, Algebra Log., 53, 39 (2014)
[13] Csima, B. F.; Stephenson, J., Finite computable dimension and degrees of categoricity, Ann. Pure Appl. Log., 170, 58 (2019)
[14] Csima, B. F.; Harrison-Trainor, M., Degrees of categoricity on a cone via \(\eta \)-systems, J. Symb. Log., 82, 325 (2017)
[15] Csima, B. F.; Franklin, J. N.Y.; Shore, R. A., Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Form. Log., 54, 215 (2013)
[16] Downey, R. G.; Hirscheldt, D. R.; Khoussainov, B., Uniformity in computable structure theory, Algebra Log., 42, 318 (2003)
[17] Ershov, Y. L.; Goncharov, S. S., Constructive Models (2000), New York: Consultants Bureau, New York
[18] Fokina, E. B.; Goncharov, S. S.; Harizanov, V.; Kudinov, O. V.; Turetsky, D., Index sets for \(n\)-decidable structures categorical relative to \(m\)-decidable presentations, Algebra Log., 54, 336 (2015)
[19] E. Fokina, V. Harizanov, and A. Melnikov, Computable model theory, inTuring’s Legacy, R. Downey, editor (Cambridge University Press, Cambridge, 2014), 124.
[20] Fokina, E.; Harizanov, V.; Turetsky, D., Computability-theoretic categoricity and Scott families, Ann. Pure Appl. Log., 170, 699 (2019)
[21] Fokina, E.; Frolov, A.; Kalimullin, I., Categoricity spectra for rigid structures, Notre Dame J. Form. Log., 57, 45 (2016)
[22] Fokina, E. B.; Kalimullin, I.; Miller, R., Degrees of categoricity of computable structures, Arch. Math. Log., 49, 51 (2010)
[23] J.N.Y. Franklin and R. Miller, Randomness and Computable Categoricity (in preparation).
[24] Frolov, A. N., Effective categoricity of computable linear orderings, Algebra Log., 54, 415 (2015)
[25] Goncharov, S. S.; Miller, R.; Harizanov, V., Turing degrees of complete formulas of almost prime models, Algebra Log., 58, 282 (2019)
[26] Goncharov, S. S., Degrees of autostability relative to strong constructivizations, Proc. Steklov Inst. Math., 274, 105 (2011)
[27] Goncharov, S. S., On the autostability of almost prime models with respect to strong constructivizations, Russ. Math. Surv., 65, 901 (2010)
[28] Goncharov, S. S., Autostability of prime models with respect to strong constructivizations, Algebra Log., 48, 410 (2009)
[29] S.S. Goncharov, “Autostable models and algorithmic dimensions,” in Yu.L. Ershov, S.S. Goncharov, A. Nerode, and J.B. Remmel, eds., Handbook of Recursive Mathematics1 (North-Holland, Amsterdam, 1998), 261.
[30] S.S. Goncharov, “Problem of number of nonautoequivalent constructivizations,” Algebra Log. 19, 401 (1980). (English translation).
[31] Goncharov, S. S.; Bazhenov, N. A.; Marchuk, M. I., The index set of the groups autostable relative to strong constructivizations, Siberian Math. J., 58, 72 (2017)
[32] Goncharov, S. S.; Bazhenov, N. A.; Marchuk, M. I., Index sets of autostable relative to strong constructivizations constructive models for familiar classes, Dokl. Math., 92, 525 (2015)
[33] Goncharov, S. S.; Bazhenov, N. A.; Marchuk, M. I., The index set of Boolean algebras autostable relative to strong constructivizations, Siberian Math. J., 56, 393 (2015)
[34] Goncharov, S. S.; Marchuk, M. I., Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations, Algebra Log., 54, 428 (2016)
[35] Goncharov, S. S.; Marchuk, M. I., Index sets of constructive models of nontrivial signature autostable relative to strong constructivizations, Dokl. Math., 91, 158 (2015)
[36] Goncharov, S. S.; Marchuk, M. I., Index sets of constructive models of bounded signature that are autostable under strong constructivizations, Algebra Log., 54, 108 (2015)
[37] Goncharov, S. S.; Marchuk, M. I., Index sets of constructive models that are autostable under strong constructivizations, J. Math. Sci., 205, 368 (2015)
[38] Goncharov, S. S.; Molokov, A. V.; Romanovskii, N. S., Nilpotent groups of finite algorithmic dimension, Siberian Math. J., 30, 63 (1989)
[39] Kudinov, O., The problem of describing autostable models, Algebra Log., 36, 16 (1997)
[40] Kudinov, O., An autostable \(1 \)-decidable model without a computable Scott family of \(\exists \)-formulas, Algebra Log., 35, 255 (1996)
[41] Marchuk, M. I., Index set of structures with two equivalence relations that are autostable relative to strong constructivizations, Algebra Log., 55, 306 (2016)
[42] Marker, D., Model Theory: An Introduction (2002), New-York: Springer, New-York
[43] R. Miller, “Revisiting uniform computable categoricity: for the sixtieth birthday of Prof. Rod Downey,” in Computability and Complexity, A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, and F. Rosamond, eds., Lecture Notes in Comput. Sci. 10010 (Springer, Berlin, 2017), 254.
[44] Miller, R., \( \mathbf{d} \) -computable categoricity for algebraic fields, J. Symbol. Log., 74, 1325 (2009)
[45] Nurtazin, A. T., Strong and weak constructivizations and computable families, Algebra Log., 13, 177 (1974)
[46] Soare, R. I., Recursively Enumerable Sets and Degrees (1987), New York: Springer-Verlag, New York
[47] Ventsov, Yu. G., The effective choice problem for relations and reducibilities in classes of constructive and positive models, Algebra Log., 31, 63 (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.