Degrees of orderings not isomorphic to recursive linear orderings
type: Item
instance of: scholarly article
title: Degrees of orderings not isomorphic to recursive linear orderings
zbMATH Open document ID: 0734.03026
DOI: 10.1016/0168-0072(91)90038-N
author: Carl G. jun. Jockusch
author: Robert I. Soare
published in: Annals of Pure and Applied Logic
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 4213970
zbMATH Keywords: degrees of unsolvability
zbMATH Keywords: recursive linear orderings
zbMATH Keywords: low degree
reviewed by: M. M. Arslanov
MaRDI profile type: Publication
cites work: Jumps of Orderings
cites work: Recursive Linear Orders with Incomplete Successivities
cites work: Degrees coded in jumps of orderings
cites work: Q3919702
cites work: Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets
cites work: Degrees of Structures
cites work: Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets
cites work: Q3819052
cites work: Recursive well-orderings
description: scientific article; zbMATH DE number 4213970