This thesis comprises one chapter (plus this introduction) and two appendices. Chapter \ref{computability theory of ec groups} appears, with minor modifications, as a stand-alone paper. The first appendix is joint work with Caroline Terry and presents a new proof of an asymptotic upper bound on the number of conjugacy classes in the upper unitriangular matrices. The result is known and the technique itself is not novel enough to warrant a paper, but the author hopes that it may still be of some interest. The second appendix is an expository introduction to model-theoretic forcing and its computability-theoretic strength.
Existentially closed groups are, informally, groups that contain solutions to every consistent finite system of equations and inequations. They were introduced in 1951 in an algebraic context and subsequent research elucidated deep connections with group theory, model theory, and computability theory. In Chapter \ref{computability theory of ec groups}, we continue this investigation, with particular emphasis on illuminating the relationship with computability theory.
In particular, we show that existentially closed groups can be built at the level of the halting problem and that this is optimal (Theorem \ref{existence of ec groups is at level of hp}). Moreover, using the the theory of the enumeration degrees and some work of Martin Ziegler in computable group theory, we show that the previous result relativises in a somewhat subtle way (Theorem \ref{relativisation of existence of ec group is level of hp}). We then tease apart the complexity contributed by ``global'' and ``local'' structure, showing that the finitely generated subgroups have complexity at the level of the PA degrees (Theorem \ref{every scott set gives an ec group}). Finally, we investigate the computability-theoretic complexity of omitting the non-principal quantifier-free types from a list of types, from which we obtain an upper bound on the complexity of building two existentially closed groups that are ``as different as possible'' (Theorem \ref{rel atomic groups below ce}).

Details

Title
A Computability-Theoretic Investigation into Existentially Closed Groups