zbMATH — the first resource for mathematics

Cuts of linear orders. (English) Zbl 1259.03055
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.

03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] Alaev, P.E., Thurber, J., Frolov, A.N.: Computability on linear orderings enriched with predicates. Algebra Logic 48(5), 313–320 (2009) · Zbl 1241.03055 · doi:10.1007/s10469-009-9067-8
[2] Ash, C.J., Knight, J.: Computable structures and the hyperarithmetical hierarchy. In: Studies in Logic and the Foundations of Mathematics, vol. 144. North-Holland, Amsterdam (2000) · Zbl 0960.03001
[3] Downey, R., Jockusch, C.G.: Every low Boolean algebra is isomorphic to a recursive one. Proc. Am. Math. Soc. 122(3), 871–880 (1994) · Zbl 0820.03019 · doi:10.1090/S0002-9939-1994-1203984-4
[4] Harris, K., Montalbán, A.: Boolean Algebra Approximations. (Submitted for publication) · Zbl 1341.03057
[5] Harris, K., Montalbán, A.: On the n-back-and-forth types of Boolean algebras. Trans. Am. Math. Soc. (to appear) · Zbl 1248.03067
[6] Hirschfeldt, D., Kach, A.M., Montalbán, A.: A Feiner Look at the Intermediate Degrees. (In preparation)
[7] Kach, A.M., Miller, J.S.: Embeddings of Computable Linear Orders. (In preparation)
[8] Knight, J.F., Stob, M.: Computable Boolean algebras. J. Symb. Logic 65(4), 1605–1623 (2000) · Zbl 0974.03041 · doi:10.2307/2695066
[9] Lerman, M.: On recursive linear orderings. Logic year 1979–80. In: Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80. Springer, Berlin (1981)
[10] Miller, R.: The $\(\backslash\)Delta\^0_2$ -spectrum of a linear order. J. Symb. Logic 66(2), 470–486 (2001) · Zbl 0992.03050 · doi:10.2307/2695025
[11] Montalbán, A.: Notes on the jump of a structure. Mathematical Theory and Computational Practice 372–378 (2009) · Zbl 1268.03043
[12] Rosenstein, J.G.: Linear orderings. In: Pure and Applied Mathematics, vol. 98. Academic, New York (1982) · Zbl 0488.04002
[13] Spector, M.: Recursive well orderings. J. Symb. Logic 20, 151–163 (1955) · Zbl 0067.00303 · doi:10.2307/2266902
[14] Thurber, J.J.: Every ${\(\backslash\)rm low}\(\backslash\)sb 2$ Boolean algebra has a recursive copy. Proc. Am. Math. Soc. 123(12), 3859–3866 (1995) · Zbl 0840.03024
[15] Watnick, R.: A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings. J. Symb. Logic 49(2), 563–569 (1984) · Zbl 0585.03015 · doi:10.2307/2274189
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.