Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-06T14:55:34.370Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal degrees and the jump operator1

Published online by Cambridge University Press:  12 March 2014

S. B. Cooper
S. B. Cooper*
Affiliation:
University of Leeds, Leeds, England University of California, Berkeley, California 94720
Get access Rights & Permissions [Opens in a new window]

Extract

The jump a′ of a degree a is defined to be the largest degree recursively enumerable in a in the upper semilattice of degrees of unsolvability. We examine below some of the ways in which the jump operation is related to the partial ordering of the degrees. Fried berg [3] showed that the equation a = x′ is solvable if and only if a ≥ 0′. Sacks [13] showed that we can find a solution of a = x′ which is ≤ 0′ (and in fact is r.e.) if and only if a ≥ 0′ and is r.e. in 0′. Spector [16] constructed a minimal degree and Sacks [13] constructed one ≤ 0′. So far the only result concerning the relationship between minimal degrees and the jump operator is one due to Yates [17] who showed that there is a minimal predecessor for each non-recursive r.e. degree, and hence that there is a minimal degree with jump 0′. In §1, we obtain an analogue of Friedberg's theorem by constructing a minimal degree solution for a = x′ whenever a ≥ 0′. We incorporate Friedberg5s original number-theoretic device with a complicated sequence of approximations to the nest of trees necessary for the construction of a minimal degree. The proof of Theorem 1 is a revision of an earlier, shorter presentation, and incorporates many additions and modifications suggested by R. Epstein. In §2, we show that any hope for a result analogous to that of Sacks on the jumps of r.e. degrees cannot be fulfilled since 0″ is not the jump of any minimal degree below 0′. We use a characterization of the degrees below 0′ with jump 0″ similar to that found for r.e. degrees with jump 0′ by R. W. Robinson [12]. Finally, in §3, we give a proof that every degree a ≤ 0′ with a′ = 0″ has a minimal predecessor. Yates [17] has already shown that every nonzero r.e. degree has a minimal predecessor, but that there is a nonzero degree ≤ 0′ with no minimal predecessor (see [18]; or for the original unrelativized result see [10] or [4]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 38 , Issue 2 , June 1973 , pp. 249 - 271
Copyright
Copyright © Association for Symbolic Logic 1973

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.)

Footnotes

1

Financial support for this paper was obtained from the S.R.C. (while the author was a graduate student, at Leicester University and at Manchester University), and also from a Fulbright-Hays travel grant. The material appearing is based on part of the author's doctoral thesis (Leicester University, 1971).

References

REFERENCES

[1]Cooper, S. B., Jump equivalence of the Δ20 hyperhyperimmune sets, this Journal, vol. 37 (1972), pp. 598–600.Google Scholar
[2]Cooper, S. B., Sets recursively enumerable in high degrees, Notices of the American Mathematical Society, vol. 19 (1972), A–20. AbstractGoogle Scholar
[3]Friedberg, Richard M., A criterion for completeness of degrees of unsohability, this Journal, vol. 22 (1957), pp. 159–160.Google Scholar
[4]Hugill, D. F., Initial segments of Turing degrees, Proceedings of the London Mathematical Society, vol. 19 (1968), pp. 1–16.Google Scholar
[5]Jockusch, Carl G. Jr., Upward closure and cohesive degrees (to appear).Google Scholar
[6]Jockusch, Carl G. Jr., The degrees of hyperhyperimmune sets, this Journal, vol. 34 (1969), pp. 489–493.Google Scholar
[7]Kleene, Stephen C., Introduction to metamathematics, Van Nostrand, Princeton, N.J., 1952.Google Scholar
[8]Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 16 (1966), pp. 537–569.CrossRefGoogle Scholar
[9]Martin, Donald A., A theorem on hyperhypersimple sets, this Journal, vol. 28 (1963), pp. 273–278.Google Scholar
[10]Martin, Donald A., Measure, category and degrees of unsohability (unpublished).Google Scholar
[11]Miller, W. and Martin, D. A., The degrees of hyperimmune sets, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 159–166.CrossRefGoogle Scholar
[12]Robinson, Robert W., A dichotomy of the recursively enumerable sets, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 339–356.CrossRefGoogle Scholar
[13]Sacks, Gerald E., Degrees of unsohability, Annals of Mathematics Studies, No. 55, Princeton University Press, Princeton, N.J., 1963.Google Scholar
[14]Sasso, L. P., A cornucopia of minimal degrees, this Journal, vol. 35 (1970), pp. 383–388.Google Scholar
[15]Schoenfield, J. R., A theorem on minimal degrees, this Journal, vol. 31 (1966), pp. 539–544.Google Scholar
[16]Spector, Clifford, On degrees of unsohability, Annals of Mathematics (2), vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[17]Yates, C. E. M., Initial segments of the degrees of unsohability, II. Minimal degrees, this Journal, vol. 35 (1970), pp. 243–266.Google Scholar
[18]Yates, C. E. M., Initial segments and implications for the structure of degrees (to appear).Google Scholar