Boolean algebras, Tarski invariants, and index sets. (English) Zbl 1107.03031

Summary: Tarski defined a way of assigning to each Boolean algebra, \(B\), an invariant \(\text{inv}(B)\in\text{In}\), where In is a set of triples from \(\mathbb{N}\), such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we analyze the complexity of the question “Does \(B\) have invariant \(x\)?” For each \(x\in\text{In}\) we define a complexity class \(\Gamma_x\) that could be either \(\Sigma_n\), \(\Pi_n\), \(\Sigma_n \wedge\Pi_n\), or \(\Pi_{\omega+1}\), depending on \(x\), and we prove that the set of indices for computable Boolean algebras with invariant \(x\) is complete for the class \(\Gamma_x\). Analogs of many of these results for computably enumerable Boolean algebras were proven in earlier works by Selivanov. In a more recent work, he showed that similar methods can be used to obtain the results for computable ones. Our methods are quite different and give new results as well. As the algebras we construct to witness hardness are all dense, we establish new similar results for the complexity of various isomorphism problems for dense Boolean algebras.


03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03D50 Recursive equivalence types of sets and structures, isols
Full Text: DOI


[1] Ash, C. J., and J. Knight, Computable Structures and the Hyperarithmetical Hierarchy , vol. 144 of Studies in Logic and the Foundations of Mathematics , North-Holland Publishing Co., Amsterdam, 2000. · Zbl 0960.03001
[2] Calvert, W., ”The isomorphism problem for computable Abelian \(p\)”-groups of bounded length, The Journal of Symbolic Logic , vol. 70 (2005), pp. 331–45. · Zbl 1099.03031 · doi:10.2178/jsl/1107298523
[3] Downey, R. G., ”On presentations of algebraic structures”, pp. 157–205 in Complexity, Logic, and Recursion Theory , vol. 187 of Lecture Notes in Pure and Applied Mathematics , Dekker, New York, 1997. · Zbl 0915.03039
[4] Ershov, Y. L., ”Decidability of the elementary theory of distributive lattices with relative complements and the theory of filters”, Algebra i Logika , vol. 3 (1964), pp. 17–38. · Zbl 0199.03103
[5] Feiner, L. J., Orderings and Boolean algebras not isomorphic to recursive ones , Ph.D. thesis, MIT, 1967.
[6] Goncharov, S. S., and J. Knight, ”Computable structure and non-structure theorems”, Algebra and Logic , vol. 41 (2002), pp. 351–73. · Zbl 1034.03044
[7] Goncharov, S. S., Countable Boolean Algebras and Decidability , Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997. · Zbl 0912.03019
[8] Hodges, W., Model Theory , vol. 42 of Encyclopedia of Mathematics and its Applications , Cambridge University Press, Cambridge, 1993. · Zbl 0789.03031
[9] Monk, J. D., and R. Bonnet, editors, Handbook of Boolean Algebras. Vols. 1–3, North-Holland Publishing Co., Amsterdam, 1989. · Zbl 0671.06001
[10] Morozov, A. S., ”Strong constructivizability of countable saturated Boolean algebras”, Algebra i Logika , vol. 21 (1982), pp. 193–203. · Zbl 0526.03016 · doi:10.1007/BF01980754
[11] Odintsov, S. P., and V. L. Selivanov, ”The arithmetical hierarchy and ideals of enumerated Boolean algebras”, Sibirskiĭ Matematicheskiĭ Zhurnal , vol. 30 (1989), pp. 140–49. · Zbl 0711.03016 · doi:10.1007/BF00970918
[12] Selivanov, V. L., ”Index sets of classes of hyperhypersimple sets”, Algebra i Logika , vol. 29 (1990), pp. 220–40, 261. · Zbl 0787.03032 · doi:10.1007/BF02001360
[13] Selivanov, V. L., ”The fine hierarchy and definable index sets”, Algebra i Logika , vol. 30 (1991), pp. 705–25, 771. · Zbl 0780.03019 · doi:10.1007/BF02018741
[14] Selivanov, V., ”Positive structures”, pp. 321–50 in Computability and Models , edited by S. B. Cooper and S. S. Goncharov, The University Series in Mathematics, Kluwer/Plenum, New York, 2003.
[15] Shore, R. A., ”Invariants, Boolean algebras and ACA”\(^+\), Transactions of the American Mathematical Society , vol. 358 (2006), pp. 965–87. · Zbl 1111.03012 · doi:10.1090/S0002-9947-05-03802-X
[16] Soare, R. I., Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets , Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. · Zbl 0667.03030
[17] Tarski, A., ”Arithmetical classes and types of Boolean algebras”, Bulletin of the American Mathematical Society , vol. 55 (1949), p. 63. · Zbl 0041.34502
[18] Waszkiewicz, J., ”\(\forall n\)”-theories of Boolean algebras”, Colloquium Mathematicum , vol. 30 (1974), pp. 171–75. · Zbl 0301.02046
[19] White, W., Characterizations for Computable Structures , Ph.D. thesis, Cornell University, 2000.
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.