Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures


Abstract
We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically invariant relation whose degree spectrum consists of all nontrivial r-degrees. We extend this construction to show that can be replaced by either or
Keywords degree spectra of relations   computable structures   computable model theory   hyperarithmetic hierarchy
Categories (categorize this paper)
DOI 10.1305/ndjfl/1071505769
Options
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,686
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Relative to Any Non-Hyperarithmetic Set.Noam Greenberg, Antonio Montalbán & Theodore A. Slaman - 2013 - Journal of Mathematical Logic 13 (1):1250007.

Add more citations

Similar books and articles

Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
The Extent of Computation in Malament–Hogarth Spacetimes.P. D. Welch - 2008 - British Journal for the Philosophy of Science 59 (4):659-674.
Development (and Evolution) of the Universe.Stanley N. Salthe - 2010 - Foundations of Science 15 (4):357-367.
Jack and Jill Have Shifted Spectra.Ned Block - 1999 - Behavioral and Brain Sciences 22 (6):946-947.

Analytics

Added to PP index
2010-08-24

Total views
16 ( #500,131 of 2,243,057 )

Recent downloads (6 months)
7 ( #254,385 of 2,243,057 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature