Degrees of orderings not isomorphic to recursive linear orderings (Q810503)

The paper under review concerns the question: What degrees of unsolvability contain linear orderings which are not isomorphic to recursive linear orderings? It is known that for any degre \(\underset{\tilde{}} a\) such that \(\underset{\tilde{}} a''>\underset{\tilde{}} 0''\) there is a linear ordering of degree \(\underset{\tilde{}} a\) not isomorphic to any recursive ordering. The next natural question was raised by Julia Knight: Is every linear ordering of low degree isomorphic to a recursive linear ordering? Next, the authors prove two theorems which both give a negative answer to this question: Theorem 1. For any nonzero r.e. degree \(\underset{\tilde{}} c\) there is a linear ordering of degree \(\underset{\tilde{}} c\) which is not isomorphic to any recursive linear ordering. Theorem 2. There is a structure \(<A,<_ A,Inf>\) of low degree such that \(<\omega,<_ A>\) is a linear ordering not isomorphic to a recursive ordering. Here, on A, Inf(a,b)\(\Leftrightarrow \{c:\) \(a<_ Ac<_ Ab\) or \(b<_ Ac<_ Aa\}\) is infinite. Finally, an analogue of the recursion theorem for recursive linear orderings is refuted.