On the elementary theories of the Muchnik and Medvedev lattices of Π⁰₁ classes

Recently, researchers in the foundations of mathematics have become interested in the distributive lattices P_w and P_s, the study of which is a major part of the field of "mass problems." In general, a mass problem U is a subset of ω^ω (Baire space). We define U ≤_s V if there is an index e for a computable functional so that for all f ∈ V, Φ_e^f ∈ U. If we do not require the same e for every f, we get a "weak version": U &le_w V if for all f ∈ V, there is an e so that Φ_e^f ∈ U.

The relations ≤_s and ≤_w naturally induce equivalence relations ≡_s and ≡_w. We define P_s to be the collection of ≡_s degrees of nonempty Π⁰₁ subsets of 2^ω (Cantor space); similarly, we define P_w to be the collection of ≡_w degrees of nonempty Π⁰₁ subsets of 2^ω.

An important open question is whether P_w is dense. The result of Chapter 2 is that the embedding of the free distributive lattice on countably many generators into P_s can be done densely. The way it is done gives indirect evidence that the kinds of priority arguments that show the density of P_s are probably not strong enough to show the density of P_w. The result of Chapter 3 applies these priority arguments to show the decidability of the elementary ∀∃-theory of P_s as a partial order. The result of Chapter 5 is that certain index sets related to P_w are Π¹₁-complete. This leads to a conjecture that the Turing degree of its elementary theory is as high as possible.