slideshow 3

Logic seminar

In search of the first-order part of Ramsey's theorem for pairs

Leszek Kołodziejczyk
University of Warsaw


Monday, 16. May 2022 - 16:00 to 17:30
Online - - contact before the meeting to join
Reverse mathematics studies the logical strength of mathematical theorems formalized as statements in the language of second-order arithmetic (which is a two-sorted language with one sort of variables for natural numbers and another for sets of natural numbers). The strength is usually measured in terms of implications between the theorems and some set existence axioms, but it also makes sense to ask about the first-order consequences of a theorem, that is, what statements about natural numbers it implies.

In recent decades, a particularly interesting case study has been provided by RT^2_2: Ramsey's theorem for pairs and two colours. RT^2_2 and its variants are anomalous in the sense of not being equivalent to any of the typical set existence axioms considered in reverse mathematics, or to each other. Characterizing the first-order part of RT^2_2 is a long-standing and highly interesting open problem. Methods used to make progress on this problem have typically been based on some combination of recursion theory and nonstandard models of arithmetic, with the latter playing an increasingly important role.

I will briefly discuss some major results on the first-order part of RT^2_2 obtained over the years and then talk about some more recent work related to the problem that I have been involved in (jointly with Marta Fiori Carones, Kasia Kowalik, Keita Yokoyama and Tin Lok Wong).