Series: Penn State Logic Seminar

 Date: Tuesday, December 6, 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 7

 Abstract: 

   In this talk we introduce the idea of mass problems, which goes
   back to Kolmogorov.  Informally, a mass problem is a problem which
   may have more than one solution.  Formally, a mass problem is any
   subset P of the Baire space.  The "solutions" of P are the members
   of P, and to "solving" P means finding a member of P.  (For
   example, consider the following mass problem: to find a complete
   extension of Peano Arithmetic.  This problem is unsolvable, in the
   sense that there is no complete extension of Peano Arithmetic which
   is computable.  We may identify this problem with the set of
   complete extensions of Peano Arithmetic.)  If P and Q are mass
   problems, we say that P is weakly reducible to Q if for every g in
   Q there exists f in P such that f is Turing reducible to Q.  We say
   that P and Q are weakly equivalent if each is weakly reducible to
   the other.  The weak degree of P is the equivalence class of P
   under weak equivalence.  The weak degrees have an obvious partial
   ordering induced by weak reducibility.  The partial ordering of
   weak degrees includes the partial ordering of Turing degrees,
   because we may identify the Turing degree of f with the weak degree
   of the singleton set {f}.  We note some applications of Basis
   Theorems to the study of weak degrees and mass problems.