Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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?)


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
Email: kenneth@kaharris.org

Antonio Montalbán
Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637-1538
Email: antonio@math.uchicago.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-2011-05331-6
PII: S 0002-9947(2011)05331-6
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.