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 Free Access

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?)


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.