The Dual Ramsey Theorem

Let $(\mathbb{N} )^k$ denote the set of partitions of $\mathbb{N}$ into exactly knonempty pieces. Let $(\mathbb{N} )^\infty$ denote the set of partitions of $\mathbb{N}$ into infinitely many nonempty pieces. For $X\in(\mathbb{N} )^\infty$, (X)^k is the set of all $Y\in(\mathbb{N} )^k$ such that Y is coarser than X. The dual Ramsey theorem of Carlson/Simpson [6] reads as follows:

If $(\mathbb{N} )^k$ is colored with finitely many Borel colors, then there exists $X\in(\mathbb{N} )^\infty$ such that (X)^k is monochromatic.

This also holds with k replaced by $\infty$. There are some important generalizations of this due to Carlson. This kind of result has been used by Furstenberg and Katznelson to obtain a ``density version'' of the Hales/Jewett theorem. For references, see my book [32, remark X.3.6].

There are many open problems concerning the strength of the dual Ramsey theorem and related theorems. Slaman [34] has shown that the dual Ramsey theorem is provable in $\Pi^1_1$- $\mathsf{CA}_0$. No interesting reversal is known.

Let A be a fixed finite alphabet. $A^{\textstyle*}$ denotes the set of words, i.e., finite strings of elements of A. An infinite variable word is an infinite string W of elements of $A\cup\{x_n:n\in\mathbb{N}\}$ such that each x_n occurs at least once, and all occurrences of x_n precede all occurrences of x_n+1, for all n. If $s=a_0\cdots a_{n-1}\in A^{\textstyle*}$, we denote by W(s)the word which results from W upon replacing all occurrences of x_m by a_m for each m<n, then truncating just before the first occurrence of x_n. A key lemma of Carlson/Simpson [6] reads as follows:

If $A^{\textstyle*}$ is colored with finitely many colors, then there exists an infinite variable word W such that $W(A^{\textstyle*})=\{W(s):s\in A^{\textstyle*}\}$ is monochromatic.

The strength of this lemma is unknown. In particular, it is unknown whether this lemma is true recursively, i.e., whether W can be taken to be recursive in the given coloring. For more background on this problem, see Simpson [30].