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