zbMATH — the first resource for mathematics

The index set of Boolean algebras autostable relative to strong constructivizations. (English. Russian original) Zbl 1328.03036
Sib. Math. J. 56, No. 3, 393-404 (2015); translation from Sib. Mat. Zh. 56, No. 3, 498-512 (2015).
Summary: We obtain exact estimates for the algorithmic complexity for the classes of strongly constructivizable computable models autostable relative to strong constructivizations and belonging to the following natural classes: Boolean algebras, distributive lattices, rings, commutative semigroups, and partial orders.

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03C15 Model theory of denumerable and separable structures
06E05 Structure theory of Boolean algebras
Full Text: DOI
[1] Goncharov, S S; Knight, J F, Computable structure and non-structure theorems, Algebra and Logic, 41, 351-373, (2002) · Zbl 1034.03044
[2] Ershov Yu. L. and Goncharov S. S., Constructive Models, Ser. Siberian School of Algebra and Logic, Kluwer Academic/Plenum Publishers, New York, etc. (2000).
[3] Ash C. J. and Knight J. F., Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, Amsterdam (2000) (Stud. Logic Found. Math.; V. 144). · Zbl 0960.03001
[4] Nurtazin A. T., Computable Classes and Algebraic Criteria of Autostability [in Russian], Dis. Kand. Fiz.-Mat. Nauk, Inst. Mat. Mekh., Alma-Ata (1974).
[5] Goncharov S. S. and Marchuk M. I., “Index sets of constructive models of bounded signature which are autostable relative to strong constructivizations,” Algebra and Logic (to be published). · Zbl 1347.03069
[6] Goncharov S. S. and Marchuk M. I., “Index sets of constructive models of finite signature and graph signature which are autostable relative to strong constructivizations,” Algebra and Logic (to be published). · Zbl 1347.03069
[7] Goncharov, S S; Marchuk, M I, Index sets of autostable relative to strong constructivizations constructive models, Vestnik NGU. Ser. Mat. Mekh. Inform., 13, 43-67, (2013) · Zbl 1349.03037
[8] Marker, D, Non σ_{n} axiomatizable almost strongly minimal theories, J. Symbolic Logic, 54, 921-927, (1989) · Zbl 0698.03021
[9] Goncharov, S S; Khoussainov, B, Complexity of theories of computable categorical models, Algebra and Logic, 43, 365-373, (2004) · Zbl 1097.03027
[10] Ash, C J; Knight, J F, Pairs of recursive structures, Ann. Pure Appl. Logic, 46, 211-234, (1990) · Zbl 0712.03020
[11] Goncharov S. S., Countable Boolean Algebras and Decidability [in Russian], Nauchnaya Kniga, Novosibirsk (1996). · Zbl 0902.03021
[12] Chang C. C. and Keisler H. J., Model Theory, North-Holland, Amsterdam and London (1973). · Zbl 0276.02032
[13] Nurtazin, A T, Strong and weak constructivization and computable families, Algebra and Logic, 13, 177-184, (1974) · Zbl 0305.02061
[14] Rogers H., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Comp., New York, St. Louis, San Francisco, Toronto, London, and Sydney (1972). · Zbl 0256.02015
[15] Tarski, A, Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc., 55, 63, (1949)
[16] Ershov, Yu L, Decidability of the elementary theory of distributive structures with relative complements and the theory of filters, Algebra i Logika, 3, 17-38, (1964) · Zbl 0199.03103
[17] Remmel, J B, Recursive Boolean algebras, 1097-1165, (1989), Amsterdam, etc.
[18] Mead, J, Recursive prime models for Boolean algebras, Colloq. Math., 41, 25-33, (1979) · Zbl 0445.03016
[19] Pal’chunov, D E; Trofimov, A V; Turko, A I, Autostability relative to strong constructivizations of Boolean algebras with distinguished ideals, Siberian Math. J., 56, 490-498, (2015) · Zbl 1347.03070
[20] Csima, B F; Montalbán, A; Shore, R A, Boolean algebras, Tarski invariants, and index sets, Notre Dame J. Formal Logic, 47, 1-23, (2006) · Zbl 1107.03031
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.