On the triple jump of the set of atoms of a Boolean algebra

Montalbán, Antonio

doi:10.1090/S0002-9939-08-09248-4

On the triple jump of the set of atoms of a Boolean algebra
HTML articles powered by AMS MathViewer

by Antonio Montalbán PDF

Proc. Amer. Math. Soc. 136 (2008), 2589-2595 Request permission

Abstract:

We prove the following result concerning the degree spectrum of the atom relation on a computable Boolean algebra. Let $\mathcal {C}$ be a computable Boolean algebra with infinitely many atoms and $\mathbf {a}$ be the Turing degree of the atom relation of $\mathcal {C}$. If $\mathbf {d}$ is a c.e. degree such that $\mathbf {a}^{\prime \prime \prime }\leq _T\mathbf {d}^{\prime \prime \prime }$, then there is a computable copy of $\mathcal {C}$ where the atom relation has degree $\mathbf {d}$. In particular, for every $\mathrm {high}_3$ c.e. degree $\mathbf {d}$, any computable Boolean algebra with infinitely many atoms has a computable copy where the atom relation has degree $\mathbf {d}$.

References

C. J. Ash and A. Nerode, Intrinsically recursive relations, Aspects of effective algebra (Clayton, 1979) Upside Down A Book Co., Yarra Glen, Vic., 1981, pp. 26–41. MR 629248
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
Rodney G. Downey and Michael F. Moses, Recursive linear orders with incomplete successivities, Trans. Amer. Math. Soc. 326 (1991), no. 2, 653–668. MR 1005933, DOI 10.1090/S0002-9947-1991-1005933-2
Rod Downey, Every recursive Boolean algebra is isomorphic to one with incomplete atoms, Ann. Pure Appl. Logic 60 (1993), no. 3, 193–206. MR 1216669, DOI 10.1016/0168-0072(93)90075-O
Rodney G. Downey, On presentations of algebraic structures, Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., vol. 187, Dekker, New York, 1997, pp. 157–205. MR 1455136
S. S. Gončarov, Certain properties of the constructivization of Boolean algebras, Sibirsk. Mat. Ž. 16 (1975), 264–278, 420. (loose errata) (Russian). MR 0381957
Julia F. Knight and Michael Stob, Computable Boolean algebras, J. Symbolic Logic 65 (2000), no. 4, 1605–1623. MR 1812171, DOI 10.2307/2695066
J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), no. 3, 572–594. MR 627907, DOI 10.2307/2273757
Jeffrey B. Remmel, Recursive Boolean algebras with recursive atoms, J. Symbolic Logic 46 (1981), no. 3, 595–616. MR 627908, DOI 10.2307/2273758
J. B. Remmel, Recursive Boolean algebras, Handbook of Boolean algebras, Vol. 3, North-Holland, Amsterdam, 1989, pp. 1097–1165. MR 991614
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