Boolean algebra approximations
HTML articles powered by AMS MathViewer
- by Kenneth Harris and Antonio Montalbán PDF
- Trans. Amer. Math. Soc. 366 (2014), 5223-5256 Request permission
Abstract:
Knight and Stob proved that every low$_4$ Boolean algebra is $0^{(6)}$-isomorphic to a computable one. Furthermore, for $n=1,2,3,4$, every low$_n$ Boolean algebra is $0^{(n+2)}$-isomorphic to a computable one. We show that this is not true for $n=5$: there is a low$_5$ Boolean algebra that is not $0^{(7)}$-isomorphic to any computable Boolean algebra.
It is worth remarking that, because of the machinery developed, the proof uses at most a $0^{\prime \prime }$-priority argument. The technique used to construct this Boolean algebra is new and might be useful in other applications, such as to solve the low$_n$ Boolean algebra problem either positively or negatively.
References
- 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
- 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
- Kenneth Harris and Antonio Montalbán, On the $n$-back-and-forth types of Boolean algebras, Trans. Amer. Math. Soc. 364 (2012), no. 2, 827–866. MR 2846355, DOI 10.1090/S0002-9947-2011-05331-6
- Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
- Julia F. Knight and Michael Stob, Computable Boolean algebras, J. Symbolic Logic 65 (2000), no. 4, 1605–1623. MR 1812171, DOI 10.2307/2695066
- Antonio Montalbán, Notes on the jump of a structure, Mathematical theory and computational practice, Lecture Notes in Comput. Sci., vol. 5635, Springer, Berlin, 2009, pp. 372–378. MR 2545911, DOI 10.1007/978-3-642-03073-4_{3}8
- Sabine Koppelberg, Handbook of Boolean algebras. Vol. 1, North-Holland Publishing Co., Amsterdam, 1989. Edited by J. Donald Monk and Robert Bonnet. MR 991565
- 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
- Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109
- Email: kaharri@umich.edu
- Antonio Montalbán
- Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637
- Email: antonio@math.uchicago.edu
- Received by editor(s): February 27, 2010
- Received by editor(s) in revised form: September 5, 2012
- Published electronically: June 3, 2014
- Additional Notes: The second author was partially supported by NSF grant DMS-0901169, and by the AMS centennial fellowship
- © Copyright 2014 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 366 (2014), 5223-5256
- MSC (2010): Primary 03D45, 03G05
- DOI: https://doi.org/10.1090/S0002-9947-2014-05950-3
- MathSciNet review: 3240923