Presentations of the successor relation of computable linear ordering
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.
- Degree spectra of the successor relation of computable linear orderings
- Computable linear orders and the ershov hierarchy
- A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation
- Computable linear orders and the Ershov hierarchy
- Degree spectra of unary relations on \langle \omega, \leq \rangle
- On the complexity of the successivity relation in computable linear orderings
- Spectra of high_n and non-low_n degrees
- The _2⁰-spectrum of a linear order
- Degrees of relations on ordinals
- Limitwise monotonic sets of reals
- Degree spectra of the successor relation of computable linear orderings
- Computable linear orders and the Ershov hierarchy
- Ranges of \(\eta \)-functions of \(\eta \)-like linear orderings
- Computable linear orders and the ershov hierarchy
- Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders
- A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation
- On the complexity of the successivity relation in computable linear orderings
- Corrigendum: "On the complexity of the successivity relation in computable linear orderings"
- Degree spectra of unary relations on \langle \omega, \leq \rangle
- Punctual 1-linear orders
- The complexity of the successor and the block relations on computable linear orders
This page was built for publication: Presentations of the successor relation of computable linear ordering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619461)
