ON EFFECTIVE CONSTRUCTIONS OF EXISTENTIALLY CLOSED GROUPS

Abstract 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 and computability theory. We continue this investigation, with particular emphasis on illuminating the relationship with computability theory. In particular, we show that there are existentially closed groups computable in the halting problem, and that this is optimal. Moreover, using the work of Martin Ziegler in computable group theory, we show that the previous result relativises in the enumeration degrees. We then tease apart the complexity contributed by “global” and “local” structure, showing that the complexity of finitely generated subgroups of existentially closed groups is captured by the PA degrees. 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”.