Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, 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 we define a complexity class Γx that could be either Σⁿ, Πⁿ, Σⁿ ∧ Πⁿ, or Πω+1 depending on x, and we prove that the set of indices for computable Boolean algebras with invariant x is complete for the class Γ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
Keywords Boolean algebras   computability   index sets   Tarski invariants
Categories (categorize this paper)
DOI 10.1305/ndjfl/1143468308
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,194
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

Classification From a Computable Viewpoint.Wesley Calvert & Julia F. Knight - 2006 - Bulletin of Symbolic Logic 12 (2):191-218.
Scott Sentences for Certain Groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
Index Sets for Some Classes of Structures.Ekaterina B. Fokina - 2009 - Annals of Pure and Applied Logic 157 (2-3):139-147.

Add more citations

Similar books and articles

Definable Sets in Boolean Ordered o-Minimal Structures. II.Roman Wencel - 2003 - Journal of Symbolic Logic 68 (1):35-51.
B-Varieties with Normal Free Algebras.Bronis?aw Tembrowski - 1989 - Studia Logica 48 (4):555 - 564.
Elementary Embedding Between Countable Boolean Algebras.Robert Bonnet & Matatyahu Rubin - 1991 - Journal of Symbolic Logic 56 (4):1212-1229.
Applications of PCF Theory.Saharon Shelah - 2000 - Journal of Symbolic Logic 65 (4):1624-1674.


Added to PP index

Total views
36 ( #299,674 of 2,448,320 )

Recent downloads (6 months)
1 ( #450,727 of 2,448,320 )

How can I increase my downloads?


My notes