Available in electronic format
Available in print format
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Effectively dense Boolean algebras and their applications

Author(s): André Nies
Journal: Trans. Amer. Math. Soc. 352 (2000), 4989-5012.
MSC (2000): Primary 03C57, 03D15, 03D25, 03D35
Posted: July 12, 2000
Retrieve article in: PDF
This article is available free of charge

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:

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

DOI: 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
Posted: July 12, 2000
Additional Notes: Partially supported by NSF grant DMS--9500983 and NSF binational grant INT--9602579
Copyright of article: Copyright 2000, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google