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

DOI:
https://doi.org/10.1090/S0002-9947-00-02652-0

Published electronically:
July 12, 2000

MathSciNet review:
1776883

Full-text PDF

Abstract | References | Similar Articles | Additional Information

A computably enumerable Boolean algebra is *effectively dense* if for each we can effectively determine an such that implies . 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 (the lattice of computably enumerable sets under inclusion) which are not Boolean algebras. We derive a similar result for theories of certain initial intervals of subrecursive degree structures, where is the degree of a set of relatively small complexity, for instance a set in exponential time.

**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 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 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**

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:
https://doi.org/10.1090/S0002-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