The -spectrum of a linear order

Journal of Symbolic Logic 66 (2):470-486 (2001)

Abstract

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Δ 0 2 degree, but not 0. Since our argument requires the technique of permitting below a Δ 0 2 set, we include a detailed explanation of the mechanics and intuition behind this type of permitting

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,856

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
24 (#478,982)

6 months
1 (#386,016)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Linear Orderings.Joseph G. Rosenstein - 1983 - Journal of Symbolic Logic 48 (4):1207-1209.

Add more references

Citations of this work

Degree Spectra and Immunity Properties.Barbara F. Csima & Iskander S. Kalimullin - 2010 - Mathematical Logic Quarterly 56 (1):67-77.
Computability of Homogeneous Models.Karen Lange & Robert I. Soare - 2007 - Notre Dame Journal of Formal Logic 48 (1):143-170.
Degree Spectra of Real Closed Fields.Russell Miller & Victor Ocasio González - 2019 - Archive for Mathematical Logic 58 (3-4):387-411.

View all 6 citations / Add more citations

Similar books and articles

The $Delta^0_2$-Spectrum of a Linear Order.Russell Miller - 2001 - Journal of Symbolic Logic 66 (2):470-486.
Adding a Cohen Real Adds an Entangled Linear Order.Yoshifumi Yuasa - 1993 - Archive for Mathematical Logic 32 (4):299-304.
Adding Linear Orders.Saharon Shelah & Pierre Simon - 2012 - Journal of Symbolic Logic 77 (2):717-725.
An Undecidable Linear Order That Is $N$-Decidable for All $N$.John Chisholm & Michael Moses - 1998 - Notre Dame Journal of Formal Logic 39 (4):519-526.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Recursive Linear Orders with Recursive Successivities.Michael Moses - 1984 - Annals of Pure and Applied Logic 27 (3):253-264.
The Continuous Spectra of Quantum Operators.Boris Leaf - 1982 - Foundations of Physics 12 (6):583-606.
Dwie koncepcje porządku.Michał Tempczyk - 1995 - Filozofia Nauki 1.
Complexity of Monodic Guarded Fragments Over Linear and Real Time.Ian Hodkinson - 2006 - Annals of Pure and Applied Logic 138 (1):94-125.
Linear Order and its Place in Grammar.Richard Wiese - 2003 - Behavioral and Brain Sciences 26 (6):693-694.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.