The proof-theoretic strength of Ramsey's theorem for pairs and two colors

11.02.2016 15:00 - 16:30

K. Yokoyama (Japan Adv. Institute of Science and Technology, Nomi, Ishikawa, JP and U Berkeley, US)

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

This is a joint work with Ludovic Patey.

Organiser:

KGRC

Location:
SR 101, 2. St., Währinger Str. 25