### Abstract

The complexity of isomorphisms for computable and decidable structures plays an
important role in computable model theory. Goncharov [26] 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} \).

This is a preview of subscription content, access via your institution.

## REFERENCES

- 1
B. Anderson and B. Csima, “Degrees that are not degrees of categoricity,” Notre Dame J. Form. Log.

**57**, 389 (2016). - 2
N.A. Bazhenov, “Degrees of categoricity for superatomic Boolean algebras,” Algebra Log.

**52**, 179 (2013). - 3
N.A. Bazhenov, “\(\Delta _{2}^{0}\) -categoricity of Boolean algebras,” J. Math. Sci.

**203**, 444 (2014). - 4
N.A. Bazhenov, “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
N.A. Bazhenov, “Degrees of autostability relative to strong constructivizations for Boolean algebras,” Algebra Log.

**55**, 87 (2016). - 7
N.A. Bazhenov, “Degrees of autostability for linear orders and linearly ordered Abelian groups,” Algebra Log.

**55**, 257 (2016). - 8
N.A. Bazhenov, I.Sh. Kalimullin, and M. Yamaleev, “Degrees of categoricity and spectral dimension,” J. Symbol. Log.

**83**, 103 (2018). - 9
N. Bazhenov, S. Goncharov, and A. Melnikov, “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
N.A. Bazhenov, and M.I. Marchuk, “Degrees of autostability relative to strong constructivizations,” Siberian Math. J.

**59**, 565 (2018). - 12
D. Cenzer, V. Harizanov, and J. Remmel, “Computability-theoretic properties of injection structures,” Algebra Log.

**53**, 39 (2014). - 13
B.F. Csima and J. Stephenson, “Finite computable dimension and degrees of categoricity,” Ann. Pure Appl. Log.

**170**, 58 (2019). - 14
B.F. Csima and M. Harrison-Trainor, “Degrees of categoricity on a cone via \(\eta \)-systems,” J. Symb. Log.

**82**, 325 (2017). - 15
B.F. Csima, J.N.Y. Franklin, and R.A. Shore, “Degrees of categoricity and the hyperarithmetic hierarchy,” Notre Dame J. Form. Log.

**54**, 215 (2013). - 16
R.G. Downey, D.R. Hirscheldt, and B. Khoussainov, “Uniformity in computable structure theory,” Algebra Log.

**42**, 318 (2003). - 17
Y.L. Ershov and S.S. Goncharov,

*Constructive Models*(Consultants Bureau, New York, 2000). - 18
E.B. Fokina, S.S. Goncharov, V. Harizanov, O.V. Kudinov, and D. Turetsky, “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, in

*Turing’s Legacy*, R. Downey, editor (Cambridge University Press, Cambridge, 2014), 124. - 20
E. Fokina, V. Harizanov, and D. Turetsky, “Computability-theoretic categoricity and Scott families,” Ann. Pure Appl. Log.

**170**, 699 (2019). - 21
E. Fokina, A. Frolov, and I. Kalimullin, “Categoricity spectra for rigid structures,” Notre Dame J. Form. Log.

**57**, 45 (2016). - 22
E.B. Fokina, I. Kalimullin, and R. Miller, “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
A.N. Frolov, “Effective categoricity of computable linear orderings,” Algebra Log.

**54**, 415 (2015). - 25
S.S. Goncharov, R. Miller, V. Harizanov, “Turing degrees of complete formulas of almost prime models,” Algebra Log.

**58**, 282 (2019). - 26
S.S. Goncharov, “Degrees of autostability relative to strong constructivizations,” Proc. Steklov Inst. Math.

**274**, 105 (2011). - 27
S.S. Goncharov, “On the autostability of almost prime models with respect to strong constructivizations,” Russ. Math. Surv.

**65**, 901 (2010). - 28
S.S. Goncharov, “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 Mathematics***1**(North-Holland, Amsterdam, 1998), 261. - 30
S.S. Goncharov, “Problem of number of nonautoequivalent constructivizations,” Algebra Log.

**19**, 401 (1980). (English translation). - 31
S.S. Goncharov, N.A. Bazhenov, and M.I. Marchuk, “The index set of the groups autostable relative to strong constructivizations,” Siberian Math. J.

**58**, 72 (2017). - 32
S.S. Goncharov, N.A. Bazhenov, and M.I. Marchuk, “Index sets of autostable relative to strong constructivizations constructive models for familiar classes,” Dokl. Math.

**92**, 525 (2015). - 33
S.S. Goncharov, N.A. Bazhenov, and M.I. Marchuk, “The index set of Boolean algebras autostable relative to strong constructivizations,” Siberian Math. J.

**56**, 393 (2015). - 34
S.S. Goncharov and M.I. Marchuk, “Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations,” Algebra Log.

**54**, 428 (2016). - 35
S.S. Goncharov and M.I. Marchuk, “Index sets of constructive models of nontrivial signature autostable relative to strong constructivizations,” Dokl. Math.

**91**, 158 (2015). - 36
S.S. Goncharov and M.I. Marchuk, “Index sets of constructive models of bounded signature that are autostable under strong constructivizations,” Algebra Log.

**54**, 108 (2015). - 37
S.S. Goncharov and M.I. Marchuk, “Index sets of constructive models that are autostable under strong constructivizations,” J. Math. Sci.

**205**, 368 (2015). - 38
S.S. Goncharov, A.V. Molokov, and N.S. Romanovskii, “Nilpotent groups of finite algorithmic dimension,” Siberian Math. J.

**30**, 63 (1989). - 39
O. Kudinov, “The problem of describing autostable models,” Algebra Log.

**36**, 16 (1997). - 40
O. Kudinov, “An autostable \(1 \)-decidable model without a computable Scott family of \( \exists \)-formulas,” Algebra Log.

**35**, 255 (1996). - 41
M.I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations,” Algebra Log.

**55**, 306 (2016). - 42
D. Marker,

*Model Theory: An Introduction*(Springer, New-York, 2002). - 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
R. Miller, “\(\mathbf {d}\) -computable categoricity for algebraic fields,” J. Symbol. Log.

**74**, 1325 (2009). - 45
A.T. Nurtazin, “Strong and weak constructivizations and computable families,” Algebra Log.

**13**, 177 (1974). - 46
R.I. Soare,

*Recursively Enumerable Sets and Degrees*(Springer-Verlag, New York, 1987). - 47
Yu.G. Ventsov, “The effective choice problem for relations and reducibilities in classes of constructive and positive models,” Algebra Log.

**31**, 63 (1992).

## Funding

The authors gratefully acknowledge support by the NSF binational grant DMS-1600625. The work of S.S. Goncharov was partially supported by the Russian Foundation for Basic Research (project No. 20-01-00300). The work of V. Harizanov was partially supported by the Simons Foundation grant 429466. The work of R. Miller was partially supported by Simons Foundation grant 581896.

## Author information

### Affiliations

### Corresponding authors

## About this article

### Cite this article

Goncharov, S.S., Harizanov, V. & Miller, R. On Decidable Categoricity and Almost Prime
Models.
*Sib. Adv. Math.* **30, **200–212 (2020). https://doi.org/10.3103/S1055134420030050

Received:

Revised:

Accepted:

Published:

Issue Date:

### Keywords

- decidable theory
- computable model
- decidable model
- prime model
- almost prime model
- complete formula
- Turing degree
- degree of decidable categoricity
- uniform decidable categoricity