${\Pi }_4^0$ conservation of a Carlson-Simpson lemma for 1-variable words

Abstract

Carlson and Simpson proved that for every finite coloring of the 1-variable words over a finite alphabet~$A$, there is an infinite $\omega$-variable word on which all the 1-variable words are monochromatic. This statement for $\ell$-colorings, written ${\mathsf{CSL}}_{\ell }^1$, is known to be strictly weaker than ${\mathsf{ACA}}_0$. We prove that ${\mathsf{RCA}}_0+{\mathsf{CSL}}_2^1$ is a $\forall {\Pi }_4^0$-conservative extension of ${\mathsf{RCA}}_0+\mathsf{B}Sigm{a}_2$. Among its consequences, it implies that neither the indivisibility of the universal triangle-free Henson graph for 2-colorings, nor the tree theorem for pairs and two colors, imply ${\Sigma }_2^0$-induction. This answers a question of Chong, Li, Wang and Yang.

33 pages