Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Effectively dense Boolean algebras and their applications

Author: André Nies
Journal: Trans. Amer. Math. Soc. 352 (2000), 4989-5012
MSC (2000): Primary 03C57, 03D15, 03D25, 03D35
Published electronically: July 12, 2000
MathSciNet review: 1776883
Full-text PDF

Abstract | References | Similar Articles | Additional Information


A computably enumerable Boolean algebra ${\mathcal{B}}$ is effectively dense if for each $x \in{\mathcal{B}}$ we can effectively determine an $F(x)\le x$ such that $x \neq 0$ implies $0 < F(x) < x$. We give an interpretation of true arithmetic in the theory of the lattice of computably enumerable ideals of such a Boolean algebra. As an application, we also obtain an interpretation of true arithmetic in all theories of intervals of ${\mathcal{E}}$ (the lattice of computably enumerable sets under inclusion) which are not Boolean algebras. We derive a similar result for theories of certain initial intervals $[{\mathbf{0}},{\mathbf{a}}]$ of subrecursive degree structures, where ${\mathbf{a}}$is the degree of a set of relatively small complexity, for instance a set in exponential time.

References [Enhancements On Off] (What's this?)

  • 1. K. Ambos-Spies, On the Structure of the Polynomial-time Degrees of Recursive Sets, Habilitationschrift, Universität Dortmund, 1984.
  • 2. K. Ambos-Spies, ``Inhomogeneities in the Polynomial-time Degrees: the Degrees of Super-Sparse Sets,'' Information Processing Letters, 22 (1986), 113-117. MR 88e:68036
  • 3. K. Ambos-Spies and A. Nies ``The theory of the polynomial many-one degrees of recursive sets is undecidable,'' STACS 92, Lecture Notes in Computer Science 577 (1992) 209-218. MR 94m:03068
  • 4. J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, Volumes 1 and 2, Springer Verlag (1987,1989). MR 91f:68058; MR 91k:68057
  • 5. D. Cenzer and A. Nies, Initial segments of the lattice of $\Pi^0_1$ classes, to appear in J. Symbolic Logic.
  • 6. C.C. Chang and H.J. Keisler, Model Theory, North Holland, 1973. MR 53:12927
  • 7. R. Downey and A. Nies, Undecidability results for low complexity degree structures, to appear in J. Comput. System Sci.
  • 8. L. Feiner, Hierarchies of Boolean Algebras, J. Symbolic Logic 35 (1970), 365-374. MR 44:39
  • 9. J.-Y. Girard, Proof theory and logical complexity, Bibliopolis, Naples, 1987. MR 89a:03113
  • 10. L. Harrington and A. Nies, Coding in the lattice of enumerable sets, Adv. in Math. 133 (1998), 133-162. MR 99c:03063
  • 11. W. Hodges, Model Theory, Encyclopedia of Mathematics and its Applications 42, Cambridge University Press, 1993. MR 94e:03002
  • 12. A. Lachlan, On the Lattice of Recursively Enumerable Sets, Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 37:2594
  • 13. R. Ladner, On the Structure of Polynomial Time Reducibility, J. Assoc. Comput. Mach, 22 (1975) 155-171. MR 57:4623
  • 14. W. Maass and M. Stob, The Intervals of the Lattice of Recursively Enumerable Sets Determined By Major Subsets, Ann. Pure Appl. Logic 24 (1983), 189-212. MR 85j:03066
  • 15. D. Martin and M. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205-209. MR 43:6094
  • 16. F. Montagna and A. Sorbi, Universal recursion theoretic properties of r.e. preordered structures, J. Symbolic Logic 50 (1985), 397-406. MR 87k:03046
  • 17. A. Nerode and J. B. Remmel, A Survey of Lattices of Recursively Enumerable Substructures, Recursion Theory, Proceedings of Symposia in Pure Mathematics 42 (1985), 322-375. MR 87b:03097
  • 18. A. Nies, The last question on recursively enumerable many-one degrees, Algebra i Logika 33, (1994), 550-563; English transl., Algebra and Logic 33 (1994), 307-314. MR 96g:03073
  • 19. A. Nies, ``Intervals of the lattice of computably enumerable sets and effective Boolean algebras,'' Bull. London Math. Soc. 29 (1997), 683-92. MR 98j:03057
  • 20. J. Shinoda and T. Slaman, ``On the Theory of $\ensuremath{\mathrm{P{\scriptstyle TIME}}} $ Degrees of Recursive Sets,'' J. Comput. System Sci. 41 (1990) 321-366. MR 92b:03049
  • 21. R. Soare, Recursively Enumerable Sets and Degrees, Springer Verlag, Heidelberg, 1987. MR 88m:03003

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03C57, 03D15, 03D25, 03D35

Retrieve articles in all journals with MSC (2000): 03C57, 03D15, 03D25, 03D35

Additional Information

André Nies
Affiliation: Department of Mathematics, The University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637

Keywords: C.e. ideals, true arithmetic, subrecursive reducibilities, intervals of $\mathcal{E}$
Received by editor(s): August 29, 1997
Received by editor(s) in revised form: April 23, 1998
Published electronically: July 12, 2000
Additional Notes: Partially supported by NSF grant DMS–9500983 and NSF binational grant INT–9602579
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society