Boolean Algebras, Tarski Invariants, and Index Sets

Notre Dame Journal of Formal Logic 47 (1):1-23 (2006)
  Copy   BIBTEX

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.

Analytics

Added to PP
2010-08-24

Downloads
39 (#356,773)

6 months
2 (#670,035)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Scott sentences for certain groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
Classification from a computable viewpoint.Wesley Calvert & Julia F. Knight - 2006 - Bulletin of Symbolic Logic 12 (2):191-218.
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

References found in this work

Add more references