Presentations of the successor relation of computable linear ordering (Q619461): Difference between revisions

The author studies the problem of determining the possible degree spectrum of the adjacency relation in a computable linear ordering. An old question of Downey and Moses was whether a degree spectrum is always closed upwards. (That is, if a computable linear ordering has a copy with the adjacency relation having c.e.\ degree \({\mathbf a}\) then there would be computable copies where the adjacency relation had degree \({\mathbf b}\) for all c.e.\ degrees \({\mathbf b}\) above \({\mathbf a}\).) \textit{J. Chubb, A. Frolov} and \textit{V. Harizanov} gave an affirmative answer in the case that there was no least nor greatest adjacency [Arch. Math. Logic 48, No. 1, 7--13 (2009; Zbl 1161.03022)], and here Frolov also gives an affirmative answer for the special case of strongly \(\eta\)-like and non-\(\eta\)-like linear orderings. The latter case uses the fact that the ordering has an \(\omega\) or \(\omega^*\) subsequence, and the former uses the bound on the block size. The problem was recently solved affirmatively by \textit{R. Downey, S. Lempp} and \textit{G. Wu} [``On the complexity of the successivity relation in computable linear orderings'', J. Math. Log. 10, No.~1--2, 83--99 (2010)]. This solution makes use of the current paper.