A survey of basis theorems

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/ simpson@math.psu.edu

December 12, 2012

This is my abstract for the Workshop on Computability Theory and Foundations of Mathematics, to be held in Tokyo, February 18–20, 2013.

A basis theorem is a theorem of the form “Every nonempty effectively closed set in an effectively compact metric space contains at least one point which is, in some specific sense, close to being computable.” Some well known basis theorems are the Low Basis Theorem, the Hyperimmune-Free Basis Theorem, the R.E. Basis Theorem, the Cone Avoidance Basis Theorem, and the Randomness Preservation Basis Theorem. Less well known is a recent basis theorem due to Higuchi/Hudelson/Simpson/Yokoyama concerning preservation of partial randomness. In this talk we shall state these basis theorems, sketch some of their proofs, and discuss the possibilities for combining them in various ways. We shall present some new results and open problems.