Next: WQO Theory Up: Ramsey Theory Previous: Szemerédi's Theorem

### The Dual Ramsey Theorem

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

If is colored with finitely many Borel colors, then there exists such that (X)k is monochromatic.
This also holds with k replaced by . 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 - . No interesting reversal is known.

Let A be a fixed finite alphabet. 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 such that each xn occurs at least once, and all occurrences of xn precede all occurrences of xn+1, for all n. If , we denote by W(s)the word which results from W upon replacing all occurrences of xm by am for each m<n, then truncating just before the first occurrence of xn. A key lemma of Carlson/Simpson [6] reads as follows:

If is colored with finitely many colors, then there exists an infinite variable word W such that 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].

Next: WQO Theory Up: Ramsey Theory Previous: Szemerédi's Theorem
Stephen G Simpson
1999-12-15