Recursive linear orders with incomplete successivities. (English) Zbl 0813.03028
Summary: A recursive linear order is said to have intrinsically complete successivities if, in every recursive copy, the successivities form a complex set. We show (Theorem 1) that there is a recursive linear order with intrinsically complete successivities but (Theorem 2) that this cannot be a discrete linear order. We investigate the related issues of intrinsically non-low and non-semilow successivities in discrete linear orders. We show also (Theorem 3) that no recursive linear order has intrinsically wtt-complete successivities.
References:
| [1] | R. G. Downey and C. G. Jockusch Jr., T-degrees, jump classes, and strong reducibilities, Trans. Amer. Math. Soc. 301 (1987), no. 1, 103 – 136. · Zbl 0638.03039 |
| [2] | Rodney G. Downey and Michael F. Moses, On choice sets and strongly nontrivial self-embeddings of recursive linear orders, Z. Math. Logik Grundlag. Math. 35 (1989), no. 3, 237 – 246. · Zbl 0654.03032 · doi:10.1002/malq.19890350307 |
| [3] | Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365 – 374. · Zbl 0222.02048 · doi:10.2307/2270692 |
| [4] | L. Feiner, The strong homogeneity conjecture, J. Symbolic Logic 35 (1970), 375 – 377. · Zbl 0251.02042 · doi:10.2307/2270693 |
| [5] | Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117 – 125. · Zbl 0108.00602 |
| [6] | S. Goncharov, Some properties of the constructivization of Boolean algebras, Sibirsk. Math. Zh. 16 (1975), 203-214. · Zbl 0326.02033 |
| [7] | C. Jockusch, Reducibilities in recursive function theory, Ph. D. Thesis, MIT, 1966. |
| [8] | Carl G. Jockusch Jr. and Robert I. Soare, Degrees of orderings not isomorphic to recursive linear orderings, Ann. Pure Appl. Logic 52 (1991), no. 1-2, 39 – 64. International Symposium on Mathematical Logic and its Applications (Nagoya, 1988). · Zbl 0734.03026 · doi:10.1016/0168-0072(91)90038-N |
| [9] | Michael Moses, Recursive properties of isomorphism types, J. Austral. Math. Soc. Ser. A 34 (1983), no. 2, 269 – 286. · Zbl 0546.03025 |
| [10] | J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), no. 3, 572 – 594. · Zbl 0543.03031 · doi:10.2307/2273757 |
| [11] | -, Recursive Boolean algebras with recursive sets of atoms, J. Symbolic Logic 46 (1981), 596-616. · Zbl 0543.03032 |
| [12] | Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. · Zbl 0488.04002 |
| [13] | Dev K. Roy and Richard Watnick, Finite condensations of recursive linear orders, Studia Logica 47 (1988), no. 4, 311 – 317 (1989). · Zbl 0673.03034 · doi:10.1007/BF00671562 |
| [14] | Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. · Zbl 0667.03030 |
| [15] | Richard Watnick, A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings, J. Symbolic Logic 49 (1984), no. 2, 563 – 569. · Zbl 0585.03015 · doi:10.2307/2274189 |
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.
