Strength of the Carlson–Simpson Lemma

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Work in second-order arithmetic over $\mathsf{RCA}_0$, the base theory with $\Delta^0_1$ comprehension and $\Sigma^0_1$ induction. The strength of a principle means which subsystems prove it and which subsystems it implies over that base; equivalence requires both implications. Let $A$ be a finite nonempty alphabet and $\mathbb N_0=\{0,1,2,\ldots\}$. An infinite variable word $W$ is a sequence in $A\cup\{x_i:i\in\mathbb N_0\}$ in which every variable occurs and all occurrences of $x_i$ precede every occurrence of $x_{i+1}$. For $\bar a=a_0\cdots a_{k-1}\in A^{<\omega}$, $W(\bar a)$ is formed by replacing $x_i$ by $a_i$ for $i<k$ and stopping just before the first $x_k$. The Carlson--Simpson principle $\mathsf{CS}$ says that every finite colouring of $A^{<\omega}$ admits such a $W$ with $\{W(\bar a):\bar a\in A^{<\omega}\}$ monochromatic.

Statement recorded in the supplied source.

Determine the reverse-mathematical strength of $\mathsf{CS}$. [S2]

Short English statement

Which set-existence axioms are needed to find an infinite variable word whose finite substitutions all have the same colour?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 7500111 (AMR-074-0111). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Antonio Montalbán, Open Questions in Reverse Mathematics, author preprint dated 17 August 2010, Question 11, printed p. 5. https://math.berkeley.edu/~antonio/papers/questionsRM.pdf.