Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T13:41:23.257Z Has data issue: false hasContentIssue false
  • English
  • Français

Pairs without infimum in the recursively enumerable weak truth table degrees

Published online by Cambridge University Press:  12 March 2014

Paul Fischer
Paul Fischer*
Affiliation:
Fakultät für Mathematik, Universität Bielefeld, D-4800 Bielefeld I, West Germany
Get access Rights & Permissions [Opens in a new window]

Extract

wtt-reducibility has become of some importance in the last years through the works of Ladner and Sasso [1975], Stob [1983] and Ambos-Spies [1984]. It differs from Turing reducibility by a recursive bound on the use of the reduction. This makes some proofs easier in the wtt degrees than in the Turing degrees. Certain proofs carry over directly from the Turing to the wtt degrees, especially those based on permitting. But the converse is also possible. There are some r.e. Turing degrees which consist of a single r.e. wtt degree (the so-called contiguous degrees; see Ladner and Sasso [1975]). Thus it suffices to prove a result about contiguous wtt degrees using an easier construction, and it carries over to the corresponding Turing degrees.

In this work we prove some results on pairs of r.e. wtt degrees which have no infimum. The existence of such a pair has been shown by Ladner and Sasso. Here we use a different technique of Jockusch [1981] to prove this result (Theorem 1) together with some stronger ones. We show that a pair without infimum exists above a given incomplete wtt degree (Theorem 5) and below any promptly simple wtt degree (Theorem 12). In Theorem 17 we prove, however, that there are r.e. wtt degrees such that any pair below them has an infimum. This shows that certain initial segments of the wtt degrees are lattices. Thus there is a structural difference between the wtt and Turing degrees where the pairs without infimum are dense (Ambos-Spies [1984]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 51 , Issue 1 , March 1986 , pp. 117 - 129
Copyright
Copyright © Association for Symbolic Logic 1986

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

Ambos-Spies, K. [1984], On pairs of recursively enumerable degrees, Transactions of the American Mathematical Society, vol. 283, pp. 507–531.CrossRefGoogle Scholar
Ambos-Spies, K. [1985], Cupping and noncapping in the r.e. weak truth table and Turing degrees, Archiv für Mathematische Logik und Grundlagenforschung (to appear).Google Scholar
Ambos-Spies, K., Jockusch, C. G. Jr., Shore, R. A. and Soare, R. I. [1984], An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Transactions of the American Mathematical Society, vol. 281, pp. 109–128.Google Scholar
Jockusch, C. G. Jr., [1981], Three easy constructions of recursively enumerable sets, Logic Year 1979–80 (Lerman, M.et al., editors), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, pp. 83–91.Google Scholar
Ladner, R. E. and Sasso, L. P. [1975], The weak truth table degrees of recursively enumerable sets, Annals of Mathematical Logic, vol. 4, pp. 429–448.Google Scholar
Maass, W. [1982], Recursively enumerable generic sets, this Journal, vol. 47, pp. 809–823.Google Scholar
Soare, R. I. [1980], Fundamental methods for constructing recursively enumerable degrees, Recursion theory: its generalisations and applications (Proceedings of Logic Colloquium '79; Drake, F. R. and Wainer, S. S., editors), London Mathematical Society Lecture Note Series, vol. 45, Cambridge University Press, Cambridge, pp. 1–51.Google Scholar
Stob, M. [1983], wtt-degrees and T-degrees of recursively enumerable sets, this Journal, vol. 48, pp. 921–930.Google Scholar
Yates, C. E. M. [1966], A minimal pair of recursively enumerable degrees, this Journal, vol. 31, pp. 159–168.Google Scholar