Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T16:16:29.820Z Has data issue: false hasContentIssue false
  • English
  • Français

The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility

Published online by Cambridge University Press:  12 March 2014

Steffen Lempp  and
Manuel Lerman
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706, E-mail: [email protected]
Manuel Lerman
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 3 , September 1992 , pp. 1120 - 1130
Copyright
Copyright © Association for Symbolic Logic 1992

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, K. and Lerman, M., Lattice embeddings into the recursively enumerable degrees, this Journal, vol. 51 (1986), pp. 257–272.Google Scholar
[2]Ambos-Spies, K. and Lerman, M., Lattice embeddings into the recursively enumerable degrees. II, this Journal, vol. 54 (1989), pp. 735–760.Google Scholar
[3]Cooper, S. B., The jump is definable in the structure of the degrees of unsolvability, preprint.Google Scholar
[4]Epstein, R. L., Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer-Verlag, Berlin, 1979.CrossRefGoogle Scholar
[5]Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences of the United States of America, vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[6]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
[7]Harrington, L. and Slaman, T. A., Interpreting arithmetic in the Turing degrees of the recursively enumerable sets (to appear).Google Scholar
[8]Hinman, P. G. and Slaman, T. A., Jump embeddings into the Turing degrees, this Journal, vol. 56 (1991), pp. 563–591.Google Scholar
[9]Lachlan, A. H., Distributive initial segments of the degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 457–472.CrossRefGoogle Scholar
[10]Lempp, S. and Lerman, M., Priority arguments using iterated trees of strategies, Recursion theory week (Ambos-Spies, K.et al., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, Berlin, 1990, pp. 277–296.CrossRefGoogle Scholar
[11]Lempp, S. and Lerman, M., The decidability of the existential theory of the poset of the recursively enumerable degrees with jump relations (in preparation).Google Scholar
[12]Lempp, S. and Slaman, T. A., A limit on relative genericity in the recursively enumerable degrees, this Journal, vol. 54 (1989), pp. 376–395.Google Scholar
[13]Lerman, M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[14]Lerman, M. and Shore, R. A., Decidability and invariant classes for degree structures, Transactions of the American Mathematical Society, vol. 301 (1988), pp. 669–692.CrossRefGoogle Scholar
[15]Mučnik, A. A., On the solvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR, vol. 108 (1956), pp. 194–197. (Russian)Google Scholar
[16]Shore, R. A., On the ∀∃-sentences of α-recursion theory, Generalized recursion theory. II (Fenstad, J. E.et al., editors), North-Holland, Amsterdam, 1978, pp. 331–354.Google Scholar
[17]Shore, R. A., On homogeneity and definability in the first-order theory of the Turing degrees, this Journal, vol. 47 (1982), pp. 8–16.Google Scholar
[18]Shore, R. A., A non-inversion theorem for the jump operator, Annals of Pure and Applied Logic, vol. 40 (1988), pp. 277–303.CrossRefGoogle Scholar
[19]Simpson, S. G., First-order theory of the degrees of recursive unsolvability, Annals of Mathematics, ser. 2, vol. 105 (1977), pp. 121–139.CrossRefGoogle Scholar
[20]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar