Effectively dense Boolean algebras and their applications

Nies, André

doi:10.1090/S0002-9947-00-02652-0

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