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