Series: Penn State Logic Seminar
Date: Tuesday, March 4, 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 1
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]. We present
a variety of results and techniques which have been useful in recent
investigations.

Lecture notes are available here.