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.