Series: Penn State Logic Seminar

Date: Tuesday, September 11, 2001

Time: 2:30 - 3:45 PM

Place: 306 Boucke Building

Speaker: Stephen Binns, Mathematics, Penn State

Title: Medvedev Degrees of Pi01 Subsets of 2omega


Let P and Q be subsets of 2^omega, the space of infinite sequences of
0's and 1's.  P is said to be Medvedev reducible to Q if there exists
a Turing computable functional which carries members of Q to members
of P.  P and Q are said to be of the same Medvedev degree if each is
Medvedev reducible to the other.  The partial ordering of Medvedev
degrees under Medvedev reducibility turns out to be a distributive
lattice.  The sublattice consisting of Medvedev degrees of Pi^0_1
subsets of 2^omega turns out to have a rich structure, which has been
explored in recent research by Binns and Simpson.