Mass Problems and Hyperarithmeticity

Stephen G. Simpson Department of Mathematics Pennsylvania State University

        http://www.math.psu.edu/simpson/

September 5, 2006

Note: This is an abstract of an invited talk, to be given at an American Mathematical Society special session, Computability Theory in Honor of Manuel Lerman’s Retirement, to be held October 28–29, 2006 in Storrs, Connecticut.

Abstract

A mass problem is a set of Turing oracles, viewed as a “decision problem with more than one solution”. A mass problem P is said to be weakly reducible to a mass problem Q if for each Y ∈ Q there exists X ∈ P such that X ≤_{T} Y. Beginning in 1999 Simpson and others studied the partial ordering P_{w} of mass problems associated with nonempty Π_{1}^{0} subsets of 2^{ω} under weak reducibility. One easily sees that P_{w} is a countable distributive lattice with 0 and 1. Simpson found a natural embedding of the recursively enumerable Turing degrees into P_{w} preserving ≤, ∨, 0,

1. In addition, Simpson showed that P_{w} contains many specific, natural degrees other than the recursively enumerable Turing degrees. These specific, natural degrees are related to foundationally interesting topics such as reverse mathematics, algorithmic randomness, subrecursive hierarchies, and computational complexity. Recently Simpson exhibited a new family of specific, natural degrees in P_{w} related to hyperarithmetic theory. Recently Simpson in joint work with Josh Cole showed that certain index sets associated with weak reducibility in P_{w} are Π_{1}^{1} complete.