Linearisations and the Ershov hierarchy

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 ' " 2 0 linear extension also satisfying the property. Thus, linear extensions of a computable order preserving the properties of computable well foundedness or compu..