On the Definability and Complexity of Sets and Structures

We prove results at the intersection of computability theory and set theory, broadly concerning notions of complexity in the sense of definability. We consider these in the contexts of problems in classical mathematics: in the first part of this thesis, we present the solution to a problem in uncountable computable structure theory concerning the construction of complicated uncountable free abelian groups, which was obtained in collaboration with Greenberg, Shelah, and Turetsky. In the second part, we turn towards fractal geometry and its connection with both descriptive set theory and algorithmic randomness. We construct a co-analytic set of reals which fails Marstrand’s Projection Theorem, a seminal result of classical fractal geometry and geometric measure theory. The construction uses computability-theoretical tools, in particular the notion of Kolmogorov complexity.