Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-31T18:44:36.821Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal complements for degrees below 0′

Published online by Cambridge University Press:  12 March 2014

Andrew Lewis
Andrew Lewis*
Affiliation:
Department of Pure Mathematics, School of Mathematics, University of Leeds, Leeds, LS2 9JT, UK, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract.

It is shown that for every (Turing) degree 0 < a < 0′ there is a minimal degree m < 0′ such that a ∨ m = 0′ (and therefore a ∧ m = 0).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 4 , December 2004 , pp. 937 - 966
Copyright
Copyright © Association for Symbolic Logic 2004

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]Chong, C. T., Generic sets and minimal α-degrees, Transactions of the American Mathematical Society, vol. 254 (1979), pp. 157–169.Google Scholar
[2]Cooper, S. B., Minimal degrees and the jump operator, this Journal, vol. 38 (1973), pp. 249–271.Google Scholar
[3]Cooper, S. B., Lewis, A. E. M., and Yang, Yue, Properly Σ2minimal degrees and 0″ complementation, to appear.Google Scholar
[4]Epstein, R. L., Minimal degrees of unsolvability and the full approximation construction, Memoirs of the American Mathematical Society, vol. 163, 1975.Google Scholar
[5]Fukuyama, M., A remark on minimal degrees, Science Reports of Tokyo Daig., vol. 9 (1968), pp. 255–256.Google Scholar
[6]Jockusch, C. G. and Posner, D., Double-jumps of minimal degrees, this Journal, vol. 43 (1978), pp. 715–724.Google Scholar
[7]Lewis, A. E. M., Finite cupping sets, to appear in Applied Mathematics Letters.Google Scholar
[8]Lewis, A. E. M., The minimal complementation property above 0′, to appear.Google Scholar
[9]Lewis, A. E. M., A single minimal complement for the c. e. degrees, to appear.Google Scholar
[10]Li, A. and Yi, X., Cupping the recursively enumerable degrees by d-r. e. degrees, Proceedings of the London Mathematical Society, vol. 78 (1999), pp. 1–21.Google Scholar
[11]Odifreddi, P. G., Classical recursion theory, vol. 2, Elsevier, 1999.Google Scholar
[12]Posner, D., High degrees, Ph. D. Thesis, University of California, Berkeley, 1977.Google Scholar
[13]Posner, D., The uppersemilattice of degrees below 0′ is complemented, this Journal, vol. 46 (1981), pp. 705–713.Google Scholar
[14]Posner, D. and Robinson, R. W., Degrees joining to 0′, this Journal, vol. 46 (1981), pp. 714–722.Google Scholar
[15]Sacks, G. E., Degrees of unsolvability, 2nd ed., Princeton University Press, 1963.Google Scholar
[16]Seetapun, D. and Slaman, T. A., Minimal complements, unpublished, 1992.Google Scholar
[17]Shoenfield, J. R., A theorem on minimal degrees, this Journal, vol. 31 (1966), pp. 539–544.Google Scholar
[18]Slaman, T. A. and Steel, J., Complementation in the Turing degrees, this Journal, vol. 54 (1989), pp. 160–176.Google Scholar
[19]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar
[20]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[21]Yates, C. E. M., Recursively enumerable degrees and the degrees less than 0′, Models and recursion theory (Crossley, et al., editors), North Holland, 1967, pp. 264–271.Google Scholar
[22]Yates, C. E. M., Initial segments of the degrees of unsolvability, part 2: minimal degrees, this Journal, vol. 35 (1970), pp. 243–266.Google Scholar