Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

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?)


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
Email: nies@math.uchicago.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-00-02652-0
PII: S 0002-9947(00)02652-0
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