On the complexity of the successivity relation in computable linear orderings

Abstract. In this paper, we solve a long-standing open ques-tion (see, e.g., Downey [6, §7] and Downey and Moses [11]), about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering L has in-finitely 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 ∆03-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of independent interest. It would seem to promise many further applications