UC Berkeley

We examine the Carlson-Simpson Lemma (VW(k,l)), which is the combinatorial core of the Dual Ramsey Theorem, from the perspective of Reverse Mathematics. Our results include the following:

Working in the system BSigma_2^0, we carry out the construction of a failure of the ordered version of the Carlson-Simpson Lemma OVW(k,l), which was introduced in a paper by Miller and Solomon. This observation implies that we can construct such a recursive counterexample in the model of SRT_2^2 that was discussed in a recent paper by Chong, Slaman and Yang. It follows that SRT_2^2 does not prove OVW(k,l) over RCA_0.

We also show that the strength of the principle VW(k,l) is independent of the number of colors l being used.

By proving that VW(k,l) is not conservative over RCA_0 for arithmetical sentences, we conclude that VW(k,l) is not provable from any theory that is conservative over RCA_0 for arithmetical sentences.