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.
Mathematical Logic at Penn State
Department of Mathematics