CCR 2025 + JC
Date:
The family of finite subsets \(s\) of the natural numbers such that \( |s|=1+\min s\) is known as the Schreier barrier in combinatorics and Banach Space theory, and as the family of exactly \(\omega\)-large sets in Logic.
Instead of considering the infinite Ramsey’s theorem for colorings of pairs, triplets or more generally n-uplets, we can study colorings of the exactly \(\omega\)-large sets. The resulting statement is true but very strong from a computational and reverse mathematical point of view.
Similarly, in this presentation we will look at the generalizations to colorings of the exactly \(\omega\)-large sets of other (Ramsey-like) theorems such as Friedman’s Free Set and Thin Set theorems and of the Rainbow Ramsey’s theorem. Surprisingly, although all these theorems have a low computational power in the case of coloring of n-uplets (none of them being able to compute the halting set), their exactly \(\omega\)-large counterparts exhibits different behaviors, with the Thin Set and Free Set theorems versions being able to encode the \(\omega\)-th iteration of the Turing jump, while the Rainbow Ramsey’s theorem version still does not code the halting set.
This is a joint work with Lorenzo Carlucci, Oriola Gjetaj and Ludovic Levy Patey.