Theodore Slaman's Guide to Computability & Definability: Theory & Applications 📚

We will start with an overview of the mathematical study of definability. In the context of sets of integers, we will discuss computability, the Halting Problem and its associated operation the Turing jump, arithmetic and hyperarithmetic hierarchies. In the context of the real numbers, the objects are directly related to topological complexity, such as a function’s being continuous or a set’s being Borel. We will include proofs of several basic theorems chosen to illustrate the basic methods of the area. In the pure theory of definability, we will discuss Martin’s Conjecture, which gives a precise sense in which this analysis of definability is intrinsic and inevitable. We will outline two case studies in which the theory of definability is used to study phenomena whose origins are external to mathematical logic: normality to integer bases and Hausdorff dimension.