The $Delta^0_2$-Spectrum of a Linear Order

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


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 $\Delta^0_2$ degree, but not 0. Since our argument requires the technique of permitting below a $\Delta^0_2$ set, we include a detailed explanation of the mechanics and intuition behind this type of permitting

Download options


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

External links

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

Through your library


Added to PP

7 (#1,075,902)

6 months
1 (#387,390)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references

Citations of this work

No citations found.

Add more citations

Similar books and articles