Series: Penn State Logic Seminar Date: Tuesday, March 26, 2002 Time: 2:30 - 3:45 PM Place: 113 McAllister Building Speaker: Stephen Binns, Penn State, Mathematics Title: A Splitting Theorem for Muchnik and Medvedev Degrees Abstract: Let P and Q be nonempty Pi^0_1 subsets of 2^omega. P is said to be Muchnik reducible to Q if for each Y in Q there exists X in P such that X is Turing reducible to Y. The Muchnik degree of P is the equivalence class of P under this equivalence relation: P is Muchnik reducible to Q, and Q is Muchnik reducible to P. The Muchnik degrees are partially ordered in the obvious way, by Muchnik reducibility. It is easy to see that the Muchnik degrees form a distributive lattice with 0 and 1. We prove that any nonzero Muchnik degree is the join of two smaller Muchnik degrees. A similar result is also obtained for Medvedev degrees.