Degrees of relations on canonically ordered natural numbers and integers

Abstract We investigate the degree spectra of computable relations on canonically ordered natural numbers $$(\omega ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ω</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and integers $$(\zeta ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ζ</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . As for $$(\omega ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ω</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , we provide several criteria that fix the degree spectrum of a computable relation to all c.e. or to all $$\Delta _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Δ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> 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 et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022), we obtain a more general solution to the problem regarding possible degree spectra on $$(\omega ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ω</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , answering the question whether there are infinitely many such spectra. As for $$(\zeta ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ζ</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , we prove the following dichotomy result: given an arbitrary computable relation R on $$(\zeta ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ζ</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , its degree spectrum is either trivial or it contains all c.e. degrees. This result, and the proof techniques required to solve it, extend the analogous theorem for $$(\omega ,&lt;)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ω</mml:mi> <mml:mo>,</mml:mo> <mml:mo>&lt;</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> obtained by Wright (Computability 7:349–365, 2018), and provide initial insight to Wright’s question whether such a dichotomy holds on computable ill-founded linear orders. This article is an extended version of Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022).