Presentations of the successor relation of computable linear ordering (Q619461): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degree spectra of relations on computable structures in the presence of Δ<sub>2</sub><sup>0</sup>isomorphisms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degree spectra of the successor relation of computable linear orderings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursive Linear Orders with Incomplete Successivities / rank | |||
Normal rank |
Latest revision as of 17:30, 3 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Presentations of the successor relation of computable linear ordering |
scientific article |
Statements
Presentations of the successor relation of computable linear ordering (English)
0 references
25 January 2011
0 references
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.
0 references
computable linear ordering
0 references
successor relation
0 references
degree spectrum
0 references