Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-16T23:36:29.097Z Has data issue: false hasContentIssue false
  • English
  • Français

How enumeration reductibility yields extended Harrington non-splitting

Published online by Cambridge University Press:  12 March 2014

Mariya I. Soskova  and
S. Barry Cooper
Mariya I. Soskova
Affiliation:
University of Leeds, Department of Pure Mathematics, Leeds, LS2 9JT., UK, E-mail: [email protected]
S. Barry Cooper
Affiliation:
University of Leeds, Department of Pure Mathematics, Leeds, LS2 9JT., UK, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

§1. Introduction. Sacks [16] showed that every computably enumerable (c.e.) degree > 0 has a c.e. splitting. Hence, relativising, every c.e. degree has a Δ2 splitting above each proper predecessor (by ‘splitting’ we understand ‘nontrivial splitting’). Arslanov [1] showed that 0′ has a d.c.e. splitting above each c.e. a < 0′. On the other hand, Lachlan [11] proved the existence of a c.e. a < 0 which has no c.e. splitting above some proper c.e. predecessor, and Harrington [10] showed that one could take a = 0′. Splitting and nonsplitting techniques have had a number of consequences for definability and elementary equivalence in the degrees below 0′.

Heterogeneous splittings are best considered in the context of cupping and non-cupping. Posner and Robinson [15] showed that every nonzero Δ2 degree can be nontrivially cupped to 0′, and Arslanov [1] showed that every c.e. degree > 0 can be d.c.e. cupped to 0′ (and hence since every d.c.e., or even n-c.e., degree has a nonzero c.e. predecessor, every n-c.e. degree > 0 is d.c.e. cuppable). Cooper [4] and Yates (see Miller [13]) showed the existence of degrees noncuppable in the c.e. degrees. Moreover, the search for relative cupping results was drastically limited by Cooper [5], and Slaman and Steel [17] (see also Downey [9]), who showed that there is a nonzero c.e. degree a below which even Δ2 cupping of c.e. degrees fails.

We prove below what appears to be the strongest possible of such nonsplitting and noncupping results.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 2 , June 2008 , pp. 634 - 655
Copyright
Copyright © Association for Symbolic Logic 2008

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., Structural properties of the degrees below 0′, Doklady Akademii Nauk SSSR, vol. 283 (1985), pp. 270–273.Google Scholar
[2]Arslanov, M. M., Cooper, S. B., and Kalimullin, I. Sh., Splitting properties of total enumeration degrees, Algebra and Logic, vol. 42 (2003), pp. 1–13.CrossRefGoogle Scholar
[3]Arslanov, M. M. and Sorbi, A., Relative splittings of 0′e in the Δ2 enumeration degrees. Logic Colloquium'98 (Buss, S. and Pudlak, P., editors), Springer-Verlag, 1999.Google Scholar
[4]Cooper, S. B., On a theorem of C. E. M. Yates, 1974, handwritten notes.Google Scholar
[5]Cooper, S. B., The strong anti-cupping property for recursively enumerable degrees, this Journal, vol. 54 (1989), pp. 527–539.Google Scholar
[6]Cooper, S. B., Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion Theory Week, Proceedings Oberwolfach 1989 (Ambos-Spies, K., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, 1990. pp. 57–110.Google Scholar
[7]Cooper, S. B., Computability Theory, Chapman & Hall/CRC Mathematics, 2004.Google Scholar
[8]Cooper, S. B., Sorbi, A., Li, A., and Yang, Y., Bounding and nonbounding minimal pairs in the enumeration degrees, this Journal, vol. 70 (2005), pp. 741–766.Google Scholar
[9]Downey, R. G., degrees and transfer theorems, Illinois Journal of Mathematics, vol. 31 (1987), pp. 419–427.CrossRefGoogle Scholar
[10]Harrington, L., Understanding Lachlan s monster paper, 1980, handwritten notes.Google Scholar
[11]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
[12]Lachlan, A. H. and Shore, R. A., The n-rea enumeration degrees are dense. Archive for Mathematical Logic, vol. 31 (1992), pp. 277–285.CrossRefGoogle Scholar
[13]Miller, D., High recursively enumerable degrees and the anti-cupping property. Logic Year 1979–80: University of Connecticut (Lerman, M., Schmerl, J. H., and Soare, R. I., editors), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, 1981.CrossRefGoogle Scholar
[14]Odifreddi, P. G., Classical Recursion Theory, Volume II, North-Holland/Elsevier, 1999.Google Scholar
[15]Posner, D. B. and Robinson, R. W., Degrees joining to 0′, this Journal, vol. 46 (1981), pp. 714–722.Google Scholar
[16]Sacks, G. E., On the degrees less than 0′, Annals of Mathematics, vol. 77 (1963), no. 2, pp. 211–231.CrossRefGoogle Scholar
[17]Slaman, T. A. and Steel, J. R., Complementation in the Turing degrees, this Journal, vol. 54 (1989), pp. 160–176.Google Scholar
[18]Soare, R. I., Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.CrossRefGoogle Scholar