Brown’s lemma in second-order arithmetic
Tom 238 / 2017
Fundamenta Mathematicae 238 (2017), 269-283
MSC: Primary 03B30; Secondary 11B75.
DOI: 10.4064/fm221-9-2016
Opublikowany online: 23 February 2017
Streszczenie
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 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^*.