Cuts of linear orders
The well-known low\({}_n\) conjecture for Boolean algebras purports that every low\({}_n\) Boolean algebra has a computable presentation. (A structure is low\({}_n\) if its atomic diagram is Turing-equivalent to the \(n\)th jump of a computable set.) Here the authors demonstrate that a certain class of linear orderings realizes this property. A descending cut of a linear ordering \(\mathcal L\) is a partition of \(\mathcal L\) as \(\mathcal J+\mathcal I\) where \(\mathcal I\) is non-empty and has no least element. Ascending cuts are defined symmetrically. The main result of this article is that the class of linear orderings with finitely many ascending or descending cuts has the property that, whenever such an ordering has a low\({}_n\) presentation, it has a computable presentation. They demonstrate the sharpness of their result from one perspective, by showing that there is a linear ordering with a single descending cut having a presentation of intermediate (neither low\({}_n\) nor high\({}_n\)) degree, but no computable presentation. They leave open another ``sharpness question: Does every low\({}_n\) linear ordering with \(\omega\)-many descending (or, symmetrically, ascending) cuts have a computable copy? Included is a classical characterization of linear orderings based on the number of cuts of the ordering: An ordering with finitely many cuts has a nice decomposition, and those with countably many are scattered. An effective study of condensations of linear orderings leads them to their main result.
- A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
- Boolean algebra approximations
- Computability on linear orderings enriched with predicates
- Computable Boolean algebras
- Computable structures and the hyperarithmetical hierarchy
- Every Low 2 Boolean Algebra has a Recursive Copy
- Every Low Boolean Algebra is Isomorphic to a Recursive One
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- Notes on the Jump of a Structure
- On the n-back-and-forth types of Boolean algebras
- Recursive well-orderings
- The _2⁰-spectrum of a linear order
- Computable linear orders and limitwise monotonic functions
- Degree spectra of structures
- Computable presentability of countable linear orders
- Scattered linear orderings with no computable presentation
- Notes on the Jump of a Structure
- Algebraic cuts
- THE SIMPLEST LOW LINEAR ORDER WITH NO COMPUTABLE COPIES
- On a computable presentation of low linear orderings
- Low scattered linear orders
- The coding theorems for linear orders
- A low scattered linear order of rank 2 without computable copy
This page was built for publication: Cuts of linear orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651418)
