Degrees of autostability for prime Boolean algebras

N. A. Bazhenov ; M. I. Marchuk

Algebra i logika, Tome 57 (2018) no. 2, pp. 149-174.

Résumé

We look at the concept of algorithmic complexity of isomorphisms between computable copies of Boolean algebras. Degrees of autostability are found for all prime Boolean algebras. It is shown that for any ordinals $\alpha$ and $\beta$ with the condition $0\le\alpha\le\beta\le\omega$ there is a decidable model for which $\mathbf0^{(\alpha)}$ is a degree of autostability relative to strong constructivizations, while $\mathbf0^{(\beta)}$ is a degree of autostability. It is proved that for any nonzero ordinal $\beta\le\omega$, there is a decidable model for which there is no degree of autostability relative to strong constructivizations, while $\mathbf0^{(\beta)}$ is a degree of autostability.

Détail

Keywords: autostability spectrum, degree of autostability, Boolean algebra, autostability, prime model, computable model, computable categoricity, categoricity spectrum, degree of categoricity, decidable model, autostability relative to strong constructivizations.

Bibliographie

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

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

[3] 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 | MR

[4] R. Miller, “$d$-computable categoricity for algebraic fields” (4), J. Symb. Log., 74 (2009), 1325–1351 | DOI | MR | Zbl

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

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

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

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

[9] N. Bazhenov, “Prime model with no degree of autostability relative to strong constructivizations”, Evolving computability, Proc. 11th conf. comput. Europe CiE 2015 (Bucharest, Romania, June 29 – July 3, 2015), Lect. Notes Comput. Sci., 9136, eds. A. Beckmann et al., Springer-Verlag, Berlin, 2015, 117–126 | DOI | MR | Zbl

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

[11] S. S. Goncharov, V. D. Dzgoev, “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR | Zbl

[12] J. B. Remmel, “Recursive isomorphism types of recursive Boolean algebras”, J. Symb. Log., 46:3 (1981), 572–594 | DOI | MR | Zbl

[13] N. A. Bazhenov, “O $\Delta^0_2$-kategorichnosti bulevykh algebr”, Vestn. NGU. Ser. matem., mekh., inform., 13:2 (2013), 3–14 | Zbl

[14] N. A. Bazhenov, “Stepeni kategorichnosti superatomnykh bulevykh algebr”, Algebra i logika, 52:3 (2013), 271–283 | MR | Zbl

[15] D. E. Palchunov, A. V. Trofimov, A. I. Turko, “Avtoustoichivost bulevykh algebr s vydelennymi idealami otnositelno silnykh konstruktivizatsii”, Sib. matem. zh., 56:3 (2015), 617–628 | MR | Zbl

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

[17] S. S. Goncharov, Schetnye bulevy algebry i razreshimost, Sibirskaya shkola algebry i logiki, Nauchnaya kniga (NII MIOO NGU), Novosibirsk, 1996 | MR

[18] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl

[19] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Sci. B. V., Amsterdam etc., 2000 | MR | Zbl

[20] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999

[21] A. Tarski, “Arithmetical classes and types of Boolean algebras”, Bull. Am. Math. Soc., 55 (1949), 63

[22] Yu. L. Ershov, “Razreshimost elementarnoi teorii distributivnykh struktur s otnositelnymi dopolneniyami i teorii filtrov”, Algebra i logika, 3:3 (1964), 17–38 | Zbl

[23] J. B. Remmel, “Recursive Boolean algebras”, Handbook of Boolean algebras, v. 3, eds. J. D. Monk, R. Bonnet, North-Holland, Amsterdam etc., 1989 | MR | Zbl

[24] J. Mead, “Recursive prime models for Boolean algebras”, Colloq. Math., 41 (1979), 25–33 | DOI | MR | Zbl

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

[26] C. Ash, J. Knight, M. Manasse, T. Slaman, “Generic copies of countable structures”, Ann. Pure Appl. Logic, 42:3 (1989), 195–205 | DOI | MR | Zbl

[27] J. Chisholm, “Effective model theory vs. recursive model theory”, J. Symb. Log., 55:3 (1990), 1168–1191 | DOI | MR | Zbl

[28] C. J. Ash, J. F. Knight, “Pairs of recursive structures”, Ann. Pure Appl. Logic, 46:3 (1990), 211–234 | DOI | MR | Zbl

[29] Yu. L. Ershov, Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980