Reducibility, Degree Spectra, and Lowness in Algebraic Structures

Author

Rebecca M. Steiner, Graduate Center, City University of New YorkFollow

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_F 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 S_F and the root set R_F 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 S_F ≤₁ R_F, but there are algebraic fields F where we have R_F \nleq₁ 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_1bT 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₅ 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₄ 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₄ Boolean algebra has a computable copy. That is, the spectrum of the subalgebra as a unary relation can contain a low₄ 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⁽ⁿ⁾, subalgebras of B considered as relations on B can have nth-jump degree strictly bigger than 0⁽ⁿ⁾.

Comments

Digital reproduction from the UMI microform.

Recommended Citation

Steiner, Rebecca M., "Reducibility, Degree Spectra, and Lowness in Algebraic Structures" (2012). CUNY Academic Works.
https://academicworks.cuny.edu/gc_etds/1408