Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T10:02:14.976Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices

Published online by Cambridge University Press:  12 March 2014

Klaus Ambos-Spies ,
Peter A. Fejer ,
Steffen Lempp  and
Manuel Lerman
Klaus Ambos-Spies
Affiliation:
Universität Heidelberg, Mathematisches Institut, Im Neuenheimer Feld 294, D-69120 Heidelberg, Germany, E-mail: [email protected]
Peter A. Fejer
Affiliation:
Department of Mathematics, and Computer Science, University of Massachusetts at Boston, Boston, MA 02125-3393, [email protected]
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA, E-mail: [email protected]
Manuel Lerman
Affiliation:
Department of Mathematics, University of Connecticut, U-9, Storrs, CT 06269-3009, [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are disjoint.

We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21].

Keywords

Recursively enumerable weak truth-table degreerecursive polynomial many-one degreedecidable fragment
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 3 , September 1996 , pp. 880 - 905
Copyright
Copyright © Association for Symbolic Logic 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ambos-Spies, Klaus, Cupping andnoncapping in the r.e. weak truth table and Turing degrees, Archiv für Mathematische Logik und Grundlagforschung, vol. 25 (1985), pp. 109–126.CrossRefGoogle Scholar
[2]Ambos-Spies, Klaus, Sublattices of the polynomial time degrees, Information and Control, vol. 65 (1985), pp. 63–84.CrossRefGoogle Scholar
[3]Ambos-Spies, Klaus, Polynomial time degrees of NP sets, Trends in theoretical computer science (Rockville, MD) (Börger, Egon, editor), Computer Science Press, 1987, pp. 95–142.Google Scholar
[4]Ambos-Spies, Klaus, Homer, Steven, and Soare, Robert I., Minimal pairs and complete problems, Theoretical Computer Science, vol. 132 (1994), pp. 229–241.CrossRefGoogle Scholar
[5]Ambos-Spies, Klaus, Jockusch, Carl G. Jr., Shore, Richard A., and Soare, Robert I., An algebraic decomposition of the recursively enumerable degrees and the coincidence of several classes with the promptly simple degrees, Transactions of the American Mathematical Society, vol. 281 (1984), pp. 109–128.CrossRefGoogle Scholar
[6]Ambos-Spies, Klaus, Nies, André, and Shore, Richard A., The theory of the recursively enumerable weak truth-table degrees is undecidable, this Journal, vol. 57 (1992), pp. 864–874.Google Scholar
[7]Balcazar, Jose Luis, Diaz, Josep, and Gabarro, Joaquim, Structural complexity, volume 1, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin, 1988.CrossRefGoogle Scholar
[8]Birkhoff, Garrett, Lattice theory, Colloquium Publications, American Mathematical Society, New York, 1948.Google Scholar
[9]Degtev, A. N., Some results on upper semilattices and m-degrees, Algebra i Logika, vol. 18 (1979), pp. 665–679, 754, in Russian; English translation in Algebra and Logic, vol. 18 (1979), pp. 420–430.Google Scholar
[10]Ershov, Y. L., The uppersemilattice of numerations of a finite set, Algebrai Logika, vol. 14 (1975), pp. 258–284, 368, in Russian; English translation in Algebra and Logic, vol. 14 (1975), pp. 159–175.Google Scholar
[11]Fejer, Peter A., Branching degrees above low degrees, Transactions of the American Mathematical Society, vol. 273 (1982), pp. 157–180.CrossRefGoogle Scholar
[12]Fejer, Peter A. and Shore, Richard A., Embeddings and extensions of embeddings in the r.e. tt and wtt-degrees, Recursion theory week, Proceedings of a conference held in Oberwolfach, West Germany, April 15–21, 1984 (Ebbinghaus, H. D., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, no. 1141, Springer-Verlag, 1985, pp. 121–140.CrossRefGoogle Scholar
[13]Grätzer, George, Lattice theory: First concepts and distributive lattices, A Series of Books in Mathematics, W. H. Freeman, San Francisco, 1971.Google Scholar
[14]Hopcroft, John E. and Ullman, Jeffrey D., Introduction to automata theory, languages, and computation, Addison-Wesley, Reading, MA, 1979.Google Scholar
[15]Jockusch, Carl G. Jr. and Slaman, Theodore A., On the Σ2-theory of the upper semilattice of Turing degrees, this Journal, vol. 58 (1993), pp. 193–204.Google Scholar
[16]Ladner, Richard E. and Sasso, Leonard P. Jr., The weak truth table degrees of recursively enumerable sets, Annals of Mathematical Logic, vol. 8 (1975), pp. 429–448.CrossRefGoogle Scholar
[17]Lempp, Steffen and Nies, André, The undecidability of the Π4-theory for the r.e. wtt- and Turing degrees, to appear, this Journal.Google Scholar
[18]Lerman, Manuel E., Degrees of unsolvability, Perspectives in Mathematical Logic, Ω-Series, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[19]Odifreddi, Piergiorgio, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland, Amsterdam, 1989.Google Scholar
[20]Shore, Richard A., On the ∀∃-sentences of α-recursion theory, Generalized recursion theory II (Amsterdam) (Fenstad, Jens E., Gandy, Robin O., and Sacks, Gerald E., editors), Studies in Logic and the Foundations of Mathematics, vol. 94, North-Holland, 1978, pp. 331–354.Google Scholar
[21]Shore, Richard A. and Slaman, Theodore A., The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, Theoretical Computer Science, vol. 97 (1992), pp. 263–284.CrossRefGoogle Scholar
[22]Soare, Robert I., Recursively enumerable sets and degrees: The study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Ω-Series, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[23]Stob, Michael, Wtt-degrees and T-degrees of recursively enumerable sets, this Journal, vol. 48 (1983), pp. 921–930.Google Scholar
[24]Stone, Marshall, The theory of representations for Boolean algebras, Transactions of the American Mathematical Society, vol. 40 (1936), pp. 37–111.Google Scholar