Reducibility, Degree Spectra, and Lowness in Algebraic Structures

This dissertation addresses questions in computable structure theory, which is a branch of mathematical logic hybridizing computability theory and the study of familiar mathematical structures. We focus on algebraic structures, which are standard topics of discussion among model theorists. The structures examined here are fields, graphs, trees under a predecessor function, and Boolean algebras. For a computable field F, the splitting set SF of F is the set of polynomials in F[X] which factor over F, and the root set RF of F is the set of polynomials in F[X] which have a root in F. Results of Fröhlich and Shepherdson from 1956 imply that for a computable field F, the splitting set SF and the root set RF are Turing-equivalent. Much more recently, in 2010, R. Miller showed that for algebraic fields, if we use a finer measure, the root set actually has slightly higher complexity: for algebraic fields F, it is always the case that SF ≤1 RF, but there are algebraic fields F where we have RF \nleq1 SF . In the first chapter, we compare the splitting set and the root set of a computable algebraic field under a different reduction: the bounded Turing (bT) reduction. We construct a computable algebraic field for which RN \lneq1bT SF. We also define a Rabin embedding g of a field into its algebraic closure, and for a computable algebraic field F, we compare the relative complexities of RF, SF, and g(F) under m-reducibility and under bT-reducibility. Work by R. Miller in 2009 proved several theorems about algebraic fields and computable categoricity. Also in 2009, A. Frolov, I. Kalimullin, and R. Miller proved some results about the degree spectrum of an algebraic field when viewed as a subfield of its algebraic closure. In the second chapter, we show that the same computable categoricity results also hold for finite-branching trees under the predecessor function and for connected, finitevalence, pointed graphs, and we show that the degree spectrum results do not hold for these trees and graphs. We also offer an explanation for why the degree spectrum results distinguish these classes of structures: although all three structures are algebraic structures, the fields are what we call effectively algebraic. Every lown Boolean algebra, for 1 ≤ n ≤ 4, is isomorphic to a computable Boolean algebra. It is not yet known whether the same is true for n \u3e 4. However, it is known that there exists a low5 subalgebra of the computable atomless Boolean algebra which, when viewed as a relation on the computable atomless Boolean algebra, does not have a computable copy. In the third chapter, we adapt the proof of this recent result to show that there exists a low4 subalgebra of the computable atomless Boolean algebra B which, when viewed as a relation on B, has no computable copy. This result provides a sharp contrast with the one which shows that every low4 Boolean algebra has a computable copy. That is, the spectrum of the subalgebra as a unary relation can contain a low4 degree without containing the degree 0, even though no spectrum of a Boolean algebra (viewed as a structure) can do the same. We also point out that unlike Boolean algebras as structures, which cannot have nth-jump degree above 0(n), subalgebras of B considered as relations on B can have nth-jump degree strictly bigger than 0(n)