×

Effectively dense Boolean algebras and their applications. (English) Zbl 0958.03023

A computably enumerable Boolean algebra is called effectively dense if for each of its elements \(x\) one can effectively find an \(F(x)\) so that \(x\neq 0\Rightarrow 0<x<F(x)\).
The author proves that for each such Boolean algebra there exists an interpretation of the theory of \(\left<N,+,\times\right>\) in the theory of the lattice of its computably enumerable ideals. As a corollary, he proves this interpretability 1) for the theory lattice of all computably enumerable extensions of the Robinson arithmetic, 2) for the theory of initial principal segments of polynomial time \(r\)-degrees where \(r\) is between \(\leq^p_m\) and \(\leq^p_T\) or equal to one of them, and 3) theories of intervals \([D,A]\) in c.e. sets
This result on Boolean algebras yields a uniform and universal way to prove further results like those ones above.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03D25 Recursively (computably) enumerable sets and degrees
03D15 Complexity of computation (including implicit computational complexity)
03C40 Interpolation, preservation, definability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Ambos-Spies, On the Structure of the Polynomial-time Degrees of Recursive Sets, Habilitationschrift, Universität Dortmund, 1984. · Zbl 0546.03021
[2] Klaus Ambos-Spies, Inhomogeneities in the polynomial-time degrees: the degrees of super sparse sets, Inform. Process. Lett. 22 (1986), no. 3, 113 – 117. · Zbl 0592.03028 · doi:10.1016/0020-0190(86)90054-2
[3] 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. · doi:10.1007/3-540-55210-3_185
[4] José Luis Balcázar, Josep Díaz, and Joaquim Gabarró, Structural complexity. I, EATCS Monographs on Theoretical Computer Science, vol. 11, Springer-Verlag, Berlin, 1988. José Luis Balcázar, Josep Díaz, and Joaquim Gabarró, Structural complexity. II, EATCS Monographs on Theoretical Computer Science, vol. 22, Springer-Verlag, Berlin, 1990.
[5] D. Cenzer and A. Nies, Initial segments of the lattice of \(\Pi^0_1\) classes, to appear in J. Symbolic Logic. · Zbl 1042.03031
[6] C. C. Chang and H. J. Keisler, Model theory, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Studies in Logic and the Foundations of Mathematics, Vol. 73. · Zbl 0276.02032
[7] R. Downey and A. Nies, Undecidability results for low complexity degree structures, to appear in J. Comput. System Sci. · Zbl 0956.68061
[8] Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365 – 374. · Zbl 0222.02048 · doi:10.2307/2270692
[9] Jean-Yves Girard, Proof theory and logical complexity, Studies in Proof Theory. Monographs, vol. 1, Bibliopolis, Naples, 1987. · Zbl 0635.03052
[10] Leo Harrington and André Nies, Coding in the partial order of enumerable sets, Adv. Math. 133 (1998), no. 1, 133 – 162. · Zbl 0890.03016 · doi:10.1006/aima.1997.1687
[11] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. · Zbl 0789.03031
[12] A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1 – 37. · Zbl 0281.02042
[13] Richard E. Ladner, On the structure of polynomial time reducibility, J. Assoc. Comput. Mach. 22 (1975), 155 – 171. · Zbl 0322.68028 · doi:10.1145/321864.321877
[14] 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. · Zbl 0538.03037 · doi:10.1016/0168-0072(83)90031-3
[15] D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205 – 209. · Zbl 0209.01204 · doi:10.2307/2270510
[16] Franco Montagna and Andrea Sorbi, Universal recursion-theoretic properties of r.e. preordered structures, J. Symbolic Logic 50 (1985), no. 2, 397 – 406. · Zbl 0578.03026 · doi:10.2307/2274228
[17] 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. · doi:10.1090/pspum/042/791067
[18] 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). · Zbl 0846.03017 · doi:10.1007/BF00739571
[19] André Nies, Intervals of the lattice of computably enumerable sets and effective Boolean algebras, Bull. London Math. Soc. 29 (1997), no. 6, 683 – 692. · Zbl 0892.03016 · doi:10.1112/S0024609397003548
[20] 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. · Zbl 0715.68040 · doi:10.1016/0022-0000(90)90024-F
[21] 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. · Zbl 0667.03030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.