Measure-theoretic Uniformity and the Suslin Functional

Abstract

Given a set A in the unit interval and the associated Lebesgue measure λ, it is a natural question whether we may (in some sense) compute the measure λ(A) in terms of the set A. Under the moniker measure theoretic uniformity, Tanaka and Sacks have (independently) provided a positive answer for the well-known class of hyperarithmetical sets of reals, and provided a basis theorem for such sets of positive measure. The hyperarithmetical sets are exactly the sets computable in terms of the functional 2E, in the sense of Kleene’s S1–S9. In turn, Kleene’s 2E essentially corresponds to arithmetical comprehension as in ACA0. In this paper, we generalise the aforementioned results to the ‘next level’, namely Π11-CA0, in the form of the Suslin functional, or the equivalent hyperjump. We also generalise the Tanaka-Sacks basis theorem to sets of positive measure that are semi-computability relative to the Suslin functional. Finally, we discuss similar generalisations for infinite time Turing machines.