Presentations of the successor relation of computable linear ordering
type: Item
instance of: scholarly article
title: Presentations of the successor relation of computable linear ordering
zbMATH Open document ID: 1218.03029
DOI: 10.3103/S1066369X10070078
author: A. N. Frolov
published in: Russian Mathematics
publication date: 2011-01-25T00:00:00Z
review text: 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.
reviewed by: Rodney G. Downey
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 5840945
zbMATH Keywords: computable linear ordering
zbMATH Keywords: successor relation
zbMATH Keywords: degree spectrum
MaRDI profile type: Publication
cites work: Degree spectra of relations on computable structures in the presence of Δ20isomorphisms
cites work: Degree spectra of the successor relation of computable linear orderings
cites work: Recursive Linear Orders with Incomplete Successivities
Recommended article: Degree spectra of the successor relation of computable linear orderings
Recommended article: Computable linear orders and the ershov hierarchy
Recommended article: A note on \(\Delta_2^0\)-spectra of linear orderings and degree spectra of the successor relation
Recommended article: Computable linear orders and the Ershov hierarchy
Recommended article: Q4630794
Recommended article: ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS
Recommended article: Spectra of high\(_n\) and non-low\(_n\) degrees
Recommended article: The \(\Delta_2^0\)-spectrum of a linear order
Recommended article: Degrees of relations on ordinals
Recommended article: Limitwise monotonic sets of reals
description: scientific article; zbMATH DE number 5840945