#### Date of Degree

2012

#### Document Type

Dissertation

#### Degree Name

Ph.D.

#### Program

Mathematics

#### Advisor

Russell G. Miller

#### Committee Members

Roman Kossak

Joel David Hamkins

#### Subject Categories

Mathematics

#### Keywords

computable structure theory, algebraic structures

#### Abstract

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 S _{F} of F* is the set of polynomials in

*F[X]*which factor over

*F*, and the

*root set R*is the set of polynomials in

_{F}of F*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

*S*and the root set

_{F}*R*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}*F*, it is always the case that S

_{F}≤

_{1}R

_{F}, but there are algebraic fields

*F*where we have

*R*

_{F}\nleq

_{1}S

_{F}.

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* \lneq_{1}_{bT} *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 low_{n} 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* > 4. However, it is known that there exists a low_{5} 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 low_{4} 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 low_{4} Boolean algebra has a computable copy. That is, the spectrum of the subalgebra as a unary relation can contain a low_{4} 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 *n*th-jump degree above **0**^{(n)}, subalgebras of* B* considered as relations on* B* can have *n*th-jump degree strictly bigger than **0**^{(n)}.

#### Recommended Citation

Steiner, Rebecca M., "Reducibility, Degree Spectra, and Lowness in Algebraic Structures" (2012). *CUNY Academic Works.*

https://academicworks.cuny.edu/gc_etds/1408

## Comments

Digital reproduction from the UMI microform.