Every Boolean algebra has a recursive copy
Author:
John J. Thurber
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
Full-text PDF
Abstract | References | Similar Articles | Additional Information
Abstract: The degree of a structure is the Turing degree of its open diagram
, coded as a subset of
. 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
has a copy of
degree, then there is a recursive Boolean algebra
which is isomorphic to
. This builds on work of Downey and Jockusch, who proved the analogous result starting with a
Boolean algebra.
- [D-J] R. Downey and C. G. Jockusch, Every low Boolean algebra is isomorphic to a recursive one, Proc. Amer. Math. Soc. 122 (1994), 871-880. MR 1203984 (95a:03044)
- [F] L. Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1974), 365-374. MR 0282805 (44:39)
- [M-B] J. D. Monk and R. Bonnet (eds.), Handbook of Boolean algebras, Vol. 1, Elsevier Science Publishers B.V., Amsterdam, 1989. MR 991565 (90k:06002)
- [R] H. Rogers, Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987. MR 886890 (88b:03059)
- [Re] J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), 572-594. MR 627907 (83a:03042)
- [T1] J. Thurber, Degrees of Boolean algebras, Ph.D. Dissertation, University of Notre Dame, 1994.
- [T2] -, Recursive and r.e. quotient Boolean algebras, Arch. Math. Logic 33 (1994), 121-129. MR 1271431 (95d:03083)
Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03C57, 03D30, 03D45, 03D80
Retrieve articles in all journals with MSC: 03C57, 03D30, 03D45, 03D80
Additional Information
DOI:
https://doi.org/10.1090/S0002-9939-1995-1283564-6
Article copyright:
© Copyright 1995
American Mathematical Society