Cuts of linear orders (Q651418): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s11083-010-9194-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1989804613 / rank | |||
Normal rank |
Revision as of 21:37, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cuts of linear orders |
scientific article |
Statements
Cuts of linear orders (English)
0 references
13 December 2011
0 references
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.
0 references
linear orders
0 references
ascending cut
0 references
descending cut
0 references
jump inversion
0 references