## Effectively dense Boolean algebras and their applications

HTML articles powered by AMS MathViewer

- by André Nies
- Trans. Amer. Math. Soc.
**352**(2000), 4989-5012 - DOI: https://doi.org/10.1090/S0002-9947-00-02652-0
- Published electronically: July 12, 2000
- PDF | Request permission

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

- K. Ambos-Spies,
*On the Structure of the Polynomial-time Degrees of Recursive Sets,*Habilitationschrift, Universität Dortmund, 1984. - Klaus Ambos-Spies,
*Inhomogeneities in the polynomial-time degrees: the degrees of super sparse sets*, Inform. Process. Lett.**22**(1986), no. 3, 113–117. MR**833174**, DOI 10.1016/0020-0190(86)90054-2 - Klaus Ambos-Spies and André Nies,
*The theory of the polynomial many-one degrees of recursive sets is undecidable*, STACS 92 (Cachan, 1992) Lecture Notes in Comput. Sci., vol. 577, Springer, Berlin, 1992, pp. 209–218. MR**1255600**, DOI 10.1007/3-540-55210-3_{1}85 - J. Horn,
*Über eine hypergeometrische Funktion zweier Veränderlichen*, Monatsh. Math. Phys.**47**(1939), 359–379 (German). MR**91**, DOI 10.1007/BF01695508 - D. Cenzer and A. Nies, Initial segments of the lattice of $\Pi ^0_1$ classes, to appear in J. Symbolic Logic.
- C. C. Chang and H. J. Keisler,
*Model theory*, Studies in Logic and the Foundations of Mathematics, Vol. 73, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. MR**0409165** - R. Downey and A. Nies,
*Undecidability results for low complexity degree structures*, to appear in J. Comput. System Sci. - Lawrence Feiner,
*Hierarchies of Boolean algebras*, J. Symbolic Logic**35**(1970), 365–374. MR**282805**, DOI 10.2307/2270692 - Jean-Yves Girard,
*Proof theory and logical complexity*, Studies in Proof Theory. Monographs, vol. 1, Bibliopolis, Naples, 1987. MR**903244** - Leo Harrington and André Nies,
*Coding in the partial order of enumerable sets*, Adv. Math.**133**(1998), no. 1, 133–162. MR**1492788**, DOI 10.1006/aima.1997.1687 - Wilfrid Hodges,
*Model theory*, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR**1221741**, DOI 10.1017/CBO9780511551574 - A. H. Lachlan,
*On the lattice of recursively enumerable sets*, Trans. Amer. Math. Soc.**130**(1968), 1–37. MR**227009**, DOI 10.1090/S0002-9947-1968-0227009-1 - Richard E. Ladner,
*On the structure of polynomial time reducibility*, J. Assoc. Comput. Mach.**22**(1975), 155–171. MR**464698**, DOI 10.1145/321864.321877 - Wolfgang Maass and Michael Stob,
*The intervals of the lattice of recursively enumerable sets determined by major subsets*, Ann. Pure Appl. Logic**24**(1983), no. 2, 189–212. MR**713299**, DOI 10.1016/0168-0072(83)90031-3 - D. A. Martin and M. B. Pour-El,
*Axiomatizable theories with few axiomatizable extensions*, J. Symbolic Logic**35**(1970), 205–209. MR**280374**, DOI 10.2307/2270510 - Franco Montagna and Andrea Sorbi,
*Universal recursion-theoretic properties of r.e. preordered structures*, J. Symbolic Logic**50**(1985), no. 2, 397–406. MR**793120**, DOI 10.2307/2274228 - A. Nerode and J. Remmel,
*A survey of lattices of r.e. substructures*, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp. 323–375. MR**791067**, DOI 10.1090/pspum/042/791067 - A. Nis,
*The last question on recursively enumerable m-degrees*, Algebra i Logika**33**(1994), no. 5, 550–563, 597 (Russian, with Russian summary); English transl., Algebra and Logic**33**(1994), no. 5, 307–314 (1995). MR**1339586**, DOI 10.1007/BF00739571 - André Nies,
*Intervals of the lattice of computably enumerable sets and effective Boolean algebras*, Bull. London Math. Soc.**29**(1997), no. 6, 683–692. MR**1468055**, DOI 10.1112/S0024609397003548 - Juichi Shinoda and Theodore A. Slaman,
*On the theory of the PTIME degrees of the recursive sets*, J. Comput. System Sci.**41**(1990), no. 3, 321–366. MR**1079470**, DOI 10.1016/0022-0000(90)90024-F - Robert I. Soare,
*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921**, DOI 10.1007/978-3-662-02460-7

## Bibliographic Information

**André Nies**- Affiliation: Department of Mathematics, The University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637
- MR Author ID: 328692
- Email: nies@math.uchicago.edu
- 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
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1776883