Degree Spectra of Relations on a Cone
Degree Spectra of Relations on a Cone
by Matthew Harrison-Trainor
English | 2018 | ISBN: 1470428393 | 120 Pages | PDF | 1.26 MB
by Matthew Harrison-Trainor
English | 2018 | ISBN: 1470428393 | 120 Pages | PDF | 1.26 MB
Let A be a mathematical structure with an additional relation R. The author is interested in the degree spectrum of R, either among computable copies of A when (A,R) is a “natural” structure, or (to make this rigorous) among copies of (A,R) computable in a large degree d. He introduces the partial order of degree spectra on a cone and begin the study of these objects. Using a result of Harizanov—that, assuming an effectiveness condition on A and R, if R is not intrinsically computable, then its degree spectrum contains all c.e. degrees—the author shows that there is a minimal non-trivial degree spectrum on a cone, consisting of the c.e. degrees.