Abstract

It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low degree. Finally, an analogue of the recursion theorem for recursive linear orderings is refuted