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

###

The Dual Ramsey Theorem

Let
denote the set of partitions of
into exactly *k*nonempty 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 *x*_{n} occurs at least once, and
all occurrences of *x*_{n} precede all occurrences of *x*_{n+1}, for all
*n*. If
,
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
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*