PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson, Jan Reimann.

Title:On the strength of Ramsey's Theorem without Sigma_1 induction
Seminar:Logic Seminar
Speaker:Keita Yokoyama, Tokyo Institute of Technology
Abstract:
Determining the strength of Ramsey's theorem RT^n_k is one of the crucial topics in the study of second-order arithmetic. It is well-known that RT^n_k (n>=3, k>=2) is equivalent to ACA_0 over RCA_0, and the first-order part of RT^2_2+RCA_0 is between BSigma_2 and ISigma_2 (Cholak/Jockusch/Slaman 2001). On the other hand, Simpson pointed out that Sigma^0_1-induction plays a key role to show RT^n_k implies ACA_0. Similarly, we use Sigma^0_1-induction essentially to prove BSigma_2 from RT^2_2+RCA_0. Then, what is the strength of RT^n_k without Sigma^0_1-induction? In this talk, I will show that the RT^n_k does not imply Sigma_1-induction over RCA_0*, a weaker base system for Reverse Mathematics.

Room Reservation Information

Room Number:MB315
Date:08 / 07 / 2012
Time:02:30pm - 03:45pm