Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  158.26603
Autor:  Erdös, Pál; Hajnal, András; Rado, R.
Title:  Partition relations for cardinal numbers (In English)
Source:  Acta Math. Acad. Sci. Hung. 16, 93-196 (1965).
Review:  Small Greek letters denote ordinal numbers, small Roman letters denote cardinal numbers (i.e. initial ordinal), always p,r,s < \omega0, |X| is the cardinality of X, [X]r denotes the set of all r element subsets of X. The partition relations I, II, III are defined as follows. The relation I: a ––> (b\nu)r\nu < \lambda holds true if and only if for every partition [X]r = \bigcup\nu < \lambda J\nu, |X| = a, there is a \nu0 < \lambda and a subset Y \subseteq X such that |Y| = b and [Y]r \subseteq J\nu0. The relation II: a ––> (b\nu) < \aleph0\nu < \lambda means that for every partition [X] < \aleph0 = \bigcup\nu < \lambda J\nu, where [X] < \aleph0 = \bigcupr < \omega0 [X]r, there exista a \nu0 < \lambda and a subset Y \subseteq X, |Y| = b\nu0 and [Y] < \aleph0 \subseteq J\nu0. The relation III:

\pmatrix a0 \\ \vdots \\as \endpmatrix ––> \pmatrix b0\nu \\ \vdots
bs\nu \endpmatrixr0,...,rs\nu < \lambda

is equivalent to the following condition. Let |Xp| = ap for p \leq s, Xp are disjoint, [X0,...,Xs]r0,...rs = {X: X \subseteq X0 \cup ··· \cup Xs, |X\cap Xp| = rp for p \leq s} = \bigcup\nu < \lambda J\nu. Then there exist sets Yr \subseteq Xr, for r \leq s and a \nu0 < \lambda such that |Yr| = br\nu0 for r \leq s and

[Y0,...,Ys]r0,...,rs \subseteq J\nu0.

"In this paper our first major aim is to discuss as completely as possible the relation I. Our most general results in this direction are stated in Theorems I and II, ... . If we disregard cases when among the given cardinals there occur inaccessible numbers greater than \aleph0, and if we assume the General Continuum Hypothesis, then our results are complete for r = 2, ... . It seems that there are only two essentially different methods for obtaining positive partition formulae: those given in Lemma 1 and those given in Lemma 3 ... In Lemma 5 we state powerful new methods for constructing examples of particular partitions which yield negative I-relation. ... Our second major aim is an investigation of the polarized partition relation III."
The exact formulation of the Lemma 1 is complicated; its contents may be shortly formulated as follows: in every sufficiently great tree, in which from every edge goes out a small number of branches, there is a large branche.
The simplest canonization lemma (the Lemma 3 proved using the Generalized Continuum Hypothesis) may be stated as follows: Let |S| = a > a' (a' is the smallest cardinal with which a is cofinal); r \geq 1, a = \sup {a\xi < a'}, a\xi1 < a\xi2 for \xi1 < \xi2 < a', [S]r = \bigcup\nu < \lambda J\nu, \lambda < a. Then there are disjoint sets S\sigma, \sigma < a', |S\sigma| = a\sigma, S\sigma \subseteq S and for X,Y in [\bigcup\sigma < a' S\sigma ]r, the relations |X\cap S\sigma| = |Y\cap S\sigma| for \sigma < a' are equivalent to the condition: there is a \nu0 < \lambda such that X,Y in J\nu0.
Define \alpha \dot- 1 = \alpha for \alpha limit \alpha \dot- 1 = \beta if and only if \alpha = \beta+1, cr(\alpha) = cf(cf(\alpha \dot- 1). Let us denote:
(R) \aleph\beta+(r-2) ––> (b\xi)r\xi < \lambda,
(IA) b0 = \aleph\beta,
(IB) b\xi < \aleph\beta for \xi < \lambda,
(CA) prod1 \leq \xi < \lambda b\xi \leq \alephcr(\beta),
(CB) prod\xi < \lambda b\xi < \aleph\beta,
(D) r \geq 3, \beta > cf(\beta) > cf(\beta) \dot- 1 > cr\beta, b\xi < \aleph0 for 1 \leq \xi < \lambda.
The first main theorem may be stated as follows. Let \lambda \geq 2, 2 \leq r < b\xi \leq \aleph\beta for \xi < \lambda. Assuming the Generalized Continuum Hypothesis we have:
(i) If (IA) holds, (D) does not holds, then (R) implies (CA).
(ii) If (IA) holds and b1 \geq \aleph0, then (R) implies (CA).
(iii) If (IA) holds and \aleph\beta' is not inaccessible, then (CA) implies (R).
(iv) If (IA) holds and b\xi < \aleph\beta ' for 0 < \xi < \lambda then (CA) implies (R).
(v) If (IB) holds, then (CB) is equivalent to (R).
Let us denote:
(IIA) b0 > \aleph\alpha \dot- (r-2).
(IIB) b\xi \leq \aleph\gamma, \xi < \lambda, \alpha = \gamma+s, \gamma limit and s < r-2.
(IIC1) b0 = \aleph\alpha \dot- (r-2),
(IIC2) b\xi < \aleph\alpha \dot- (r-2) for \xi < \lambda.
(R0) \aleph\alpha ––> (b\xi)r\xi < \lambda.
The second main theorem: Let \lambda \geq 2, 2 \leq r < b\xi \leq \aleph\alpha for \xi < \lambda.
Assuming the Generalized Continuum Hypothesis we have:
(i) If (IIA) holds, then (R0) is false.
(ii) If (IIB) and (IIC1) hold, (R0) implies that \aleph\alpha \dot-(r-2) is inaccessible.
(iii) If (IIB) and (IIC2) hold, then (R0) is equivalent to the condition prod\xi < \lambda b\xi < \aleph\alpha \dot-(r-2).
The proofs are based on Lemmas 1, 2, 3 and 5. The Lemma 2 and 5 are the stepping-up and stepping-down Lemmas respectively, i.e. they are of the form "if a ––> (b\xi)r\xi < \lambda, then a^+ ––> (b\xi+1)r+1\xi < \lambda" and "if a \not ––> (b\xi)r\xi < \lambda, then 2a \not ––> (b\xi+1)r+1\xi < \lambda", respectively (of course, under some assumptions).
A great part of the paper is devoted to the study of relations IV and V. The relation IV: a ––> [b\xi ]r\xi < c (relation V: a ––> [b]rc,d) is equivalent to the condition: whenever |S| = a, [S]r = \bigcup\xi < c J\xi, where the J\xi are disjoint, then there are a set X \subseteq S and a number \xi0 < c (a set D \subseteq c) such that |X| = b\xi0 and [X]r \cap J\xi0 = Ø (|X| = b, |D| \leq a and [X]r \subseteq \bigcup\xi in D J\xi). Some results (assuming the Generalized Continuum Hypothesis):
(i) \aleph\alpha+1 \not ––> [\aleph\alpha+1 ]2\aleph_{\alpha+1} for any \alpha.
(ii) Let r \geq 2 and \alpha > cf (\alpha). Then \aleph\alpha \not ––> [\aleph\alpha]r2r-1.
(iii) If \aleph\alpha' is \aleph0 or a measurable cardinal, then \aleph\alpha ––> [\aleph\alpha]rc for c > 2r-1 and \aleph\alpha ––> [\aleph\alpha]rc2r-1 for c < \aleph\alpha.
(iv) \aleph2 ––> [\aleph0, \aleph1, \aleph1 ]3.
On the other hand, there are many open problems, e.g. \aleph2 ––> [\aleph1]34?, \aleph3 ––> [\aleph1]2\aleph2,\aleph0?
In the second part, the authors investigate the polarized partition relation \binom{a}{b} ––> \pmatrix a0, a1 \\ b0, b1 \endpmatrix, i. e. a special case of the relation III. A complete discussion is given, however, the results are not complete. Many other relations and problems are studied, but it is impossible to give a full list of them here.
The paper is rather difficult to read and gives the impression of a condensed version of a monography.
Reviewer:  L.Bukovský
Classif.:  * 05D10 Ramsey theory
                   03E05 Combinatorial set theory (logic)
                   04A20 Combinatorial set theory
                   03-02 Research monographs (mathematical logic)
                   05E10 Tableaux, etc.
                   04A10 Ordinal and cardinal numbers; generalizations
Index Words:  set theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page