Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T12:59:46.100Z Has data issue: false hasContentIssue false
  • English
  • Français

The undecidability of the Π4-theory for the r.e. wtt and Turing degrees

Published online by Cambridge University Press:  12 March 2014

Steffen Lempp  and
André Nies
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706, E-mail: [email protected]
André Nies
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the Π4-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 60 , Issue 4 , December 1995 , pp. 1118 - 1136
Copyright
Copyright © Association for Symbolic Logic 1995

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

[A83]Ambos-Spies, K., Contiguous r.e. degrees, Computation and proof theory (Proceedings of Logic Colloquium '83, Aachen), Lecture Notes in Mathematics, vol. 1104, Springer-Verlag, Berlin, 1984, pp. 58–68.Google Scholar
[A85]Ambos-Spies, K., Anti-mitotic recursively enumerable sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 31 (1985), pp. 461–477.CrossRefGoogle Scholar
[ANS92]Ambos-Spies, K., Nies, A., and Shore, R., The theory of the r.e. weak truth-table degrees is undecidable, this Journal, vol. 57 (1992), pp. 864–874.Google Scholar
[AS93]Ambos-Spies, K. and Shore, R., Undecidability and 1-types in the r.e. degrees, Annals of Pure and Applied Logic, vol. 63 (1993), pp. 3–37.CrossRefGoogle Scholar
[HaSh82]Harrington, L. and Shelah, S., The undecidability of the recursively enumerable degrees, Bulletin (New Series) of the American Mathematical Society, vol. 6 (1982), pp. 79–80.CrossRefGoogle Scholar
[HtS90]Haught, C. A. and Shore, R., Undecidability and initial segments of the {r.e.) tt-degrees, this Journal, vol. 55 (1990), pp. 987–1006.Google Scholar
[La66]Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, ser. 3, vol. 16 (1966), pp. 537–569.CrossRefGoogle Scholar
[La72]Lachlan, A. H., Recursively enumerable many-one degrees, Algebra and Logic, vol. 11 (1972), pp. 186–202.CrossRefGoogle Scholar
[LdSa75]Ladner, R. and Sasso, S., The weak truth-table degrees of r.e. sets, Annals of Mathematical Logic, vol. 8 (1975), pp. 429–449.CrossRefGoogle Scholar
[Ler83]Lerman, M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[N92]Nies, A., Definability and undecidability in recursion theoretic semi-lattices, Ph.D. thesis, Universität Heidelberg, Heidelberg, 1992.Google Scholar
[Nta]Nies, A., Undecidable fragments of elementary theories, Algebra Universalis (to appear).Google Scholar