Linearisations and the Ershov Hierarchy

S. Barry Cooper, James Gay, Charles Harris, Kyung Il Lee, Anthony Morphett

Research output: Contribution to journalArticle (Academic Journal)peer-review

281 Downloads (Pure)

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 ifit 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 ∆0/2 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 ∆0/2 level of the arithmetical hierarchy, but not at the ∆0/1 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 theproperty of not computably embedding a copy of ζ, the order type of the integers, byconstructing a computable partial ordering which does not embed ζ, but such thatevery ∆0/2 linear extension of the ordering does admit a computable embedding of ζ.
Original languageEnglish
Pages (from-to)143-169
Number of pages27
JournalComputability
Volume7
Issue number2-3
Early online date10 Oct 2017
DOIs
Publication statusPublished - 8 Jun 2018

Fingerprint Dive into the research topics of 'Linearisations and the Ershov Hierarchy'. Together they form a unique fingerprint.

Cite this