Degrees of autostability for prime Boolean algebras. (English. Russian original) Zbl 1485.03107
Algebra Logic 57, No. 2, 98-114 (2018); translation from Algebra Logika 57, No. 2, 149-174 (2018).
Summary: 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 \leq\alpha\leq\beta\leq\omega\), there is a decidable model for which \(\mathbf{0}^{(\alpha)}\) is a degree of autostability relative to strong constructivizations, while \(\mathbf{0}^{(\beta)}\) is a degree of autostability. It is proved that for any nonzero ordinal \(\beta \leq\omega\), there is a decidable model for which there is no degree of autostability relative to strong constructivizations, while \(\mathbf{0}^{(\beta)}\) is a degree of autostability.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D45 | Theory of numerations, effectively presented structures |
| 06E05 | Structure theory of Boolean algebras |
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 constructivizationsReferences:
| [1] | Fokina, EB; Kalimullin, I; Miller, R, Degrees of categoricity of computable structures, Arch. Math. Log., 49, 51-67, (2010) · Zbl 1184.03026 · doi:10.1007/s00153-009-0160-4 |
| [2] | Csima, BF; Franklin, JNY; Shore, RA, Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Form. Log., 54, 215-231, (2013) · Zbl 1311.03070 · doi:10.1215/00294527-1960479 |
| [3] | Goncharov, SS, Degrees of autostability relative to strong constructivizations, Trudy MIAN, 274, 119-129, (2011) · Zbl 1294.03025 |
| [4] | Miller, R, d-computable categoricity for algebraic fields, J. Symb. Log., 74, 1325-1351, (2009) · Zbl 1202.03044 · doi:10.2178/jsl/1254748694 |
| [5] | Miller, R; Shlapentokh, A, Computable categoricity for algebraic fields with splitting algorithms, Trans. Am. Math. Soc., 367, 3955-3980, (2015) · Zbl 1375.03052 · doi:10.1090/S0002-9947-2014-06093-5 |
| [6] | Fokina, E; Frolov, A; Kalimullin, I, Categoricity spectra for rigid structures, Notre Dame J. Form. Log., 57, 45-57, (2016) · Zbl 1359.03030 · doi:10.1215/00294527-3322017 |
| [7] | Bazhenov, NA; Kalimullin, IS; Yamaleev, MM, Degrees of categoricity vs. strong degrees of categoricity, Algebra and Logic, 55, 173-177, (2016) · Zbl 1402.03066 · doi:10.1007/s10469-016-9385-6 |
| [8] | Nurtazin, AT, Strong and weak constructivizations and computable families, Algebra and Logic, 13, 177-184, (1974) · Zbl 0305.02061 · doi:10.1007/BF01463352 |
| [9] | N. Bazhenov, “Prime model with no degree of autostability relative to strong constructivizations,” in Lect. Notes Comput. Sci., 9136, Springer-Verlag, Berlin (2015), pp. 117-126. · Zbl 1461.03027 |
| [10] | Bazhenov, NA, Autostability spectra for Boolean algebras, Algebra and Logic, 53, 502-505, (2014) · Zbl 1355.03028 · doi:10.1007/s10469-015-9311-3 |
| [11] | Goncharov, SS; Dzgoev, VD, Autostability of models, Algebra and Logic, 19, 28-36, (1980) · Zbl 0468.03023 · doi:10.1007/BF01669102 |
| [12] | Remmel, JB, Recursive isomorphism types of recursive Boolean algebras, J. Symb. Log., 46, 572-594, (1981) · Zbl 0543.03031 · doi:10.2307/2273757 |
| [13] | N. A. Bazhenov, “\( {\varDelta}_2^0- \) categoricity of Boolean algebras,” Vestnik NGU, Mat., Mekh., Inf., 13, No. 2, 3-14 (2013). · Zbl 1289.03025 |
| [14] | Bazhenov, NA, Degrees of categoricity for superatomic Boolean algebras, Algebra and Logic, 52, 179-187, (2013) · Zbl 1315.03052 · doi:10.1007/s10469-013-9233-x |
| [15] | Pal’chunov, DE; Trofimov, AV; Turko, AI, Autostability relative to strong constructivizations of Boolean algebras with distinguished ideals, Sib. Math. J., 56, 490-498, (2015) · Zbl 1347.03070 · doi:10.1134/S003744661503012X |
| [16] | Bazhenov, NA, Degrees of autostability relative to strong constructivizations for Boolean algebras, Algebra and Logic, 55, 87-102, (2016) · Zbl 1402.03064 · doi:10.1007/s10469-016-9381-x |
| [17] | S. S. Goncharov, Countable Boolean Algebras and Decidability, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1996). · Zbl 0902.03021 |
| [18] | H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401 |
| [19] | C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Logic Found. Math., 144, Elsevier, Amsterdam (2000). · Zbl 0960.03001 |
| [20] | S. S. Goncharov and Yu. L. Ershov, Constructive Models, Siberian School of Algebra and Logic [in Russian], Nauch. Kniga, Novosibirsk (1999). · Zbl 1043.03518 |
| [21] | Tarski, A, Arithmetical classes and types of Boolean algebras, Bull. Am. Math. Soc., 55, 63, (1949) |
| [22] | Ershov, YL, Decidability of the elementary theory of distributive structures with relative complements and of the filter theory, Algebra Logika, 3, 17-38, (1964) · Zbl 0199.03103 |
| [23] | J. B. Remmel, “Recursive Boolean algebras,” in Handbook of Boolean Algebras, Vol. 3, J. D. Monk and R. Bonnet (Eds.), North-Holland, Amsterdam (1989), pp. 1097-1165. |
| [24] | Mead, J, Recursive prime models for Boolean algebras, Coll. Math., 41, 25-33, (1979) · Zbl 0445.03016 · doi:10.4064/cm-41-1-25-33 |
| [25] | Goncharov, SS; Bazhenov, NA; Marchuk, MI, The index set of Boolean algebras autostable relative to strong constructivizations, Sib. Math. J., 56, 394-404, (2015) · Zbl 1328.03036 · doi:10.1134/S0037446615030039 |
| [26] | Ash, C; Knight, J; Manasse, M; Slaman, T, Generic copies of countable structures, Ann. Pure Appl. Log., 42, 195-205, (1989) · Zbl 0678.03012 · doi:10.1016/0168-0072(89)90015-8 |
| [27] | Chisholm, J, Effective model theory vs. recursive model theory, J. Symb. Log., 55, 1168-1191, (1990) · Zbl 0722.03030 · doi:10.2307/2274481 |
| [28] | Ash, CJ; Knight, JF, Pairs of recursive structures, Ann. Pure Appl. Log., 46, 211-234, (1990) · Zbl 0712.03020 · doi:10.1016/0168-0072(90)90004-L |
| [29] | Yu. L. Ershov, Problems of Decidability and Constructive Models [in Russian], Nauka, Moscow (1980). · Zbl 0495.03009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
