Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T09:17:36.778Z Has data issue: false hasContentIssue false
  • English
  • Français

Cupping Δ20 enumeration degrees to 0e′†

Published online by Cambridge University Press:  01 February 2009

MARIYA IVANOVA SOSKOVA  and
GUOHUA WU
MARIYA IVANOVA SOSKOVA
Affiliation:
Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom Email: mariya@maths.leeds.ac.uk
GUOHUA WU
Affiliation:
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 639798, Republic of Singapore Email: guohua@ntu.edu.sg
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 169 - 191
Copyright
Copyright © Cambridge University Press 2009

References

Cooper, S. B. (1982) Partial degrees and the density problem. J. Symb. Log. 47 854–859.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 503–513.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 57–110.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 491–522.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 317–342.CrossRefGoogle Scholar
Copestake, K. (1988) 1-Genericity enumeration Degrees. J. Symb. Log. 53 878–887.CrossRefGoogle Scholar
Copestake, K. (1990) 1-Genericity in the enumeration degrees below 0e′. In: Petkov, P. P. (ed.) Mathematical Logic, Plenum Press 257–265.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 727–738.CrossRefGoogle Scholar