Degree Spectra of Relations on Computable Structures

by Denis R. Hirschfeldt

Status: doctoral dissertation written at Cornell University under the supervision of Richard A. Shore

Availability: PDF

Abstract. The study of additional relations on computable structures began with the work of Ash and Nerode. The concept of degree spectra of relations was later introduced by Harizanov. In this thesis, several new examples of possible degree spectra of relations on computable structures are given. In particular, it is shown that for every c.e. degree a, the set {0,a} can be realized as the degree spectrum of a relation on a structure of computable dimension two, answering a question of Goncharov and Khoussainov. Some extensions of this result are given. Degree spectra of relations on computable models of particular algebraic theories are also investigated. For example, it is shown that, for every n, there is a computable integral domain with a subring whose degree spectrum consists of exactly n c.e. degrees including 0. In contrast to this result, it is shown, for instance, that the degree spectrum of a computable relation on a computable linear ordering is either a singleton or infinite. In both cases, sufficient criteria for similar results to hold of a given theory are provided.