zbMATH — the first resource for mathematics

Degrees of orderings not isomorphic to recursive linear orderings. (English) Zbl 0734.03026
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.

03D25 Recursively (computably) enumerable sets and degrees
03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] Ash, C.J.; Jockusch, C.G.; Knight, J.F., Jumps of orderings, Trans. amer. math. soc., 319, 573-599, (1990) · Zbl 0705.03022
[2] R.G. Downey and M. Moses, Recursive linear orders with incomplete successivities Trans. Amer. Math. Soc., to appear. · Zbl 0813.03028
[3] Knight, J.F., Degrees coded in jumps of orderings, J. symbolic logic, 51, 1034-1042, (1986) · Zbl 0633.03038
[4] Lerman, M., On recursive linear orderings, () · Zbl 0467.03045
[5] Maass, W., Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets, Trans. amer. math. soc., 279, 311-336, (1983) · Zbl 0546.03024
[6] Richter, L.J., Degrees of structures, J. symbolic logic, 46, 723-731, (1981) · Zbl 0512.03024
[7] Soare, R.I., Automorphisms of the lattice of recursively enumerable sets, part II: low sets, Ann. math. logic, 22, 69-107, (1982) · Zbl 0526.03022
[8] Soare, R.I., Recursively enumerable sets and degrees, (1987), Springer Berlin · Zbl 0667.03030
[9] Spector, C., Recursive well-orderings, J. symbolic logic, 20, 151-163, (1955) · Zbl 0067.00303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.