Cuts of linear orders
type: Item
instance of: scholarly article
title: Cuts of linear orders
zbMATH Open document ID: 1259.03055
author: Asher M. Kach
author: Antonio Montalbán
published in: Order
publication date: 2011-12-13T00:00:00Z
review text: 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.
reviewed by: Jennifer Chubb
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 5988074
zbMATH Keywords: linear orders
zbMATH Keywords: ascending cut
zbMATH Keywords: descending cut
zbMATH Keywords: jump inversion
MaRDI profile type: Publication
full work available at URL: s11083-010-9194-9
OpenAlex ID: W1989804613
cites work: Computability on linear orderings enriched with predicates
cites work: Computable structures and the hyperarithmetical hierarchy
cites work: Every Low Boolean Algebra is Isomorphic to a Recursive One
cites work: Boolean algebra approximations
cites work: On the $n$-back-and-forth types of Boolean algebras
cites work: Computable Boolean algebras
cites work: The \(\Delta_2^0\)-spectrum of a linear order
cites work: Notes on the Jump of a Structure
cites work: Q3949052
cites work: Recursive well-orderings
cites work: Every Low 2 Boolean Algebra has a Recursive Copy
cites work: A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
DOI: 10.1007/S11083-010-9194-9
description: scientific article; zbMATH DE number 5988074