Every 𝑙𝑜𝑤₂ Boolean algebra has a recursive copy

Thurber, John J.

doi:10.1090/S0002-9939-1995-1283564-6

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

Degrees of Boolean algebras

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