Tutorial on Mass Problems

Stephen G. Simpson Department of Mathematics Pennsylvania State University

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

September 12, 2006

This note consists of an abstract and bibliography for an invited tutorial, to be given as part of the Third International Conference on Computability and Complexity in Analysis, November 1–5, 2006, in Gainesville, Florida, USA.

Abstract

Let P be a set of reals viewed as a mass problem, i.e., a “decision problem with more than one solution.” Here the “solutions” of P are the elements of P. Many unsolvable mathematical problems are best viewed as mass problems. One says that a mass problem P is weakly reducible to a mass problem Q if for every solution Y of Q there exists a solution X of P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Weak degrees are also known as Muchnik degrees.

Let P_{w} be the set of weak degrees of mass problems associated with nonempty Π_{1}^{0} subsets of 2^{ω}, partially ordered by weak reducibility. Algebraically, it is easy to see that P_{w} is a countable distributive lattice with top and bottom. Simpson and others have studied the lattice P_{w} in a series of publications beginning in 1999. Our principal findings are as follows.

1. There is a natural embedding of E_{T}, the countable semilattice of recursively enumerable Turing degrees, into the lattice P_{w}. This embedding is one-to-one and preserves the semilattice structure and the top and bottom. We identify E_{T} with its image in P_{w} under this embedding.

2. Like the semilattice E_{T}, the lattice P_{w} is structurally rich. In particular, any countable distributive lattice is lattice-embeddable in any nontrivial initial segment of P_{w}. Moreover, the P_{w} analog of the Sacks Splitting Theorem holds. These structural results are proved by means of priority arguments. The P_{w} analog of the Sacks Density Theorem remains as an open problem.

3. Unlike E_{T}, the lattice P_{w} contains a large number of specific, natural degrees other than the top and bottom degrees. These specific, natural degrees in P_{w} arise from foundationally interesting topics such as reverse mathematics, algorithmic randomness, subrecursive hierarchies, computational complexity, and hyperarithmeticity.

4. The known specific, natural degrees in P_{w} are disjoint from the recursively enumerable Turing degrees in E_{T}. The only exceptions are the top and bottom degrees in E_{T}, which are the same as the top and bottom degrees in P_{w}.

References

[1] Stephen Binns. A splitting theorem for the Medvedev and Muchnik lattices. Mathematical Logic Quarterly, 49:327–335, 2003.

[2] Stephen Binns and Stephen G. Simpson. Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes. Archive for Mathematical Logic, 43:399– 414, 2004.

[3] C.-T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors. Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20 – August 15, 2005. Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific Publishing Company, Ltd. In preparation, 2006, to appear.

[4] Joshua Cole and Stephen G. Simpson. Mass problems and hyperarithmeticity. In preparation, 2006, to appear.

[5] FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/,

September 1997 to the present.

[6] A. A. Muchnik. On strong and weak reducibilities of algorithmic problems. Sibirskii Matematicheskii Zhurnal, 4:1328–1341, 1963. In Russian.

[7] Stephen G. Simpson. FOM: natural r.e. degrees; Pi01 classes. FOM e-mail list [5], August 13, 1999.

[8] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005.

[9] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society. Preprint, 15 pages, August 10, 2004; accepted for publication July 4, 2006.

[10] Stephen G. Simpson. FOM: natural r.e. degrees. FOM e-mail list [5], February 27, 2005.

[11] Stephen G. Simpson. Some fundamental issues concerning degrees of unsolvability. In [3]. Preprint, 21 pages, 2006, to appear.

[12] Stephen G. Simpson. Mass problems and almost everywhere domination. In preparation, 2006, to appear.