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

Notre Dame Journal of Formal Logic 43 (1):51-64 (2002)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 92,150

External links

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

Through your library

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.
Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
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.


Added to PP

34 (#471,489)

6 months
8 (#365,731)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Pairs of recursive structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
Pairs of computable structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
Turing degrees of certain isomorphic images of computable relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.

View all 16 references / Add more references