For more information about this meeting, contact Stephen Simpson, Jan Reimann.
|Title:||On the strength of Ramsey's Theorem without Sigma_1 induction|
|Speaker:||Keita Yokoyama, Tokyo Institute of Technology|
|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
Room Reservation Information
|Date:||08 / 07 / 2012|
|Time:||02:30pm - 03:45pm|