Recursive linear orders with incomplete successivities
HTML articles powered by AMS MathViewer
- by Rodney G. Downey and Michael F. Moses
- Trans. Amer. Math. Soc. 326 (1991), 653-668
- DOI: https://doi.org/10.1090/S0002-9947-1991-1005933-2
- PDF | Request permission
Abstract:
A recursive linear order is said to have intrinsically complete successivities if, in every recursive copy, the successivities form a complete 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 oder. 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
- 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. MR 879565, DOI 10.1090/S0002-9947-1987-0879565-X
- 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. MR 1000966, DOI 10.1002/malq.19890350307
- Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365–374. MR 282805, DOI 10.2307/2270692
- L. Feiner, The strong homogeneity conjecture, J. Symbolic Logic 35 (1970), 375–377. MR 286655, DOI 10.2307/2270693
- Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117–125. MR 112831, DOI 10.1002/malq.19590050703 S. Goncharov, Some properties of the constructivization of Boolean algebras, Sibirsk. Math. Zh. 16 (1975), 203-214. C. Jockusch, Reducibilities in recursive function theory, Ph. D. Thesis, MIT, 1966.
- 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). MR 1104053, DOI 10.1016/0168-0072(91)90038-N
- Michael Moses, Recursive properties of isomorphism types, J. Austral. Math. Soc. Ser. A 34 (1983), no. 2, 269–286. MR 687333
- J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), no. 3, 572–594. MR 627907, DOI 10.2307/2273757 —, Recursive Boolean algebras with recursive sets of atoms, J. Symbolic Logic 46 (1981), 596-616.
- Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564
- Dev K. Roy and Richard Watnick, Finite condensations of recursive linear orders, Studia Logica 47 (1988), no. 4, 311–317 (1989). MR 999784, DOI 10.1007/BF00671562
- 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. MR 882921, DOI 10.1007/978-3-662-02460-7
- Richard Watnick, A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings, J. Symbolic Logic 49 (1984), no. 2, 563–569. MR 745385, DOI 10.2307/2274189
Bibliographic Information
- © Copyright 1991 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 326 (1991), 653-668
- MSC: Primary 03D45; Secondary 03C57, 06A05
- DOI: https://doi.org/10.1090/S0002-9947-1991-1005933-2
- MathSciNet review: 1005933