Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-03T08:18:58.200Z Has data issue: false hasContentIssue false
  • English
  • Français

Splitting and non-splitting in the difference hierarchy

Published online by Cambridge University Press:  20 June 2016

MARAT ARSLANOV
MARAT ARSLANOV*
Affiliation:
Department of Mathematics, Kazan Federal University, Kazan, Russia Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we investigate splitting and non-splitting properties in the Ershov difference hierarchy, in which area major contributions have been made by Barry Cooper with his students and colleagues. In the first part of the paper, we give a brief survey of his research in this area and discuss a number of related open questions. In the second part of the paper, we consider a splitting of 0′ with some additional properties.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Special Issue 3: Mind, Mechanism and Mathematics: Computability Unchained , March 2018 , pp. 384 - 391
Copyright
Copyright © Cambridge University Press 2016 

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

Arslanov, M.M. (1985). Structural properties of the degrees below 0′. Soviet Mathematics - Doklady N.S. 283 270–273.Google Scholar
Arslanov, M.M. (1988). On the upper semilattice of Turing degrees below 0′. Russian Mathematics (Iz. VUZ) 7 27–33.Google Scholar
Arslanov, M.M., Cooper, S.B. and Li, A. (2000). There is no low maximal d.c.e. degree. Mathematical Logic Quarterly 46 409–416.3.0.CO;2-P>CrossRefGoogle Scholar
Arslanov, M.M., Cooper, S.B. and Li, A. (2004). There is no low maximal d.c.e. degree - Corrigendum. Mathematical Logic Quarterly 50, 628–636.Google Scholar
Arslanov, M.M., Kalimullin, I.Sh. and Lempp, S. (2010). On Downey's conjecture. Journal of Symbolic Logic 75 401–441.CrossRefGoogle Scholar
Arslanov, M.M., Lempp, L. and Shore, R.A. (1996). On isolating r.e. and isolated d-r.e. degrees. In: London Math. Soc. Lect. Note Series 224 Cambridge University Press 61–80.Google Scholar
Cooper, S.B. (1971). Degrees of Unsolvability, Ph. D. Thesis, Leicester University, Leicester, England.Google Scholar
Cooper, S.B. (1990). The jump is definable in the structure of the degrees of unsolvability. Bulletin of the American Mathematical Society 23 151–158.Google Scholar
Cooper, S.B. (1991). The density of the Low2 n-r.e. degrees. Archive for Mathematical Logic 31 19–24.CrossRefGoogle Scholar
Cooper, S.B. (1992) A splitting theorem for the n-r.e. degrees. Proceedings of the American Mathematical Society 115 461–471.Google Scholar
Cooper, S.B., Harrington, L., Lachlan, A.H., Lempp, S. and Soare, R.I. (1991). The d-r.e. degrees are not dense. Annals of Pure and Applied Logic 55 125–151.CrossRefGoogle Scholar
Cooper, S.B. and Li, A. (2000a). Non-uniformity and generalised Sacks splitting. Acta Mathematica Sinica, English Series 18 327–334.Google Scholar
Cooper, S.B. and Li, A. (2002b). Splitting and cone avoidance in the d.c.e. degrees, Science in China (Series A) 45 1135–1146.Google Scholar
Cooper, S.B. and Li, A. (2002c). Turing definability in the Ershov hierarchy. Journal London Mathematical Society 66 513–528.Google Scholar
Downey, R.G. (1989). D.r.e. degrees and the Nondiamond theorem. Bulletin of the London Mathematical Society 21 43–50.CrossRefGoogle Scholar
Downey, R.A., Laforte, G.A. and Shore, R.I. (2003). Decomposition and infima in the computably enumerable degrees. Journal of Symbolic Logic 68 551–579.Google Scholar
Ershov, Y.L. (1968a). On a hierarchy of sets I. Algebra i Logika 7 (1) 47–73.Google Scholar
Ershov, Y.L. (1968b). On a hierarchy of sets II. Algebra i Logika 7 (4) 15–47.Google Scholar
Ershov, Y.L. (1970). On a hierarchy of sets III. Algebra i Logika 9 (1) 34–51.Google Scholar
Faizrakhmanov, M.Kh. (2010). Decomposability of low 2-computably enumerable degrees and Turing jumps in the Ershov hierarchy. Russian Mathematics (Iz. VUZ) 12 51–58 CrossRefGoogle Scholar
Gold, E.M. (1965). Limiting recursion. Journal of Symbolic Logic 30 28–48.Google Scholar
Miller, D. (1981). High recursively enumerable degrees and the anticupping property. In: Logic Year 1979–80, University of Connecticut 230–245.Google Scholar
Putnam, H. (1965). Trial and error predicates and the solution to a problem of Mostowski. Journal of Symbolic Logic 30 49–57.Google Scholar
Shore, R.A. (2000) Natural definability in degree structures. In: Cholak, P., Lempp, S., Lerman, M. and Shore, R. A. (eds.) Computability Theory and Its Applications: Current Trends and Open Problems. Contemporary Mathematics, AMS, Providence RI, 255–272.Google Scholar
Shore, R.A. and Slaman, T. A. (1999) Defining the Turing jump. Mathematical Research Letters 6 711–722.Google Scholar
Shore, R.A. and Slaman, T.A. (2001) Working below a low2 recursively enumerable degrees, Archive for Mathematical Logic 29 201–211.CrossRefGoogle Scholar
Welch, L. (1981) A Hierarchy of Families of Recursively Enumerable Degrees and a Theorem on Bounding Minimal Pairs, Ph. D. Thesis, University of Illinois, Urbana, 1981.Google Scholar