Dissertations, Theses, and Capstone Projects

Date of Degree

6-2025

Document Type

Doctoral Dissertation

Degree Name

Doctor of Philosophy

Program

Mathematics

Advisor

Russell Miller

Committee Members

Johanna Franklin

Alfred Dolich

Roman Kossak

Subject Categories

Logic and Foundations

Keywords

Computability Theory, Computable Structure Theory, Profinite Groups, Presburger Arithmetic, Degree Spectra, Scott Analysis

Abstract

Profinite groups, which are exactly the Galois groups, are all either finite or uncountable. However, all second countable profinite groups can be presented as the set of paths through a countable tree. We use these tree presentations to find upper bounds on the complexity of the existential theories of profinite groups, as well as to prove sharpness for these bounds. These complexity results enable us to distinguish the class of profinite groups that are isomorphic to a direct product of finite groups, for which we find an upper bound on the complexity of the entire first order theory. Additionally, given a profinite subgroup $G$ and a Turing ideal $I$ we define $G_I$ to be the set of elements in $G$ whose Turing degree lies in $I$. We examine to what extent and under what conditions $G_I$ will be an elementary subgroup of $G$. In particular, we construct a profinite group whose subgroup of computable elements is not elementary even for existential formulas.

A Presburger group is just a model of Presburger Arithmetic, which is the first order theory of the structure $(\Z,+,<,0,1)$. We examine the possible degree spectra of these groups as well as the possible Scott ranks. The key to these results is the connection between linear orders, divisible ordered abelian groups and Presburger groups. We show how given a linear order $L$, one can construct a divisible ordered abelian group $V_L$ and a Presburger group $P_L=V_L\times \Z$ such that the degree spectra and Scott ranks of $L$, $V_L$ and $P_L$ are all nearly the same.

Download

Share

COinS