Open Access Te Herenga Waka-Victoria University of Wellington
thesis_access.pdf (835.25 kB)

On the Definability and Complexity of Sets and Structures

Download (835.25 kB)
posted on 2024-04-10, 05:19 authored by Linus Richter

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.


Copyright Date


Date of Award



Te Herenga Waka—Victoria University of Wellington

Rights License

Author Retains Copyright

Degree Discipline

Logic and Computation; Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level


Degree Name

Doctor of Philosophy

ANZSRC Socio-Economic Outcome code

280118 Expanding knowledge in the mathematical sciences

ANZSRC Type Of Activity code

1 Pure basic research

Victoria University of Wellington Item Type

Awarded Doctoral Thesis



Victoria University of Wellington School

School of Mathematics and Statistics


Turetsky, Daniel