Effectively dense Boolean algebras and their applications
HTML articles powered by AMS MathViewer
- by André Nies PDF
- Trans. Amer. Math. Soc. 352 (2000), 4989-5012 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
Additional 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