Series: Penn State Logic Seminar

Date: Tuesday, September 18, 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, part 2

Abstract: 

This is a continuation of last week's talk.  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
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.