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

HTML articles powered by AMS MathViewer

- by Kenneth Harris and Antonio Montalbán PDF
- Trans. Amer. Math. Soc.
**364**(2012), 827-866 Request permission

## 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

- C. J. Ash and J. F. Knight,
*Pairs of recursive structures*, Ann. Pure Appl. Logic**46**(1990), no. 3, 211–234. MR**1049387**, DOI 10.1016/0168-0072(90)90004-L - C. J. Ash and J. Knight,
*Computable structures and the hyperarithmetical hierarchy*, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR**1767842** - P. E. Alaev,
*Computable homogeneous Boolean algebras and a metatheorem*, Algebra Logika**43**(2004), no. 2, 133–158, 256 (Russian, with Russian summary); English transl., Algebra Logic**43**(2004), no. 2, 73–87. MR**2072567**, DOI 10.1023/B:ALLO.0000020844.03135.a6 - C. J. Ash,
*Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees*, Trans. Amer. Math. Soc.**298**(1986), no. 2, 497–514. MR**860377**, DOI 10.1090/S0002-9947-1986-0860377-7 - C. J. Ash,
*Stability of recursive structures in arithmetical degrees*, Ann. Pure Appl. Logic**32**(1986), no. 2, 113–135. MR**863330**, DOI 10.1016/0168-0072(86)90048-5 - C. J. Ash,
*Categoricity in hyperarithmetical degrees*, Ann. Pure Appl. Logic**34**(1987), no. 1, 1–14. MR**887551**, DOI 10.1016/0168-0072(87)90038-8 - Jon Barwise,
*Back and forth through infinitary logic*, Studies in model theory, MAA Studies in Math., Vol. 8, Math. Assoc. Amer., Buffalo, N.Y., 1973, pp. 5–34. MR**0342370** - Ewan J. Barker,
*Back and forth relations for reduced abelian $p$-groups*, Ann. Pure Appl. Logic**75**(1995), no. 3, 223–249. MR**1355134**, DOI 10.1016/0168-0072(94)00045-5 - Wesley Calvert,
*The isomorphism problem for computable abelian $p$-groups of bounded length*, J. Symbolic Logic**70**(2005), no. 1, 331–345. MR**2119136**, DOI 10.2178/jsl/1107298523 - Barbara F. Csima, Antonio Montalbán, and Richard A. Shore,
*Boolean algebras, Tarski invariants, and index sets*, Notre Dame J. Formal Logic**47**(2006), no. 1, 1–23. MR**2211179**, DOI 10.1305/ndjfl/1143468308 - M. A. Dickmann,
*Larger infinitary languages*, Model-theoretic logics, Perspect. Math. Logic, Springer, New York, 1985, pp. 317–363. MR**819540** - Rod Downey and Carl G. Jockusch,
*Every low Boolean algebra is isomorphic to a recursive one*, Proc. Amer. Math. Soc.**122**(1994), no. 3, 871–880. MR**1203984**, DOI 10.1090/S0002-9939-1994-1203984-4 - Jörg Flum and Martin Ziegler,
*Topological model theory*, Lecture Notes in Mathematics, vol. 769, Springer, Berlin, 1980. MR**560706** - Lutz Heindorf,
*Comparing the expressive power of some languages for Boolean algebras*, Z. Math. Logik Grundlagen Math.**27**(1981), no. 5, 419–434. MR**628302**, DOI 10.1002/malq.19810272506 - Lutz Heindorf,
*Alternative characterizations of finitary and well-founded Boolean algebras*, Algebra Universalis**29**(1992), no. 1, 109–135. MR**1145559**, DOI 10.1007/BF01190759 - Kenneth Harris and Antonio Montalbán. Boolean algebras of finitary type and the back-and-forth hierarchy.
- Carl G. Jockusch Jr. and Robert I. Soare,
*Boolean algebras, Stone spaces, and the iterated Turing jump*, J. Symbolic Logic**59**(1994), no. 4, 1121–1138. MR**1312300**, DOI 10.2307/2275695 - Julia F. Knight and Michael Stob,
*Computable Boolean algebras*, J. Symbolic Logic**65**(2000), no. 4, 1605–1623. MR**1812171**, DOI 10.2307/2695066 - Sabine Koppelberg,
*Handbook of Boolean algebras. Vol. 1*, North-Holland Publishing Co., Amsterdam, 1989. Edited by J. Donald Monk and Robert Bonnet. MR**991565** - E. A. Palyutin,
*Boolean algebras that have a categorical theory in weak second order logic*, Algebra i Logika**10**(1971), 523–534 (Russian). MR**0304167** - R. S. Pierce,
*Countable Boolean algebras*, Handbook of Boolean algebras, Vol. 3, North-Holland, Amsterdam, 1989, pp. 775–876. MR**991610** - John J. Thurber,
*Every $\textrm {low}_2$ Boolean algebra has a recursive copy*, Proc. Amer. Math. Soc.**123**(1995), no. 12, 3859–3866. MR**1283564**, DOI 10.1090/S0002-9939-1995-1283564-6

## 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
- 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
- © Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**364**(2012), 827-866 - MSC (2010): Primary 03D80; Secondary 03C57
- DOI: https://doi.org/10.1090/S0002-9947-2011-05331-6
- MathSciNet review: 2846355