A dual form of Ramsey's theorem (Q1057862): Difference between revisions

This paper contains major progress in Ramsey theory. Ramsey's theorem may be stated as follows: Let \([X]^ k\) be the set of all subsets of X of cardinality k. Let k be finite and \([\omega]^ k=C_ 0\cup C_ 1;\) then there exists \(X\subseteq \omega\) with \(| X| =\aleph_ 0\) and \([X]^ k\subseteq C_ i\) for some i. First of all this is a theorem of infinitary combinatorics in which only k is finite. It is well known that by using the axiom of choices counterexamples for \(k=\aleph_ 0\) are possible. Therefore such a version can only hold if the set \(C_ 0,C_ 1\) are wellbehaved. It was the merit of Nash-Williams, Galvin- Prikry, Silver and Ellentuck to give the correct description of ''well behaviour'' in terms of certain topologies on \([\omega]^{\omega}\). Instead of considering \([\omega]^ k\) it was natural to investigate the dual situation \((\omega)^ k\) of all equivalence relations on \(\omega\) with k classes or equivalently of rigid surjections from \(\omega\) to k. \textit{R. L. Graham} and \textit{B. L. Rothschild} [Trans. Am. Math. Soc. 159, 257-292 (1971; Zbl 0233.05003)] gave a careful analysis of equivalence relations on finite sets introducing the notion of parameter sets. They proved a finitary version of a Ramsey type theorem for parameter sets. The authors show 1. Borel sets in \((\omega)^ k\) are Ramsey (k finite). 2. For \((\omega)^{\omega}\) a dual version of Ellentuck's theorem holds. These results are particularly relevant, as for about 15 years it was not clear whether extensions of the Graham-Rothschild theorem into the infinite are possible. The paper is clearly written and easily readable. It is carefully shown how the classical results may be derived as corollaries. Moreover applications to work of \textit{J. D. Halpern} and \textit{H. Läuchli} [ibid. 124, 360-367 (1966; Zbl 0158.269)] and dual Mathias forcing are indicated. Needless to say that the authors' paper got immediate attention and several papers extending their fine ideas emerged: The first author, An infinitary version of the Graham-Leeb-Rothschild theorem (to appear in J. Comb. Theory, Ser. A), \textit{V. Voigt}, J. Reine Angew. Math. 358, 209-220 (1985; Zbl 0553.05011), \textit{H. J. Prömel}, and \textit{B. Voigt}, Baire sets of k-parameter words are Ramsey (to appear in Trans. Am. Math. Soc.). Recently the authors have asked me to append the following remarks: 1. The proof of Theorem 6.3 was inspired in part by \textit{J. Baumgartner} [J. Comb. Theory, Ser. A 17, 384-386 (1974; Zbl 0289.05009)]. 2. The presentation of the proof of Lemma 2.5 in {\S} 2 was influenced by the ideas of \textit{W. Deuber} and \textit{B. Voigt} [Eur. J. Comb. 3, 329-340 (1982; Zbl 0503.05005)]. 3. Theorem 3.3, erroneously called the Halpern- Läuchli theorem, is actually only a corollary of the full result which is due to Halpern, Läuchli, Laver and Pincus. [See \textit{K. R. Milliken}, J. Comb. Theory, Ser. A 26, 215-237 (1979; Zbl 0429.05035).]