Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T02:04:49.406Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal complementation below uniform upper bounds for the arithmetical degrees

Published online by Cambridge University Press:  12 March 2014

Masahiro Kumabe
Masahiro Kumabe*
Affiliation:
University of the Air, Kanagawa Study Center, 2-31-1, Ohoka, Minami-Ku, Yokohama, 232, Japan, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

This paper was inspired by Lerman [15] in which he proved various properties of upper bounds for the arithmetical degrees. We discuss the complementation property of upper bounds for the arithmetical degrees. In Lerman [15], it is proved that uniform upper bounds for the arithmetical degrees are jumps of upper bounds for the arithmetical degrees. So any uniform upper bound for the arithmetical degrees is not a minimal upper bound for the arithmetical degrees. Given a uniform upper bound a for the arithmetical degrees, we prove a minimal complementation theorem for the upper bounds for the arithmetical degrees below a. Namely, given such a and b < a which is an upper bound for the arithmetical degrees, there is a minimal upper bound for the arithmetical degrees c such that b ∪ c = a. This answers a question in Lerman [15]. We prove this theorem by different methods depending on whether a has a function which is not dominated by any arithmetical function. We prove two propositions (see §1), of which the theorem is an immediate consequence.

Our notation is almost standard. Let A ⊕ B = {2n∣n ∈ A} ∪ {2n + 1∣n + 1∣n ∈ B} for any sets A and B. Let ω be the set of nonnegative natural numbers.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 4 , December 1996 , pp. 1158 - 1192
Copyright
Copyright © Association for Symbolic Logic 1996

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 jump is definable in the structure of the degrees of unsolvability, to appear, 1989.Google Scholar
[2]Cooper, S. B., The strong anticupping property for recursively enumerable degrees, this Journal, vol. 54 (1989), pp. 527–539.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 note series, vol. 45, Cambridge University Press, 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]Kumabe, M., Minimal upper bounds for arithmetical degrees, this Journal, vol. 59 (1994), pp. 516–528.Google Scholar
[11]Lachlan, A. H., The impossibility of finding relative complements for recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 434–454.Google Scholar
[12]Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 16, Cambridge University Press, no. 3, 1966, pp. 537–569.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., Degrees of unsolvability, perspectives in mathematical logic, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[15]Lerman, M., Upper bounds for the arithmetical degrees, Annals of Pure and Applied Logic, vol. 29 (1985), pp. 225–254.CrossRefGoogle Scholar
[16]Posner, D., The upper semilattice of degrees ≤ 0′ is complemented, this Journal, vol. 46 (1981), pp. 705–713.Google Scholar
[17]Posner, D. and Robinson, R. W., Degrees joining to 0′, this Journal, vol. 46 (1981), pp. 714–722.Google Scholar
[18]Sacks, G. E., Forcing with perfect closed sets, Axiomatic settheory, Proc. sym. pure mat. 13 part I, American Mathematical Society, Providence, RI, 1971, pp. 714–722.Google Scholar
[19]Seetapun, D. and Slaman, T., Minimal complement, to appear.Google Scholar
[20]Slaman, T. A. and Steel, J. R., Complementation in the Turing degrees, this Journal, vol. 54 (1989), pp. 160–176.Google Scholar
[21]Yates, C. E. M., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 159–168.Google Scholar