×

A dual form of Ramsey’s theorem. (English) Zbl 0564.05005

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. R. L. Graham and 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 J. D. Halpern and 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), V. Voigt, J. Reine Angew. Math. 358, 209-220 (1985; Zbl 0553.05011), H. J. Prömel, and 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 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 § 2 was influenced by the ideas of W. Deuber and 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 K. R. Milliken, J. Comb. Theory, Ser. A 26, 215-237 (1979; Zbl 0429.05035).]
Reviewer: W.Deuber

MSC:

05A17 Combinatorial aspects of partitions of integers
03E15 Descriptive set theory
54C50 Topology of special sets defined by functions
54H05 Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Baumgartner, J.E, Iterated forcing, () · Zbl 0524.03040
[2] Blass, A, A partition theorem for perfect sets, (), 271-277 · Zbl 0472.03038
[3] ()
[4] Carlson, T.J, On a conjecture of stephen simpson, preliminary report, Abstracts amer. math. soc., 4, 192, (1983)
[5] {\scT. J. Carlson}, in preparation.
[6] Drake, F, Set theory: an introduction to large cardinals, (1974), North-Holland Amsterdam · Zbl 0294.02034
[7] Ellentuck, E, A new proof that analytic sets are Ramsey, J. symbolic logic, 39, 163-165, (1974) · Zbl 0292.02054
[8] Friedman, H.M; McAloon, K; Simpson, S.G, A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis, (), 197-230
[9] Friedman, H, Independence results in finite graph theory, I-VI, handwritten notes, (1981), Ohio State University
[10] Galvin, F; Prikry, K, Borel sets and Ramsey’s theorem, J. symbolic logic, 38, 193-198, (1973) · Zbl 0276.04003
[11] Graham, R.L; Rothschild, B.L, Ramsey’s theorem for n-parameter sets, Trans. amer. math. soc., 159, 257-292, (1971) · Zbl 0233.05003
[12] Graham, R.L; Rothschild, B.L; Spencer, J.H, Ramsey theory, (1980), Wiley New York · Zbl 0455.05002
[13] Hales, A.W; Jewett, R.I, Regularity and positional games, Trans. amer. math. soc., 106, 222-229, (1963) · Zbl 0113.14802
[14] Halpern, J.D; Läuchli, H, A partition theorem, Trans. amer. math. soc., 124, 360-367, (1966) · Zbl 0158.26902
[15] Halpern, J.D; Lévy, A, The Boolean prime ideal theorem does not imply the axiom of choice, (), 83-134, Part I · Zbl 0233.02024
[16] Hindman, N, Finite sums from sequences within cells of a partition of N, J. combin. theory A, 17, 1-11, (1974) · Zbl 0285.05012
[17] Jech, T, Set theory, (1978), Academic Press New York · Zbl 0419.03028
[18] Jockusch, C.G, Ramsey’s theorem and recursion theory, J. symbolic logic, 37, 268-280, (1972) · Zbl 0262.02042
[19] Kuratowski, K, ()
[20] Laver, R, On the consistency of Borel’s conjecture, Acta math., 137, 151-169, (1976) · Zbl 0357.28003
[21] Laver, R, Products of infinitely many perfect trees, (1983), to be published
[22] Leeb, K, Vorlesungen über pascaltheorie, arbeitsberichte des inst. für math. maschinen und datenverarbeitung, Friedrich Alexander universität erlangen Nürnberg, Vol. 6, No. 7, (1973)
[23] Louveau, A; Simpson, S.G, A separable image theorem for Ramsey mappings, Bull. acad. polon. sci. ser. math., 30, 105-108, (1982) · Zbl 0498.04006
[24] Mathias, A.R.D, Happy families, Ann. of math. logic, 12, 59-111, (1977) · Zbl 0369.02041
[25] {\scA. Miller and K. Prikry}, in preparation.
[26] Milliken, K.R, Ramsey’s theorem with sums or unions, J. combin. theory A, 18, 276-290, (1975) · Zbl 0323.05001
[27] Milliken, K.R, A Ramsey theorem for trees, J. combin. theory A, 26, 215-237, (1979) · Zbl 0429.05035
[28] Milliken, K.R, A partition theorem for the infinite subtrees of a tree, Trans. amer. math. soc., 263, 137-148, (1981) · Zbl 0471.05026
[29] Paris, J; Harrington, L, A mathematical incompleteness in Peano arithmetic, (), 1133-1142
[30] Pincus, D; Halpern, J.D, Partitions of products, Trans. amer. math. soc., 267, 549-568, (1981) · Zbl 0485.03021
[31] Prikry, K, Determinateness and partitions, (), 303-306 · Zbl 0352.04003
[32] Prikry, K, In these notes I give…, manuscript, (November 1982)
[33] Ramsey, F.P, On a problem of formal logic, (), 264-286 · JFM 55.0032.04
[34] {\scK. Schilling}, On absolutely Δ12 operations, Fund. Math., in press.
[35] Schmerl, J.H, Peano models with many generic classes, Pacific J. math., Erratum, Pacific J. math., 92, 195-198, (1981) · Zbl 0461.03005
[36] Schmerl, J.H; Simpson, S.G, On the role of Ramsey quantifiers in first order arithmetic, J. symbolic logic, 47, 423-435, (1982) · Zbl 0492.03015
[37] Shelah, S, Proper forcing, () · Zbl 0495.03035
[38] Simpson, S.G, Sets which do not have subsets of every higher degree, J. symbolic logic, 43, 135-138, (1978) · Zbl 0402.03040
[39] Solovay, R.M, A model of set theory in which every set of reals is Lebesgue measurable, Ann. of math., 92, 1-56, (1970) · Zbl 0207.00905
[40] Solovay, R.M, Hyperarithmetically encodable sets, Trans. amer. math. soc., 239, 99-122, (1978) · Zbl 0411.03039
[41] van der Waerden, B.L, Beweis einer baudetschen vermutung, Nieuw arch. wisk., 15, 212-216, (1927) · JFM 53.0073.12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.