Every $\textrm {low}_ 2$ Boolean algebra has a recursive copy
HTML articles powered by AMS MathViewer
- by John J. Thurber PDF
- Proc. Amer. Math. Soc. 123 (1995), 3859-3866 Request permission
Abstract:
The degree of a structure $\mathcal {A}$ is the Turing degree of its open diagram $D(\mathcal {A})$, coded as a subset of $\omega$. Implicit in the definition is a particular presentation of the structure; the degree is not an isomorphism invariant. We prove that if a Boolean algebra $\mathcal {A}$ has a copy of ${\text {low}_2}$ degree, then there is a recursive Boolean algebra $\mathcal {B}$ which is isomorphic to $\mathcal {A}$. This builds on work of Downey and Jockusch, who proved the analogous result starting with a ${\text {low}_1}$ Boolean algebra.References
- 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
- Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365–374. MR 282805, DOI 10.2307/2270692
- Sabine Koppelberg, Handbook of Boolean algebras. Vol. 1, North-Holland Publishing Co., Amsterdam, 1989. Edited by J. Donald Monk and Robert Bonnet. MR 991565
- Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890
- 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 J. Thurber, Degrees of Boolean algebras, Ph.D. Dissertation, University of Notre Dame, 1994.
- John J. Thurber, Recursive and r.e. quotient Boolean algebras, Arch. Math. Logic 33 (1994), no. 2, 121–129. MR 1271431, DOI 10.1007/BF01352933
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 123 (1995), 3859-3866
- MSC: Primary 03C57; Secondary 03D30, 03D45, 03D80
- DOI: https://doi.org/10.1090/S0002-9939-1995-1283564-6
- MathSciNet review: 1283564