Kurt Gödel Research Center

2016 seminar talk: The proof-theoretic strength of Ramsey's theorem for pairs and two colors

Talk held by Keita Yokoyama (Japan Advanced Institute of Science and Technology, Nomi, Ishikawa, Japan and University of Berkeley, California, USA) at the KGRC seminar on 2016-02-11.

Abstract

In the study of reverse mathematics, determining the first-order strength of Ramsey's theorem for pairs and two colors ($RT^2_2$) is a long-term open problem. Hirst showed that $RT^2_2$ implies $\Sigma^0_2$-bounding and Cholak/Jockusch/Slaman showed that $RT^2_2$ is $\Pi^1_1$-conservative over $\Sigma^0_2$-indction. Note that the proof-theoretic strength of $\Sigma^0_2$-bounding is the same as that of $\Sigma^0_1$-induction, so the proof-theoretic strength (or consistency strength) of $RT^2_2$ is in between $\Sigma^0_1$-induction and $\Sigma^0_2$-indction. Recently, the project of deciding the first-order strength of $RT^2_2$ has been strongly carried out using forcing constructions or priority arguments on nonstandard models of $\Sigma^0_2$-bounding mainly by Chong, Slaman and Yang, and they proved in particular that $RT^2_2$ does not imply $\Sigma^0_2$-indction. In this talk, we use a hybrid of forcing construction, indicator arguments, and proof-theoretic technique to show that the $\Pi^0_3$-part of $RT^2_2$ is exactly the same as $\Sigma^0_1$-induction, thus, the proof-theoretic strength of $RT^2_2$ is exactly the same as $\Sigma^0_1$-induction.

This is a joint work with Ludovic Patey.