Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



On the $ n$-back-and-forth types of Boolean algebras

Authors: Kenneth Harris and Antonio Montalbán
Journal: Trans. Amer. Math. Soc. 364 (2012), 827-866
MSC (2010): Primary 03D80; Secondary 03C57
Published electronically: September 1, 2011
MathSciNet review: 2846355
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The objective of this paper is to uncover the structure of the back-and-forth equivalence classes at the finite levels for the class of Boolean algebras. As an application, we obtain bounds on the computational complexity of determining the back-and-forth equivalence classes of a Boolean algebra for finite levels. This result has implications for characterizing the relatively intrinsically $ \Sigma^0_n$ relations of Boolean algebras as existential formulas over a finite set of relations.

References [Enhancements On Off] (What's this?)

  • [AK90] C. J. Ash and J. F. Knight.
    Pairs of recursive structures.
    Ann. Pure Appl. Logic, 46(3):211-234, 1990. MR 1049387 (91b:03061)
  • [AK00] C. J. Ash and J. Knight.
    Computable Structures and the Hyperarithmetical Hierarchy.
    Elsevier Science, 2000. MR 1767842 (2001k:03090)
  • [Ala04] Pavel Alaev.
    Computable homogeneous Boolean algebras and a Metatheorem.
    Algebra and Logic, 43(2):133-158, 2004. MR 2072567 (2005d:03082)
  • [Ash86a] C. J. Ash.
    Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees.
    Trans. Amer. Math. Soc., 298(2):497-514, 1986. MR 860377 (87j:03060)
  • [Ash86b] C. J. Ash.
    Stability of recursive structures in arithmetical degrees.
    Ann. Pure Appl. Logic, 32(2):113-135, 1986. MR 863330 (88j:03021)
  • [Ash87] C. J. Ash.
    Categoricity in hyperarithmetical degrees.
    Ann. Pure Appl. Logic, 34(1):1-14, 1987. MR 887551 (88e:03053)
  • [Bar73] J. Barwise.
    Back and forth through infinitary logic.
    In M. D. Morley, editor, Studies in model theory, pages 5-34. The Mathematical Association of America, Buffalo, N.Y., 1973. MR 0342370 (49:7116)
  • [Bar95] Ewan J. Barker.
    Back and forth relations for reduced abelian $ p$-groups.
    Ann. Pure Appl. Logic, 75(3):223-249, 1995. MR 1355134 (96j:03066)
  • [Cal05] Wesley Calvert.
    The isomorphism problem for computable abelian $ p$-groups of bounded length.
    J. Symbolic Logic, 70(1):331-345, 2005. MR 2119136 (2005j:03033)
  • [CMS06] Barbara F. Csima, Antonio Montalbán, and Richard A. Shore.
    Boolean algebras, Tarski invariants, and index sets.
    Notre Dame Journal of Formal Logic, 47(1):1-23, 2006. MR 2211179 (2006k:03081)
  • [Dic85] M.A. Dickman.
    Larger infinitary languages.
    In J. Barwise and S. Feferman, editors, Larger Infinitary Languages, chapter Chapter IX, pages pp. 316-353. Springer, 1985. MR 819540
  • [DJ94] Rod Downey and Carl G. Jockusch.
    Every low Boolean algebra is isomorphic to a recursive one.
    Proc. Amer. Math. Soc., 122(3):871-880, 1994. MR 1203984 (95a:03044)
  • [FZ80] Jörg Flum and Martin Ziegler.
    Topological model theory, volume 769 of Lecture Notes in Mathematics.
    Springer, Berlin, 1980. MR 560706 (81j:03059)
  • [Hei81] Lutz Heindorf.
    Comparing the expressive power of some languages for Boolean algebras.
    Z. Math. Logik Grundlag. Math., 27(5):419-434, 1981. MR 628302 (82m:03050)
  • [Hei92] Lutz Heindorf.
    Alternative characterizations of finitary and well-founded Boolean algebras.
    Algebra Universalis, 29: 109-135, 1992. MR 1145559 (93b:06027)
  • [HMfin] Kenneth Harris and Antonio Montalbán.
    Boolean algebras of finitary type and the back-and-forth hierarchy.
  • [JS94] Carl G. Jockusch and Robert I. Soare.
    Boolean algebras, Stone spaces, and iterated Turing jumps.
    J. Symbolic Logic, 59(4):1121-1138, 1994. MR 1312300 (95m:03094)
  • [KS00] Julia F. Knight and Michael Stob.
    Computable Boolean algebras.
    J. Symbolic Logic, 65(4):1605-1623, 2000. MR 1812171 (2001m:03086)
  • [Mon89] J.D. Monk, editor.
    Handbook of Boolean algebras, Vol. 1.
    North-Holland, 1989. MR 991565 (90k:06002)
  • [Pal71] E.A. Palyutin.
    Boolean algebras having a categorical weak second-order theory (in Russian).
    Algebra i Logika, 10:523-534, 1971. MR 0304167 (46:3302)
  • [Pie89] R. S. Pierce.
    Countable Boolean algebras.
    In Handbook of Boolean algebras, Vol. 3, pages 775-876. North-Holland, Amsterdam, 1989. MR 991610
  • [Thu95] John J. Thurber.
    Every $ {\rm low}\sb 2$ Boolean algebra has a recursive copy.
    Proc. Amer. Math. Soc., 123(12):3859-3866, 1995. MR 1283564 (96b:03047)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D80, 03C57

Retrieve articles in all journals with MSC (2010): 03D80, 03C57

Additional Information

Kenneth Harris

Antonio Montalbán
Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637-1538

Keywords: Boolean algebra, back-and-forth, invariant
Received by editor(s): October 2, 2007
Received by editor(s) in revised form: January 28, 2008, August 13, 2008, June 9, 2009, June 29, 2009, February 18, 2010, and February 19, 2010
Published electronically: September 1, 2011
Additional Notes: The second author was partially supported by NSF Grants DMS-0600824 and DMS-0901169 and by the Marsden Foundation of New Zealand, via a postdoctoral fellowship
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society