# On the elementary theories of the Muchnik and Medvedev lattices of Π^{0}_{1} classes

_{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 Π^{0}_{1} subsets of 2^{ω} (Cantor space); similarly, we define P_{w} to be the collection of ≡_{w} degrees of nonempty Π^{0}_{1} 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 Π^{1}_{1}-complete. This leads to a conjecture that the Turing degree of its elementary theory is as high as possible.

## History

## Date Modified

2017-06-05## Defense Date

2009-09-10## Research Director(s)

Peter Cholak## Committee Members

Sergei Starchenko Julia Knight Steven Buechler## Degree

- Doctor of Philosophy

## Degree Level

- Doctoral Dissertation

## Language

- English

## Alternate Identifier

etd-12092009-114509## Publisher

University of Notre Dame## Program Name

- Mathematics