The Medvedev and Muchnik lattices of Pi(0/1) classes

This thesis contains four chapters including the Introduction. It is an analysis of the structure of the Medvedev and Muchnik lattices of non-empty II01 classes of 2o. These two structures are denoted PM and Pw respectively. PM and Pw are countable, distributive lattices each with a maximum and minimum element.; Chapter 2 has been accepted for publication in Mathematical Logic Quarterly [4]. Its main result is a proof that every finite distributive lattice can be embedded into PM and Pw . Further, given any special II01 subset P ⊆ 2o, any finite distributive lattice can be embedded into PM and Pw with its maximal element going to P. As a corollary, any non-zero Muchnik or Medvedev degree is the least upper bound of two strictly lower degrees. The result can be extended further for PM . We show that given any P > M Q, any finite distributive lattice can be embedded between P and Q with its top element going to P .; The second part of Chapter 2 deals with a model theoretic consequence of these theorems. Here it is shown that both PM and Pw have decidable ∃-theories.; Chapter 3 also deals with lattice embeddings, but this time of countable lattices. We use similar techniques to those used in [17]. The two main countable lattices that we deal with are FD(o) and FB(o)---the free distributive lattice on ℵ0 generators and the free Boolean algebra on ℵ0 generators respectively. It is shown that, in PM , FD(o) can be embedded below any non-zero element of the lattice. Similarly, we show that in the Muchnik lattice, FB (o) can be embedded below any non-zero element.; The second result is stronger as any countable distributive lattice can be embedded into FB(o), and this is not the case for FD(o). We do, however, show that the distributive lattice of finite (co-finite) subsets of o can be embedded into PM below any non-zero element.; Chapter 4 examines the relationship between certain structural properties of II01 classes and their Muchnik and Medvedev degrees. Two structural properties--- smallness and very smallness---are defined and examined. We show that the class of II01 classes that contain a small (very small) subset forms a non-trivial proper prime ideal in Pw and PM . We also look at the relationship between smallness, very smallness and the well-studied property of thinness. We show there are thin sets that are not very small and vice-versa as well as other results of this sort.