Degree spectra of the successor relation of computable linear orderings

Archive for Mathematical Logic 48 (1):7-13 (2009)

Valentina Harizanov
George Washington University
We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees
Keywords Mathematics   Algebra   Mathematics, general   Mathematical Logic and Foundations
Categories (categorize this paper)
DOI 10.1007/s00153-008-0110-6
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,031
Through your library

References found in this work BETA

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Recursive Isomorphism Types of Recursive Boolean Algebras.J. B. Remmel - 1981 - Journal of Symbolic Logic 46 (3):572-594.
Every Recursive Boolean Algebra is Isomorphic to One with Incomplete Atoms.Rod Downey - 1993 - Annals of Pure and Applied Logic 60 (3):193-206.

View all 7 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
The $Delta^0_2$-Spectrum of a Linear Order.Russell Miller - 2001 - Journal of Symbolic Logic 66 (2):470-486.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
On Lachlan’s Major Sub-Degree Problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.


Added to PP index

Total views
24 ( #334,118 of 2,236,309 )

Recent downloads (6 months)
19 ( #35,848 of 2,236,309 )

How can I increase my downloads?


My notes

Sign in to use this feature