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