The degree of decidable categoricity of a model with infinite solutions for complete formulas

S. S. Goncharov ; M. I. Marchuk

Algebra i logika, Tome 60 (2021) no. 3, pp. 303-312.

Résumé

We construct a decidable prime model in which the degree of a set of complete formulas is equal to $\mathbf{0}'$, infinitely many tuples of elements comply with every complete formula, and the decidable categoricity spectrum coincides with the set of all $PA$-degrees.

Détail

Keywords: computable model, decidable model, computable categoricity, autostability relative to strong constructivizations, degree of decidable categoricity, decidable categoricity spectrum, $PA$-degree.

Bibliographie

[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] A. T. Nurtazin, “Silnye i slabye konstruktivizatsii i vychislimye semeistva”, Algebra i logika, 13:3 (1974), 311–323 | Zbl

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

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

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

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

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

[8] 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 | Zbl

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

[10] N. A. Bazhenov, “Spektry avtoustoichivosti bulevykh algebr”, Algebra i logika, 53:6 (2014), 764–769

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

[12] 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 | Zbl

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

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

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

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

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

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

[19] 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

[20] M. Harrison-Trainor, “There is no classification of the decidably presentable structures”, J. Math. Log., 18:2 (2018), 1850010, 41 pp. | DOI | Zbl