Affiliations: [a] School of Mathematics, University of Leeds, Leeds LS2 9JT, U.K. | [b] School of Mathematics, University of Leeds, Leeds LS2 9JT, U.K.. [email protected] | [c] School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, U.K.. [email protected] | [d] Department of Mathematics and Statistics, Minnesota State University, 273 Wissink Hall, Mankato, MN 56001, U.S.A.. [email protected] | [e] School of Mathematics and Statistics, The University of Melbourne, Parkville 3010, Australia. [email protected]
Abstract: A partial order is computably well founded if it does not computably embed a copy of ω∗, the order type of the negative integers. It is computably scattered if it does not computably embed a copy of η, the order type of Q. It is known that, for each of these properties, there are computable partial orders satisfying the property which do not have a computable linear extension with the same property. Rosenstein showed, however, that for both of these properties, every computable partial order satisfying the property has a Δ20 linear extension also satisfying the property. Thus, linear extensions of a computable order preserving the properties of computable well foundedness or computable scatteredness can always be found at the Δ20 level of the arithmetical hierarchy, but not at the Δ10 level. In this paper, we investigate at which level of the Ershov hierarchy such linear extensions can be found. We show that, for both properties, every computable partial order satisfying the property has an ω-c.e. linear extension with the same property. We establish that this is the best possible result within the Ershov hierarchy by constructing, respectively, computably well founded and computably scattered orders which do not have n-c.e. linear extensions which are computably well founded and computably scattered respectively, for any n<ω. In a strengthening of Rosenstein’s theorems in another direction, we show that a linear extension preserving each of these properties can be computed using any oracle satisfying an escape property, which includes the class of non-generalised low2 sets. Finally, we show that the analogue of Rosenstein’s theorems do not hold for the property of not computably embedding a copy of ζ, the order type of the integers, by constructing a computable partial ordering which does not embed ζ, but such that every Δ20 linear extension of the ordering does admit a computable embedding of ζ.
Keywords: Computable, partial order, linear extension, well founded, scattered, Ershov hierarchy, arithmetical hierarchy
DOI: 10.3233/COM-170080
Journal: Computability, vol. 7, no. 2-3, pp. 143-169, 2018
