Cuts of linear orders (Q651418): Difference between revisions

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.