Aspects of the Muchnik lattice

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

December 9, 2014

This is my abstract for a special session at the Annual Meeting of the Association for Symbolic Logic, to be held March 25–28, 2015 at the University of Illinois at Urbana-Champaign.

Let P and Q be sets of reals. Intuitively we may view a set of reals as a “problem,” namely, the problem of “finding” some real in the set. Accordingly, we say that P is Muchnik reducible to Q if for all y ∈ Q there exists x ∈ P such that x is Turing reducible to y. The Muchnik degree of P is the equivalence class of P under mutual Muchnik reducibility. Let D_{w} be the lattice of all Muchnik degrees, and let E_{w} be the sublattice consisting of the Muchnik degrees of nonempty, effectively closed (i.e., Π_{1}^{0}) sets of reals. It is well known that D_{w} is the natural completion of the upper semilattice D_{T} of Turing degrees. Similarly, E_{w} is a natural extension of the upper semilattice E_{T} of recursively enumerable Turing degrees. In a recent paper by Sankha S. Basu and the speaker, we show that the category of sheaves of sets over D_{w} is an interesting model of intuitionistic higher-order logic. We call this model the Muchnik topos. In recent work by Stephen E. Binns and Richard A. Shore and the speaker, we show that E_{w} is dense, i.e., for all p, q ∈ E_{w} such that p < q there exists r ∈ E_{w} such that p < r < q. We now sketch the proof of this latter result. The proof involves some hyperarithmetical theory.