Series: Penn State Logic Seminar

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

 Abstract:

  In the previous talk we proved that Ramsey's Theorem for k = 3 fails
  computably, in the following strong sense: There is a computable
  assignment of colors to the 3-element sets of natural numbers such
  that, if X is any infinite set all of whose 3-element subsets are
  assigned the same color, then using X as a Turing oracle we can solve
  the Halting Problem.  We now prove a theorem of Seetapun showing that
  the situation for k = 2 is different.  Namely, given an unsolvable
  problem P, and given a computable assignment of colors to the
  2-element sets of natural numbers, we can find an infinite set X all
  of whose 2-element sets are assigned the same color, and such that P
  remains unsolvable allowing X as a Turing oracle.  The proof uses
  Mathias forcing over omega-models of weak subsystems of second order
  arithmetic.