Recursive linear orders with incomplete successivities

Downey, Rodney G.; Moses, Michael F.

doi:10.1090/S0002-9947-1991-1005933-2

Recursive linear orders with incomplete successivities
HTML articles powered by AMS MathViewer

by Rodney G. Downey and Michael F. Moses PDF

Trans. Amer. Math. Soc. 326 (1991), 653-668 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

Some properties of the constructivization of Boolean algebras

16

Reducibilities in recursive function theory

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

46

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