The Medvedev and Muchnik Lattices of Pi-0-1 Classes
Open Access
- Author:
- Binns, Stephen Ernest
- Graduate Program:
- Mathematics
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 10, 2003
- Committee Members:
- Stephen George Simpson, Committee Chair/Co-Chair
Richard Beech Mansfield, Committee Member
William C Waterhouse, Committee Member
Dale Jacquette, Committee Member - Keywords:
- Medvedev
computability theory
recursion theory
Cantor space
Pi-0-1
Muchnik
recursive functional
small
very small
thin - Abstract:
- This thesis contains four chapters including the Introduction. It is an analysis of the structure of the Medvedev and Muchnik lattices of non-empty Pi-0-1 classes of the Cantor space. These two structures are denoted P_M and P_w respectively. P_M and P_w are countable, distributive lattices each with a maximum and minimum element. <p> <b> Chapter 2 </b> 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 P_M and P_w. Further, given any special Pi-0-1 subset, P, of the Cantor space, any finite distributive lattice can be embedded into P_M and P_w 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 P_M. We show that given any P strictly greater than Q in P_M, any finite distributive lattice can be embedded between P and Q with its top element going to P. <p> The second part of Chapter 2 deals with a model theoretic consequence of these theorems. Here it is shown that both P_M and P_w have decidable existence-theories. <p> <b> Chapter 3 </b> 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(omega) and FB(omega) - the free distributive lattice on countably many generators and the free Boolean algebra on countably generators respectively. It is shown that, in P_M, FD(omega) can be embedded below any non-zero element of the lattice. Similarly, we show that in the Muchnik lattice, FB(omega) can be embedded below any non-zero element. <p> The second result is stronger as any countable distributive lattice can be embedded into FB(omega), and this is not the case for FD(omega). We do, however, show that the distributive lattice of finite (co-finite) subsets of the natural numbers can be embedded into P_M below any non-zero element. <p> <b>Chapter 4 </b> examines the relationship between certain structural properties of Pi-0-1 classes and their Muchnik and Medvedev degrees. Two structural properties - "smallness" and "very smallness}" - are defined and examined. We show that the class of Pi-0-1 classes that contain a small (very small) subset forms a non-trivial proper prime ideal in P_w and P_M. 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.