Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

The Carlson-Simpson Lemma in Reverse Mathematics


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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View