Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-12-04T09:29:31.539Z Has data issue: false hasContentIssue false
  • English
  • Français

Splitting and nonsplitting, II: A low2 c.e. degree above which 0′ is not splittable

Published online by Cambridge University Press:  12 March 2014

S. Barry Cooper  and
Angsheng Li
S. Barry Cooper
Affiliation:
School of Mathematics, University of Leeds, Leeds, LS2 9JT, England, E-mail: [email protected], URL: http://www.amsta.leeds.ac.uk/~pmt6sbc
Angsheng Li*
Affiliation:
School of Mathematics, University of Leeds, Leeds, LS2 9JT, England, E-mail: [email protected]
*
Institute of Software, Chinese Academy of Sciences, P.O. Box, 8718, Beijing, 100080, P.R. of, China, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown that there exists a low2 Harrington non-splitting base — that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if 0′ = x ∨ y, then either 0′ = x ∨ a or 0′ = y ∨ a. Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the low2-ness requirements to be satisfied, and the proof given involves new techniques with potentially wider application.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 67 , Issue 4 , December 2002 , pp. 1391 - 1430
Copyright
Copyright © Association for Symbolic Logic 2002

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]Arslanov, M. M., Cooper, S. B., and Li, A., There is no low maximal d.c.e. degree, Mathematical Logic Quarterly, vol. 46 (2000), no. 3, pp. 409–416.3.0.CO;2-P>CrossRefGoogle Scholar
[2]Cooper, S. B. and Copestake, C. S., Properly ∑2 enumeration degrees, Zeitschrift für Mathenatische Logik and Grundlagen der Mathematik, vol. 34 (1988), pp. 491–522.CrossRefGoogle Scholar
[3]Cooper, S. B. and Li, A., Splitting and nonsplitting, I: A Low3Harrington nonsplitting base, to appear.Google Scholar
[4]Cooper, S. B., Li, A., and Yi, X., On the distribution of Lachlan nonsplitting bases, Archive for Mathematical Logic, vol. 41 (2002), pp. 455–482.CrossRefGoogle Scholar
[5]Friedberg, R. G., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences of USA, vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[6]Harrington, L., Understanding Lachlan's monster paper, handwritten notes, Department of Mathematics, University of California at Berkeley, 1980.Google Scholar
[7]Lachlan, A. H., A recursively enumerable degree which will not split over all lesser ones, Annals of Mathematical Logic, vol. 9 (1975), pp. 307–365.CrossRefGoogle Scholar
[8]Muchnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Academii Nauk, vol. 108 (1956), pp. 194–197, in russian.Google Scholar
[9]Odifreddi, P., Classical Recursion Theory, North-Holland, Amsterdam, New York, Oxford, 1989.Google Scholar
[10]Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[11]Robinson, R. W., Interpolation and embedding in the recursively enumerable degrees, Annals of Mathematics, vol. 93 (1971), pp. 285–314.CrossRefGoogle Scholar
[12]Sacks, G. E., On the degrees less than 0′, Annals of Mathematics, vol. 77 (1963), pp. 211–231.CrossRefGoogle Scholar
[13]Sacks, G. E., The recursively enumerable degrees are dense, Annals of Mathematics, vol. 80 (1964), pp. 300–312.CrossRefGoogle Scholar
[14]Shore, R. A. and Slaman, T. A., Working below Low2recursively enumerable degrees, Archive for Mathematical Logic, vol. 29 (1990), pp. 201–211.CrossRefGoogle Scholar
[15]Soare, R. I., Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, Heidelberg, London, New York, 1987.CrossRefGoogle Scholar