Series: Penn State Logic Seminar

Date: Tuesday, March 25, 2003

Time: 2:30 - 3:45 PM

Place: 113 McAllister Building

Speaker: Stephen G. Simpson, Penn State, Mathematics

Title: Some Results Concerning Muchnik Degrees, part 2

Abstract: 

Let P and Q be sets of reals.  P is said to be Muchnik reducible to Q
if every member of Q Turing-computes a member of P.  A Muchnik degree
is an equivalence class of sets of reals under mutual Muchnik
reducibility.  It is easy to see that the Muchnik degrees form a
distributive lattice under the partial ordering induced by Muchnik
reducibility.  Call this lattice L.  We study not only L but also its
distributive sublattice L_0 consisting of the Muchnik degrees of
nonempty Pi^0_1 subsets of the closed unit interval [0,1].  

In part 1 we introduce L and L_0.  We also present Simpson's result
that any two nonempty Pi^0_1 subsets of [0,1] belonging to the top
element of L_0 are Turing degree isomorphic.

In part 2 we discuss some further topics concerning L_0: 1-random
reals, applications of the hyperimmune-free basis theorem,
applications of Arslanov's completeness criterion, the
Sigma^0_3/Pi^0_1 lemma, 2-random reals, DNR functions, embedding the
r. e. degrees.