Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-22T21:01:28.313Z Has data issue: false hasContentIssue false
  • English
  • Français

On the jump classes of noncuppable enumeration degrees

Published online by Cambridge University Press:  12 March 2014

Charles M. Harris
Charles M. Harris*
Affiliation:
University of Leeds, Department of Mathematics, Leeds, UK, E-mail: [email protected], URL: http://www.maths.leeds.ac.uk/~charlie
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that for every Σ20 enumeration degree b there exists a noncuppable Σ20 degree a > 0e such that and . This allows us to deduce, from results on the high/low jump hierarchy in the local Turing degrees and the jump preserving properties of the standard embedding , that there exist Σ20 noncuppable enumeration degrees at every possible—i.e., above low1—level of the high/low jump hierarchy in the context of .

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 1 , March 2011 , pp. 177 - 197
Copyright
Copyright © Association for Symbolic Logic 2011

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

[Co90]Cooper, S. B., Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion theory week, Oberwolfach 1989 (Ambos-Spies, K., Müller, G., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer Verlag, Heidelberg, 1990, pp. 57–110.Google Scholar
[Co04]Cooper, S. B., Computability theory, Chapman and Hall, 2004.Google Scholar
[CMc85]Cooper, S. B. and McEvoy, K., On minimal pairs of enumeration degrees, this Journal, vol. 50(4) (1985), pp. 983–1001.Google Scholar
[CSY]Cooper, S. B, Sorbi, A., and Yi, X., Cupping and noncupping in the enumeration degrees of Σ20 sets, Annals of Pure and Applied Logic, vol. 82 (1996), pp. 317–342.CrossRefGoogle Scholar
[Gi08]Giorgi, M., A high noncuppable Σ20 e-degree, Archive for Mathematical Logic, vol. 47 (2008), pp. 181–191.CrossRefGoogle Scholar
[GSY]Giorgi, M., Sorbi, A., and Yang, Y., Properly Σ20 enumeration degrees and the high/low hierarchy, this Journal, vol. 71(4) (2006), pp. 1125–1144.Google Scholar
[Gr03]Griffith, E. J., Limit lemmas and jump inversion in the enumeration degrees, Archive for Mathematical Logic, vol. 42 (2003), pp. 553–562.CrossRefGoogle Scholar
[Har10]Harris, C. M., Goodness in the enumeration and singleton degrees, Archive for Mathematical Logic, vol. 49 (2010), no. 6, pp. 673–691.CrossRefGoogle Scholar
[Har]Harris, C. M., Noncuppable enumeration degrees via finite injury, Journal of Logic and Computation, to appear.Google Scholar
[Jo68]Jockusch, C. G., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[LS92]Lachlan, H. and Shore, R. A., The n-rea enumeration degrees are dense, Archive for Mathematical Logic, vol. 31 (1992), pp. 277–285.CrossRefGoogle Scholar
[Mc84]McEvoy, K., The structure of the enumeration degrees, Ph.D. thesis, The University of Leeds, UK, 10 1984.Google Scholar
[NS00]Nies, A. and Sorbi, A., Structural properties and Σ20 enumeration degrees, this Journal, vol. 65(1) (2000), pp. 285–289.Google Scholar
[Od89]Odifreddi, P. G., Classical recursion theory, Elsevier, Amsterdam, 1989.Google Scholar
[Sa63a]Sacks, G. E., Recursive enumerability and the jump operator, Transactions of the American Mathematical Society, vol. 108 (1963), pp. 223–239.CrossRefGoogle Scholar
[Sa67]Sacks, G. E., On a theorem of Lachlan and Martin, Proceedings of the American Mathematical Society, vol. 18 (1967), pp. 140–141.CrossRefGoogle Scholar
[So87]Soare, R. I., Recursively enumerable sets and degrees, Springer, Berlin, 1987.CrossRefGoogle Scholar
[So97]Sorbi, A., The enumeration degrees of the Σ20 sets, Complexity, logic and recursion theory (Sorbi, A., editor), Marcel Dekker, New York, 1997, pp. 303–330.Google Scholar