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

DOI:
https://doi.org/10.1090/S0002-9947-1991-1005933-2

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 -complete successivities.

**[1]**R. Downey and C. Jockusch, -*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)**

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

DOI:
https://doi.org/10.1090/S0002-9947-1991-1005933-2

Article copyright:
© Copyright 1991
American Mathematical Society