Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T05:53:25.599Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal upper bounds for arithmetical degrees

Published online by Cambridge University Press:  12 March 2014

Masahiro Kumabe
Masahiro Kumabe*
Affiliation:
The University of the Air, 2-11, Wakaba, Mihama-Ku, Chiba 261, Japan
Get access Rights & Permissions [Opens in a new window]

Extract

This paper was inspired by Lerman [14] in which he proved various properties of upper bounds for the arithmetical degrees. The degrees which are upper bounds for the arithmetical degrees were first studied by Hodes [5] and Enderton and Putnam [5]. Enderton and Putnam [5] showed that if a is an upper bound for the arithmetical degrees, then a(2) ≥ 0(ω). This area was further studied by Hodes [5], Knight, Lachlan and Soare [12], Jockusch and Simpson [12], and Sacks [17].

Enderton and Putnam [5] and Sacks [17] have combined to show that 0(ω) is the least degree in {a(2): a is an upper bound for the arithmetical degrees}. So there seem to be some analogies between the degrees of upper bounds for the arithmetical degrees and the degrees below 0(2). But Sacks [17] showed an important difference between these two structures; namely, the Turing jumps of upper bounds for the arithmetical degrees have no least element. In Lerman [14], a systematic investigation of properties of the jumps of upper bounds for the arithmetical degrees was suggested, which could lead to a definition of the jump operator over the elementary theory of the partial ordering of the degrees. Although Cooper [5] found a degree-theoretic definition of the jump operator, Lerman's plan is still interesting.

We say a degree a is generic if there is a representative A of a such that A is Cohen generic for the arithmetical sentences. By Jockusch [5], the statement that A is Cohen generic for the arithmetical sentences is equivalent to saying that for any arithmetical set S of binary strings, there is a σ extended by A such that σ is in S or no extension of σ is in S. First, we investigate the relation between generic degrees and upper bounds for the arithmetical degrees. In the case D(≤ 0′), the set of degrees below 0′, it is well known that any nonrecursive r.e. degree bounds a 1-generic degree (Cohen generic for Σ1 sentences). Jockusch and Ponser [12] showed that any degree a with a″ >T (a ∪ 0′)′ bounds a 1-generic degree.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 2 , June 1994 , pp. 516 - 528
Copyright
Copyright © Association for Symbolic Logic 1994

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] Cooper, S. B., The strong anticupping property for recursively enumerable degrees, this Journal, vol. 54 (1989), pp. 527–539.Google Scholar
[2] Cooper, S. B., The jump is definable in the structure of degrees of unsohablity (to appear).Google Scholar
[3] Enderton, H. B. and Putnam, H.. A note on the hyperarithmetical hierarchy, this Journal, vol. 35 (1970), pp. 429–430.Google Scholar
[4] Hodes, H., Uniform upper bounds on ideals of Turing degrees, this Journal, vol. 43 (1978), pp. 601–612.Google Scholar
[5] Hodes, H., Jumping to an uniform upper bound, Proceedings of the American Mathematical Society, vol. 85 (1982), pp. 600–602.CrossRefGoogle Scholar
[6] Jockusch, C. G. Jr., Degrees of generic sets, Proceedings of London Mathematical Society Lecture Notes Series no. 45, Cambridge University Press, London and New York, 1980, pp. 110–139.Google Scholar
[7] Jockusch, C. G. Jr. and Posner, D., Double jumps of minimal degrees, this Journal, vol. 43 (1978), pp. 715–724.Google Scholar
[8] Jockusch, C. G. Jr. and Simpson, S. G., A degree-theoretic definition of the ramified analytical hierarchy, Annals of Mathematical Logic, vol. 10 (1975), pp. 1–32.CrossRefGoogle Scholar
[9] Knight, J., Lachlan, A. H., and Soare, R., TWO theorems on degrees of models of true arithmetic, this Journal, vol. 49 (1984), pp. 425–436.Google Scholar
[10] Lachlan, A. H., The impossibility of finding relative complements for recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 537–569.Google Scholar
[11] Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceeedings of the London Mathematical Society, vol. 16 (1966), pp. 537–569.CrossRefGoogle Scholar
[12] Lerman, M., Degrees of unsolvability, Perspectives in Mathematical Logic, Springer, Berlin, 1933.Google Scholar
[13] Lerman, M., On recursive linear orderings, Logic year 1979–80: The University of Connecticut, Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, 1981, pp. 132–142.CrossRefGoogle Scholar
[14] Lerman, M., Upper bound for the arithmetical degrees, Annals of Pure and Applied Logic, vol. 29 (1985), pp. 225–254.CrossRefGoogle Scholar
[15] Posner, D., The upper semilattice of degrees ≤ 0′ is complemented, this Journal, vol. 46 (1981), pp. 705–713.Google Scholar
[16] Posner, D. and Robinson, R. W., Degrees joining to 0′, this Journal, vol. 46 (1981), pp. 714–722.Google Scholar
[17] Sacks, G. E., Forcing with perfect closed sets, Axiomatic set theory, Proceedings of Symposia in Pure Mathematics, vol. XII, Part 1 (Scott, Dana S., editor), American Mathematical Society, Providence, Rhode Island, 1971, pp. 331–355.CrossRefGoogle Scholar
[18] Slaman, T. A. and Steel, J. R., Complementation in the Turing degrees, this Journal, vol. 54 (1989), pp. 160–176.Google Scholar
[19] Yates, C. E. M., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 159–168.Google Scholar