Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 103.27901
Autor: Erdös, Pál; Rado, R.
Title: Intersection theorems for systems of sets (In English)
Source: J. Lond. Math. Soc. 35, 85-90 (1960).
Review: Let a and b be cardinals \geq 1, let { X\nu | \nu in N } be a family of sets of equal cardinality |X\nu| = c \leq b, let \Phi(a,b) be a cardinal, and consider the assertion (D): if |N| > \Phi(a,b) then there exists a subset N' of N, |N'| > a, such that all (X\nu \cap X\mu) are equal for \nu \ne \mu, \nu, \mu in N'. Note that for finite a,b = 1, and \Phi(a,b) = a2, this is a version of Dirichlet's box principle. It is extended here to theorem III: If a and b are finite then assertion (D) is valid for \Phi(a,b) = b! ab+1 (1- ½! a-···-(b-1)/b! ab-1). The problem is left open whether or not the factor b! may be replaced by db, for an appropriate constant d (the authors would have an application of this improved theorem III to number theory).
Theorem I(ii): If a \geq 2 and either a or b is infinite then assertion (D) is valid for \Phi(a,b) = ab. Examples are produced to show that in I(ii) the estimating function ab is the best possible, and in III the indicated \Phi is best up to a factor of b! (theorem II). I(ii) is a simple consequence of theorem I(i): Assertion (D) holds for \Phi(a,b) = (b+1) bb ab+1. However, the proof of I(i) uses the axiom of choice and a Ramification Lemma: Let \alpha be an ordinal, {c\gamma | \gamma < \alpha} a family of cardinals. Let S be a set and for \gamma < \alpha, {s\delta | \delta < \gamma} \subseteq S let M { s\delta } \subseteq S and |M{S\delta}| \leq c\gamma. Let V be the set of all families {s\delta | \delta < \alpha} such that s\gamma in M{s\delta | \delta < \gamma} if \gamma < \alpha. Then |V| \leq prod\gamma < \alpha c\gamma. Theorem III is also established by using I(i); of course the axiom of choice is not needed here, as I(i) and the Ramification Lemma enter in their finite version only. It should be noted that this is not the Ramification Lemma which is an extension of Königs's infinite lemma. It would be interesting to know what relation there is between these results and Ramsey's theorems.
Reviewer: J.R.Büchi
Classif.: * 05D05 Extremal set theory
04A99 Miscellaneous topics in set theory
Index Words: set theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag