Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-04T21:20:50.472Z Has data issue: false hasContentIssue false

Cupping Δ20 enumeration degrees to 0e

Published online by Cambridge University Press:  01 February 2009

MARIYA IVANOVA SOSKOVA
Affiliation:
Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom Email: [email protected]
GUOHUA WU
Affiliation:
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 639798, Republic of Singapore Email: [email protected]

Abstract

In this paper we prove that every non-zero Δ20e-degree is cuppable to 0e′ by a 1-generic Δ20e-degree (and is thus low and non-total), and that every non-zero ω-c.e. e-degree is cuppable to 0e′ by an incomplete 3-c.e. e-degree.

Type
Paper
Copyright
Copyright © Cambridge University Press 2009

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

Cooper, S. B. (1982) Partial degrees and the density problem. J. Symb. Log. 47 854859.CrossRefGoogle Scholar
Cooper, S. B. (1984) Partial Degrees and the density problem, part 2: the enumeration degrees of the Σ2 sets are dense. J. Symb. Log. 49 503513.CrossRefGoogle Scholar
Cooper, S. B. (1990) Enumeration reducibility, nondeterministic computations and relative computability of partial functions. In Recursion Theory Week, Oberwolfach 1989. Springer-Verlag Lecture Notes in Mathematics 1432 57110.CrossRefGoogle Scholar
Cooper, S. B. (2004) Computability Theory, Chapman and Hall/CRC Mathematics.Google Scholar
Cooper, S. B. and Copestake, C. S. (1988) Properly Σ2 enumeration degrees. Zeits. f. Math. Logik. u. Grundl. der Math. 34 491522.CrossRefGoogle Scholar
Cooper, S. B., Sorbi, A. and Yi, X. (1996) Cupping and noncupping in the enumeration degrees of Σ20 sets. Ann. Pure Appl. Logic 82 317342.CrossRefGoogle Scholar
Copestake, K. (1988) 1-Genericity enumeration Degrees. J. Symb. Log. 53 878887.CrossRefGoogle Scholar
Copestake, K. (1990) 1-Genericity in the enumeration degrees below 0e′. In: Petkov, P. P. (ed.) Mathematical Logic, Plenum Press 257265.CrossRefGoogle Scholar
Gutteridge, L. (1971) Some Results on Enumeration Reducibility, Ph.D. thesis, Simon Fraser University.Google Scholar
Soare, R. I. (1987) Recursively enumerable sets and degrees, Springer-Verlag.CrossRefGoogle Scholar
Soskova, M. and Wu, G. (2007) Cupping Δ20 enumeration degrees to 0e (extended abstract). In: Computability in Europe 2007. Springer-Verlag Lecture Notes in Computer Science 4497 727738.CrossRefGoogle Scholar