Geodesic
Decidable categoricity spectra for almost prime models
Algebra i logika, Tome 62 (2023) no. 4, pp. 441-457.

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

We study decidable categoricity spectra for almost prime models. For any computable collection $\{D_i\}_{i\in\omega}$, where $D_i$ either is a c.e. set or $D_i=PA$, we construct a sequence of almost prime models $\{\mathcal{M}_i\}_{i\in\omega}$ elementarily embedded in each other, in which case for any $i$ there exists a finite collection of constants such that the model $\mathcal{M}_i$ in the expansion by these constants has degree of decidable categoricity $\deg_T(D_i)$, if $D_i$ is a c.e. set, and has no degree of decidable categoricity if $D_i=PA$. The result obtained extends that of S. S. Goncharov, V. Harizanov, and R. Miller [Sib. Adv. Math., 30, No. 3, 200–212 (2020)].
Keywords: computable model, decidable model, computable categoricity, decidable categoricity, autostability relative to strong constructivizations, degree of decidable categoricity, decidable categoricity spectrum, $PA$-degree. 
@article{AL_2023_62_4_a0,
     author = {N. A. Bazhenov and M. I. Marchuk},
     title = {Decidable categoricity spectra for almost prime models},
     journal = {Algebra i logika},
     pages = {441--457},
     publisher = {mathdoc},
     volume = {62},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2023_62_4_a0/}
}
TY  - JOUR
AU  - N. A. Bazhenov
AU  - M. I. Marchuk
TI  - Decidable categoricity spectra for almost prime models
JO  - Algebra i logika
PY  - 2023
SP  - 441
EP  - 457
VL  - 62
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2023_62_4_a0/
LA  - ru
ID  - AL_2023_62_4_a0
ER  - 
%0 Journal Article
%A N. A. Bazhenov
%A M. I. Marchuk
%T Decidable categoricity spectra for almost prime models
%J Algebra i logika
%D 2023
%P 441-457
%V 62
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2023_62_4_a0/
%G ru
%F AL_2023_62_4_a0
N. A. Bazhenov; M. I. Marchuk. Decidable categoricity spectra for almost prime models. Algebra i logika, Tome 62 (2023) no. 4, pp. 441-457. http://geodesic.mathdoc.fr/item/AL_2023_62_4_a0/

[1] S. S. Goncharov, “Stepeni avtoustoichivosti otnositelno silnykh konstruktivizatsii”, Algoritmicheskie voprosy algebry i logiki. K 80-letiyu so dnya rozhd. akad. S. I. Adyana, Tr. MIAN, 274, MAIK,, M., 2011, 119–129

[2] E. B. Fokina, I. Kalimullin, R. Miller, “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67 | DOI | MR | Zbl

[3] B. F. Csima, J. N. Y. Franklin, R. A. Shore, “Degrees of categoricity and the hyperarithmetic hierarchy”, Notre Dame J. Form. Log., 54:2 (2013), 215–231 | DOI | MR | Zbl

[4] R. Miller, A. Shlapentokh, “Computable categoricity for algebraic fields with splitting algorithms”, Trans. Am. Math. Soc., 367:6 (2015), 3955–3980 | DOI | MR | Zbl

[5] E. Fokina, A. Frolov, I. Kalimullin, “Categoricity spectra for rigid structures”, Notre Dame J. Form. Log., 57:1 (2016), 45–57 | DOI | MR | Zbl

[6] N. A. Bazhenov, I. Sh. Kalimullin, M. M. Yamaleev, “O strogikh i nestrogikh stepenyakh kategorichnosti”, Algebra i logika, 55:2 (2016), 257–263 | MR | Zbl

[7] A. I. Maltsev, “Konstruktivnye algebry. I”, Uspekhi matem. n., 16:3(99) (1961), 3–60 | MR | Zbl

[8] S. S. Goncharov, “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19:6 (1980), 621–639 | MR

[9] A. T. Nurtazin, “Silnye i slabye konstruktivizatsii i vychislimye semeistva”, Algebra i logika, 13:3 (1974), 311–323 | MR | Zbl

[10] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei ogranichennoi signatury”, Algebra i logika, 54:2 (2015), 163–192 | MR | Zbl

[11] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei konechnoi signatury i signatury grafov”, Algebra i logika, 54:6 (2015), 663–679

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

[13] B. F. Csima, K. M. Ng, “Every $\Delta^0_2$ degree is a strong degree of categoricity”, J. Math. Log., 22:3 (2022), 2250022, 18 pp. | DOI | MR

[14] S. S. Goncharov, “Ob avtoustoichivosti otnositelno silnykh konstruktivizatsii pochti prostykh modelei”, UMN, 65:5(395) (2010), 107–142 | DOI | MR | Zbl

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

[16] S. S. Goncharov, “Avtoustoichivost prostykh modelei otnositelno silnykh konstruktivizatsii”, Algebra i logika, 48:6 (2009), 729–740 | MR | Zbl

[17] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei netrivialnykh signatur”, Dokl. AN, 461:2 (2015), 140–142 | DOI | Zbl

[18] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii bulevykh algebr”, Sib. matem. zh., 56:3 (2015), 498–512 | MR | Zbl

[19] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii lineinykh poryadkov”, Vestn. NGU. Ser. matem., mekh., inform., 15:3 (2015), 51–60 | Zbl

[20] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei estestvennykh klassov”, Dokl. AN, 464:1 (2015), 12–14 | DOI | Zbl

[21] M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii struktur s dvumya otnosheniyami ekvivalentnosti”, Algebra i logika, 55:4 (2016), 465–477 | MR | Zbl

[22] N. A. Bazhenov, “O stepenyakh avtoustoichivosti otnositelno silnykh konstruktivizatsii dlya bulevykh algebr”, Algebra i logika, 55:2 (2016), 133–155 | MR | Zbl

[23] S. C. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii grupp”, Sib. matem. zh., 58:1 (2017), 95–103 | MR | Zbl

[24] N. A. Bazhenov, M. I. Marchuk, “Stepeni avtoustoichivosti otnositelno silnykh konstruktivizatsii grafov”, Sib. matem. zh., 59:4 (2018), 719–735 | MR | Zbl

[25] S. S. Goncharov, M. I. Marchuk, “O stepeni razreshimoi kategorichnosti modeli s beskonechnymi resheniyami dlya polnykh formul”, Algebra i logika, 60:3 (2021), 303–312 | Zbl

[26] M. I. Marchuk, “Razreshimaya kategorichnost pochti prostykh modelei signatury grafa”, Matem. tr., 24:1 (2021), 117–141

[27] E. B. Fokina, S. S. Goncharov, V. Kharizanova, O. V. Kudinov, D. Turetski, “Indeksnye mnozhestva $n$-razreshimykh struktur, kategorichnykh otnositelno $m$-razreshimykh predstavlenii”, Algebra i logika, 54:4 (2015), 520–528 | MR | Zbl

[28] S. S. Goncharov, V. Harizanov, R. Miller, “On decidable categoricity and almost prime models”, Sib. Adv. Math., 30:3 (2020), 200–212 | DOI | MR | Zbl

[29] G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1977

[30] D. Scott, “Algebras of sets binumerable in complete extensions of arithmetic”, Proc. Sympos. Pure Math., 5 (1962), 117–121 | DOI | MR | Zbl

[31] C. G. Jockusch, jun., R. I. Soare, “$\Pi^0_1$ classes and degrees of theories”, Trans. Am. Math. Soc., 173 (1972), 33–56 \pagebreak | MR | Zbl

[32] S. G. Simpson, “Degrees of unsolvability: A survey of results”, Handbook of mathematical logic, Stud. Logic Found. Math., 90, ed. J. Barwise, North-Holland Publ. Co., Amsterdam etc., 1977, 631–652 | DOI | MR