Switch to: References

Add citations

You must login to add citations.
  1. Degrees of relations on canonically ordered natural numbers and integers.Nikolay Bazhenov, Dariusz Kalociński & Michał Wrocławski - forthcoming - Archive for Mathematical Logic:1-33.
    We investigate the degree spectra of computable relations on canonically ordered natural numbers $$(\omega,<)$$ ( ω, < ) and integers $$(\zeta,<)$$ ( ζ, < ). As for $$(\omega,<)$$ ( ω, < ), we provide several criteria that fix the degree spectrum of a computable relation to all c.e. or to all $$\Delta _2$$ Δ 2 degrees; this includes the complete characterization of the degree spectra of so-called computable block functions that have only finitely many types of blocks. Compared to Bazhenov (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Corrigendum: "On the complexity of the successivity relation in computable linear orderings".Rodney G. Downey, Steffen Lempp & Guohua Wu - 2017 - Journal of Mathematical Logic 17 (2):1792002.
    Download  
     
    Export citation  
     
    Bookmark  
  • On the complexity of the successivity relation in computable linear orderings.Rod Downey, Steffen Lempp & Guohua Wu - 2010 - Journal of Mathematical Logic 10 (1):83-99.
    In this paper, we solve a long-standing open question, about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations