Degrees of autostability relative to strong constructivizations for Boolean algebras

N. A. Bazhenov

Algebra i logika, Tome 55 (2016) no. 2, pp. 133-155.

Résumé

It is proved that for every computable ordinal $\alpha$, the Turing degree $\mathbf0^{(\alpha)}$ is a degree of autostability of some computable Boolean algebra and is also a degree of autostability relative to strong constructivizations for some decidable Boolean algebra. It is shown that a Harrison Boolean algebra has no degree of autostability relative to strong constructivizations. It is stated that the index set of decidable Boolean algebras having degree of autostability relative to strong constuctivizations is $\Pi^1_1$–complete.

Détail

Keywords: autostability, Boolean algebra, autostability relative to strong constructivizations, degree of autostability, degree of categoricity, index set.

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. Formal Logic, 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] C. J. Ash, “Categoricity in hyperarithmetical degrees”, Ann. Pure Appl. Logic, 34:1 (1987), 1–14 | DOI | MR | Zbl

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

[6] N. A. Bazhenov, “O kategorichnosti bulevykh algebr tipa $B(\omega^\alpha\times\eta)$ v giperarifmeticheskoi ierarkhii”, Vestn. NGU. Ser. matem., mekh., inform., 12:3 (2012), 35–45 | Zbl

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

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

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

[10] S. S. Goncharov, “Konstruktiviziruemost superatomnykh bulevykh algebr”, Algebra i logika, 12:1 (1973), 31–40 | Zbl

[11] J. Harrison, “Recursive pseudo-well orderings”, Trans. Am. Math. Soc., 131:2 (1968), 526–543 | DOI | MR | Zbl

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

[13] P. E. Alaev, “Giperarifmeticheskie bulevy algebry s vydelennym idealom”, Sib. matem. zh., 45:5 (2004), 963–976 | MR | Zbl

[14] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR

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

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

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

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

[19] G. E. Sacks, Higher recursion theory, Perspect. Math. Log., Springer-Verlag, Berlin etc., 1990 | DOI | MR | Zbl

[20] S. S. Goncharov, Dzh. Nait, “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681 | MR | Zbl

[21] E. B. Fokina, “Indeksnye mnozhestva razreshimykh modelei”, Sib. matem. zh., 48:5 (2007), 1167–1179 | MR | Zbl

[22] W. White, “On the complexity of categoricity in computable structures”, Math. Logic Quarterly, 49:6 (2003), 603–614 | DOI | MR | Zbl