Brown’s lemma in second-order arithmetic

Emanuele Frittaion¹

¹ Mathematical Institute Tohoku University Tohoku, Japan

Fundamenta Mathematicae, Tome 238 (2017) no. 3, pp. 269-283

Résumé

Brown’s lemma states that in every finite coloring of the natural numbers there is a homogeneous piecewise syndetic set. We show that Brown’s lemma is equivalent to $\mathsf {I}\Sigma ^0_2$ over $\mathsf {RCA}_0^*$. We show in contrast that (infinite) van der Waerden’s theorem is equivalent to $\mathsf {B}\Sigma ^0_2$ over $\mathsf {RCA}_0^*$. We finally consider the finite version of Brown’s lemma and show that it is provable in $\mathsf {RCA}_0$ but not in $\mathsf {RCA}_0^*$.

Détail

DOI : 10.4064/fm221-9-2016

Keywords: brown lemma states every finite coloring natural numbers there homogeneous piecewise syndetic set brown lemma equivalent mathsf sigma mathsf rca * contrast infinite van der waerden theorem equivalent mathsf sigma mathsf rca * finally consider finite version brown lemma provable mathsf rca mathsf rca *