Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T01:55:25.301Z Has data issue: false hasContentIssue false
  • English
  • Français

Noncappable enumeration degrees below 0e′

Published online by Cambridge University Press:  12 March 2014

S. Barry Cooper  and
Andrea Sorbi
S. Barry Cooper
Affiliation:
School of Mathematics, University of Leeds, LS2 9JT, England, E-mail: [email protected]
Andrea Sorbi
Affiliation:
Department of Mathematics, University of Siena, 53100 Siena, Italy, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that there exists a noncappable enumeration degree strictly below 0e′.

Keywords

Enumeration operatorenumeration degreeΣ20-set
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 4 , December 1996 , pp. 1347 - 1363
Copyright
Copyright © Association for Symbolic Logic 1996

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]Ahmad, S., Embedding the diamond in the Σ2 enumeration degrees, this Journal, vol. 56 (1991), pp. 195–212.Google Scholar
[2]Ambos-Spies, K., On the structure of the recursively enumerable degrees, Ph.D. thesis, University of Munich, 1980.Google Scholar
[3]Ambos-Spies, K., On pairs of recursively enumerable degrees, Transactions of the American Mathematical Society, vol. 283 (1984), pp. 507–531.CrossRefGoogle Scholar
[4]Case, J., Enumeration reducibility and partial degrees, Annals of Mathematical Logic, vol. 2 (1971), pp. 419–439.CrossRefGoogle Scholar
[5]Cooper, S. B., Partial degrees and the density problem, this Journal, vol. 47 (1982), pp. 854–859.Google Scholar
[6]Cooper, S. B., Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense, this Journal, vol. 49 (1984), pp. 503–513.Google Scholar
[7]Cooper, S. B., Enumeration reducibility using bounded information: counting minimal covers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 33 (1987), pp. 537–560.CrossRefGoogle Scholar
[8]Cooper, S. B., Enumeration reducibility, non-deterministic computations and relative computability of partial functions, Recursion Theory Week (Heidelberg) (Ambos-Spies, K., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, no. 1432, Springer-Verlag, year?, Proceedings Oberwolfach 1989, pp. 57–110.Google Scholar
[9]Cooper, S. B. and Copestake, C. S., Properly Σ2 enumeration degrees, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 34 (1988), pp. 491–522.CrossRefGoogle Scholar
[10]Cooper, S. B., Slaman, T. A., and Yi, X., The Σ2 theory of the recursively enumerable degrees, to appear.Google Scholar
[11]Friedberg, R. M. and Rogers, H. Jr., Reducibility and completeness for sets of integers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 117–125.CrossRefGoogle Scholar
[12]Gutteridge, L., Some results on enumeration reducibility, Ph.D. thesis, Simon Fraser University, 1971.Google Scholar
[13]Jockush, C. G. Jr., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[14]Lagemann, J., Embedding theorems in the reducibility ordering of the partial degrees, Ph.D. thesis, MIT, 1972.Google Scholar
[15]Lerman, M., Degrees of Unsolvability, Perspectives in Mathematical Logic, Omega series, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[16]McEvoy, K., Jumps of quasi-minimal enumeration degrees, this Journal, vol. 50 (1985), pp. 839–848.Google Scholar
[17]McEvoy, K. and Cooper, S. B., On minimal pairs of enumeration degrees, this Journal, vol. 50 (1985), pp. 983–100.Google Scholar
[18]Odifreddi, P., Classical recursion theory, North-Holland, Amsterdam, 1989.Google Scholar
[19]Posner, D., The upper semilattice of degrees ≤ 0′ is complemented, this Journal, vol. 46 (1981), pp. 705–713.Google Scholar
[20]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[21]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[22]Yates, C. E. M., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 159–168.Google Scholar