|
On the triple jump of the set of atoms of a Boolean algebra
Author:
Antonio Montalbán
Journal:
Proc. Amer. Math. Soc. 136 (2008), 2589-2595
MSC (2000):
Primary 03D80
Posted:
March 11, 2008
MathSciNet review:
2390531
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We prove the following result concerning the degree spectrum of the atom relation on a computable Boolean algebra. Let be a computable Boolean algebra with infinitely many atoms and be the Turing degree of the atom relation of . If is a c.e. degree such that , then there is a computable copy of where the atom relation has degree . In particular, for every c.e. degree , any computable Boolean algebra with infinitely many atoms has a computable copy where the atom relation has degree .
- [AN81]
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
(83a:03039)
- [DJ94]
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
(95a:03044), http://dx.doi.org/10.1090/S0002-9939-1994-1203984-4
- [DM91]
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
(91k:03115), http://dx.doi.org/10.1090/S0002-9947-1991-1005933-2
- [Dow93]
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
(94c:03059), http://dx.doi.org/10.1016/0168-0072(93)90075-O
- [Dow97]
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
(98k:03099)
- [Gon75]
S.
S. Gončarov, Certain properties of the constructivization of
Boolean algebras, Sibirsk. Mat. Ž. 16 (1975),
264–278, 420. (loose errata) (Russian). MR 0381957
(52 #2846)
- [KS00]
Julia
F. Knight and Michael
Stob, Computable Boolean algebras, J. Symbolic Logic
65 (2000), no. 4, 1605–1623. MR 1812171
(2001m:03086), http://dx.doi.org/10.2307/2695066
- [Rem81a]
J.
B. Remmel, Recursive isomorphism types of recursive Boolean
algebras, J. Symbolic Logic 46 (1981), no. 3,
572–594. MR
627907 (83a:03042), http://dx.doi.org/10.2307/2273757
- [Rem81b]
Jeffrey
B. Remmel, Recursive Boolean algebras with recursive atoms, J.
Symbolic Logic 46 (1981), no. 3, 595–616. MR 627908
(82j:03055), http://dx.doi.org/10.2307/2273758
- [Rem89]
J.
B. Remmel, Recursive Boolean algebras, Handbook of Boolean
algebras, Vol. 3, North-Holland, Amsterdam, 1989,
pp. 1097–1165. MR
991614
- [Thu95]
John
J. Thurber, Every
𝑙𝑜𝑤₂ Boolean algebra has a recursive
copy, Proc. Amer. Math. Soc.
123 (1995), no. 12, 3859–3866. MR 1283564
(96b:03047), http://dx.doi.org/10.1090/S0002-9939-1995-1283564-6
- [AN81]
- C. J. Ash and A. Nerode.
Intrinsically recursive relations. In Aspects of effective algebra (Clayton, 1979), pages 26-41. Upside Down A Book Co. Yarra Glen, Vic., 1981. MR 629248 (83a:03039)
- [DJ94]
- Rod Downey and Carl G. Jockusch.
Every low Boolean algebra is isomorphic to a recursive one. Proc. Amer. Math. Soc., 122(3):871-880, 1994. MR 1203984 (95a:03044)
- [DM91]
- Rodney G. Downey and Michael F. Moses.
Recursive linear orders with incomplete successivities. Trans. Amer. Math. Soc., 326(2):653-668, 1991. MR 1005933 (91k:03115)
- [Dow93]
- Rod Downey.
Every recursive Boolean algebra is isomorphic to one with incomplete atoms. Ann. Pure Appl. Logic, 60(3):193-206, 1993. MR 1216669 (94c:03059)
- [Dow97]
- Rodney G. Downey.
On presentations of algebraic structures. In Complexity, logic, and recursion theory, volume 187 of Lecture Notes in Pure and Appl. Math., pages 157-205. Dekker, New York, 1997. MR 1455136 (98k:03099)
- [Gon75]
- S. S. Goncharov.
Certain properties of the constructivization of Boolean algebras. Sibirskii Matematicheskii Zhurnal, 16(2):264-278, 1975. MR 0381957 (52:2846)
- [KS00]
- Julia F. Knight and Michael Stob.
Computable Boolean algebras. J. Symbolic Logic, 65(4):1605-1623, 2000. MR 1812171 (2001m:03086)
- [Rem81a]
- J. B. Remmel.
Recursive isomorphism types of recursive Boolean algebras. J. Symbolic Logic, 46(3):572-594, 1981. MR 627907 (83a:03042)
- [Rem81b]
- Jeffrey B. Remmel.
Recursive Boolean algebras with recursive atoms. J. Symbolic Logic, 46(3):595-616, 1981. MR 627908 (82j:03055)
- [Rem89]
- J. B. Remmel.
Recursive Boolean algebras. In Handbook of Boolean algebras, Vol. 3, pages 1097-1165. North-Holland, Amsterdam, 1989. MR 991614
- [Thu95]
- John J. Thurber.
Every Boolean algebra has a recursive copy. Proc. Amer. Math. Soc., 123(12):3859-3866, 1995. MR 1283564 (96b:03047)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2000):
03D80
Retrieve articles in all journals
with MSC (2000):
03D80
Additional Information
Antonio Montalbán
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Email:
antonio@mcs.vuw.ac.nz
DOI:
http://dx.doi.org/10.1090/S0002-9939-08-09248-4
PII:
S 0002-9939(08)09248-4
Keywords:
Boolean algebra,
atom,
relation,
degree spectrum
Received by editor(s):
December 8, 2006
Received by editor(s) in revised form:
April 12, 2007, April 22, 2007, and May 31, 2007
Posted:
March 11, 2008
Additional Notes:
This research was partially supported by NSF Grant DMS-0600824 and by the Marsden Foundation of New Zealand, via a postdoctoral fellowship.
Communicated by:
Julia Knight
Article copyright:
© Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
|