Series: Penn State Logic Seminar

 Date: Tuesday, November 15, 2005

 Time: 2:30 - 3:45 PM

 Place: 106 McAllister Building

 Speaker: Stephen G. Simpson, Penn State, Mathematics

 Title: An Introduction to Degrees of Unsolvability, part 5


   In this talk I shall discuss the arithmetical hierarchy over the
   Baire space, omega^omega, noting in particular its close
   relationship with the hierarchy of open sets, closed sets, G_delta
   sets, F_sigma sets, ..., from descriptive set theory.  In addition,
   I shall point out that the arithmetical hierarchy over the Baire
   space behaves somewhat differently from the arithmetical hierarchy
   over the integers.  For instance, Post's Theorem fails in this
   context.  After that, I shall begin my discussion of basis theorems
   and mass problems.  Loosely speaking, the Basis Problem reads as
   follows.  Given a "tame" subset P of the Baire space which is
   nonempty, to find a "tame" member of P.  I shall present various
   solutions to the Basis Problem in the case when P is a recursively
   bounded Pi^0_1 subset of the Baire space.