Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-25T14:02:38.162Z Has data issue: false hasContentIssue false
  • English
  • Français

Structural properties and Σ20 enumeration degrees

Published online by Cambridge University Press:  12 March 2014

André Nies  and
Andrea Sorbi
André Nies
Affiliation:
Department of Mathematics, The University of Chicago, Chicago, Illinois 60637-1514, 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 each Σ20 set which is hypersimple relative to ∅′ is noncuppable in the structure of the Σ20 enumeration degrees. This gives a connection between properties of Σ20 sets under inclusion and and the Σ20 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to ∅′.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 1 , March 2000 , pp. 285 - 292
Copyright
Copyright © Association for Symbolic Logic 2000

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

[BCS]Bereznyuk, S., Coles, R., and Sorbi, A., The distribution of properly Σ20 enumeration degrees, this Journal, to appear.Google Scholar
[Coo90]Cooper, S.B., Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion theory week, Oberwolfach 1989 (Ambos-Spies, K., Muller, G., and Sacks, G.E., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, Heidelberg, 1990, pp. 57–110.Google Scholar
[CSY97]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 (1997), pp. 317–342.CrossRefGoogle Scholar
[DJ87]Downey, R.G. and Jockusch, Carl G. Jr., T-degrees, jump classes, and strong reducibilities, Transactions of the American Mathematical Society, vol. 30 (1987), pp. 103–137.CrossRefGoogle Scholar
[Joc68]Jockusch, C.G. Jr., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[MC85]McEvoy, K. and Cooper, S. B., On minimal pairs of enumeration degrees, this Journal, vol. 50 (1985), pp. 983–1001.Google Scholar
[Pos44]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