Linearisations and the Ershov Hierarchy

Charles Harris, University of Leeds. Part of the proofs, constructions and computations seminar series.

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 rationals. 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 Delta^0_2 - i.e. computable in the Halting Set - linear extension also satisfying the property. Thus, linear extensions of a computable partial order preserving the properties of computable well foundedness or computable scatteredness can always be found at the Delta^0_2 level of the arithmetical hierarchy, but not at the Delta^0_1 level. A natural question articulated by Barry Cooper, is to ask at what level of the Ershov hierarchy - which in turn gives a stratification of the Delta^0_2 sets - such linear extensions can be found. Barry Cooper and his research students Anthony Morphett, Kyung Il Lee and James Gay showed that, for both properties, every computable partial order satisfying the property has an omega-c.e. linear extension with the same property. James Gay subsequently established that this is the best possible result within the Ershov hierarchy by constructing, respectively, computably well founded and computably scattered partial orders which do not have n-c.e. linear extensions sharing the respective property, for any finite n.

In my talk I will introduce the Ershov Hierarchy and give an informal presentation of the computably well founded result.

Charles Harris, University of Leeds