Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Recursive linear orders with incomplete successivities

Authors: Rodney G. Downey and Michael F. Moses
Journal: Trans. Amer. Math. Soc. 326 (1991), 653-668
MSC: Primary 03D45; Secondary 03C57, 06A05
MathSciNet review: 1005933
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] R. Downey and C. Jockusch, $ T$-degrees, jump classes and strong reducibilities, Trans. Amer. Math. Soc. 301 (1987), 103-137. MR 879565 (88c:03045)
  • [2] R. Downey and M. Moses, On choice-sets and strongly non-trivial self-embeddings of recursive linear orders, Z. Math. Logik. Grundlagen Math. 35 (1989), 237-246. MR 1000966 (90j:03085)
  • [3] L. Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365-373. MR 0282805 (44:39)
  • [4] -, The strong homogeneity conjecture, J. Symbolic Logic 35 (1970), 375-377. MR 0286655 (44:3864)
  • [5] R. Friedberg and H. Rogers, Reducibility and completeness for sets of integers, Z. Math. Logik. Grundlagen Math. 5 (1959), 117-125. MR 0112831 (22:3682)
  • [6] S. Goncharov, Some properties of the constructivization of Boolean algebras, Sibirsk. Math. Zh. 16 (1975), 203-214.
  • [7] C. Jockusch, Reducibilities in recursive function theory, Ph. D. Thesis, MIT, 1966.
  • [8] C. Jockusch and R. Soare, Degrees of orderings not isomorphic to recursive linear orderings, Ann. Pure Appl. Logic (to appear). MR 1104053 (92c:03051)
  • [9] M. Moses, Recursive properties of isomorphism types, Ph. D. Thesis, Monash University, 1983. MR 687333 (84g:03067)
  • [10] J. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), 572-593. MR 627907 (83a:03042)
  • [11] -, Recursive Boolean algebras with recursive sets of atoms, J. Symbolic Logic 46 (1981), 596-616.
  • [12] J. Rosenstein, Linear orderings, Academic Press, 1982. MR 662564 (84m:06001)
  • [13] D. Roy and R. Watnick, Finite condensations of recursive linear orders, Ann. Pure Appl. Logic (to appear). MR 999784 (90e:03056)
  • [14] R. Soare, Recursively enumerable sets and degrees, Springer-Verlag, 1987. MR 882921 (88m:03003)
  • [15] R. Watnick, A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings, J. Symbolic Logic 49 (1984), 563-569. MR 745385 (85i:03152)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D45, 03C57, 06A05

Retrieve articles in all journals with MSC: 03D45, 03C57, 06A05

Additional Information

Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society