Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-28T14:33:43.719Z Has data issue: false hasContentIssue false
  • English
  • Français

Degrees bounding minimal degrees

Published online by Cambridge University Press:  24 October 2008

C. T. Chong  and
R. G. Downey
C. T. Chong
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, 0511, Singapore
R. G. Downey
Affiliation:
Department of Mathematics, Victoria University of Wellington, P.O. Box 600, Wellington, New Zealand
Get access Rights & Permissions [Opens in a new window]

Extract

A set is called n-generic if it is Cohen generic for n-quantifier arithmetic. A (Turing) degree is n-generic if it contains an n-generic set. Our interest in this paper is the relationship between n-generic (indeed 1-generic) degrees and minimal degrees, i.e. degrees which are non-recursive and which bound no degrees intermediate between them and the recursive degree. It is known that n-generic degrees and minimal degrees have a complex relationship since Cohen forcing and Sacks forcing are mutually incompatible. The goal of this paper is to show.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 105 , Issue 2 , March 1989 , pp. 211 - 222
Copyright
Copyright © Cambridge Philosophical Society 1989

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.. Minimal degrees recursive in 1-generic degrees, Ann. Pure Appl. Logic. (To appear.)Google Scholar
[2]Chong, C. T.. Minimal degrees and 1-generic degrees in higher recursion theory, II, Ann. Pure Appl. Logic 31 (1986), 165–176.CrossRefGoogle Scholar
[3]Chong, C. T. and Jockusch, C. G.. Minimal degrees and 1-generic degrees below 0'. In Computation and Proof Theory, Lecture Notes in Math. vol. 1104 (Springer-Verlag, 1984), pp. 63–77.CrossRefGoogle Scholar
[4]Epstein, R. L.. Minimal Degrees of Unsolvability and the Full Approximation Method, Mem. Amer. Math. Soc. no. 162 (American Mathematical Society, 1975).Google Scholar
[5]Epstein, R. L.. Initial Segments of the Degrees Below 0', Mem. Amer. Math. Soc. no. 241 (American Mathematical Society, 1981).CrossRefGoogle Scholar
[6]Haught, C.. Turing and truth table degrees of 1-generic and recursively enumerable sets. Ph.D. thesis, Cornell University (1985).Google Scholar
[7]Jockusch, C. G.. Degrees of generic sets. In Recursion Theory: Its Generalizations and Applications, London Math. Soc. Lecture Note ser. no. 45 (Cambridge University Press, 1980), pp. 110–139.CrossRefGoogle Scholar
[8]Lerman, M.. Degrees of Unsolvability (Springer-Verlag, 1983).CrossRefGoogle Scholar
[9]Lerman, L.. Degrees which do not bound minimal degrees. Ann. Pure Appl. Logic 30 (1986), 249–276.CrossRefGoogle Scholar
[10]Posner, D.. High Degrees. Ph.D. thesis, Berkeley (1977).Google Scholar
[11]Posner, D.. A survey of the non r.e. degrees below 0'. In Recursion Theory: Its Generalizations and Applications, London Math. Soc. Lecture Note Series no. 45 (Cambridge University Press, 1980), pp. 52–109.CrossRefGoogle Scholar
[12]Sacks, G. E.. Degrees of Unsolvability. Ann. of Math. Stud. no. 55 (Princeton University Press, 1966).Google Scholar
[13]Shoenfield, J. R.. Degrees of Unsolvability (North Holland, 1971).Google Scholar
[14]Soare, R. I.. Recursively Enumerable Sets and Degrees, Ω Series (Springer-Verlag, 1987).CrossRefGoogle Scholar
[15]Spector, C.. On the degrees of recursive unsolvability. Annals of Math. 64 (1956), 581–592.CrossRefGoogle Scholar