Series: Penn State Logic Seminar

Date: Tuesday, August 30, 2005

Time: 2:30 - 3:45 PM

Place: 106 McAllister Building

Speaker: Stephen G. Simpson, Penn State, Mathematics

Title: The Reverse Mathematics of Ramsey's Theorem

Abstract:

  Ramsey's Theorem reads as follows: If the k-element sets of natural
  numbers are assigned colors from a finite set of colors, then we can
  find an infinite set all of whose k-element subsets are assigned the
  same color.  It is known that Ramsey's Theorem fails computably, in
  the sense that one can construct a computable assignment of colors
  for which no computable infinite set satisfies the conclusion of the
  theorem.  Moreover, it is possible to measure the extent of the
  failure, using the concepts and methods of recursion theory (a.k.a.,
  computability theory) and reverse mathematics.  It turns out that
  Ramsey's Theorem for k = 3 or more requires the Halting Problem and
  is thus equivalent to ACA_0.  However, in the special case k = 2,
  the situation is different and more complicated.  We discuss recent
  research by Seetapun, Jockusch, and others.