Series: Penn State Logic Seminar

Date: Tuesday, June 7, 2005

Time: 2:30 - 3:45 PM

Place: 123 Pond Laboratory

Speaker: Chi-Tat Chong, Mathematics, National University of Singapore

Title: 

  Ramsey's Theorem and Sigma_2 Induction

Abstract:

  Ramsey's Theorem states that every k-coloring of n-element subsets
  of the natural numbers is monochromatic on an infinite subset. The
  relation between Ramsey's Theorem and first order mathematical
  induction, over the base theory RCA_0, is of interest from the
  reverse mathematics point of view.  Hirst (1987) proved that over
  RCA_0, Ramsey's Theorem for pairs implies Sigma_2 bounding
  (BSigma_2). In this talk, we show that the stronger inductive scheme
  ISigma_2 is a consequence of this axiom system, answering a question
  posed by Cholak, Jockusch and Slaman.