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.
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.
Reviewer: M.M.Arslanov (Kazan’)
MSC:
| 03D25 | Recursively (computably) enumerable sets and degrees |
| 03D45 | Theory of numerations, effectively presented structures |
References:
| [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.; 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, (Lerman, M.; Schmerl, J. H.; Soare, R. I., Logic Year 1979-1980: University of Connecticut, Lecture Notes in Math., 859 (1981), Springer: Springer Berlin) · 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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
