Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  274.04005
Autor:  Erdös, Paul; Hajnal, András; Mate, Attila
Title:  Chain conditions on set mappings and free sets. (In English)
Source:  Acta Sci. Math. 34, 69-79 (1973).
Review:  Given an infinite set E, a function f mapping E into P(E), the set of all subsets of E, is called a set mapping if x \not in f(x) holds for any x in E. A subset X of E is called free (with respect to f) if X \cap f(x) = 0 holds for any x in X. A. Hajnal [Fundam. Math. 50, 123-128 (1961; Zbl 100.28003)] showed that if |f(x)| < \mu < |E| (|A| denotes the cardinality of A) holds with some cardinal \mu for any x in E, then there is a free set of cardinality |E|. The aim of the present paper is to weaken the assumptions in Hajnal's theorem. To this end, say that a set S satisfies the \eta-chain condition for some ordinal \eta if there is no sequence < s\alpha: \alpha < \eta > of elements of S such that s\alpha \subset s\beta whenever \alpha < \beta < \eta (\subset means strict inclusion here). Consider the following conditions imposed on f: |E| = \kappa is a regular cardinal, |f(x)| < \kappa for any x in E, and, for any \tau < \kappa and any decomposition E = \bigcup\alpha < \tau E\alpha of E into pairwise disjoint sets E\alpha of cardinality \kappa, there is an ordinal \gamma < \tau and a set F \subseteq E\gamma of cardinality \kappa such that the set {f(x) \cap F: x in E } satisfies the \kappa-chain condition. Under these assumptions it is proved by a tree argument that (i) there exists an infinite free set, (ii) if \mu is a cardinal < \kappa such that for every \nu < \kappa we have \nu \mu < \kappa, then there exists a free set of cardinality \mu, and (iii) if \kappa is inaccessible and weakly compact, then there exists a free set of cardinality \kappa. (iv) If there is a \kappa-Souslin tree, or if (v) \kappa = 2\lambda = \lambda ^+, then it is shown that the above conditions do not imply the existence of a free set of cardinality \kappa. Several stronger negative results are announced without proof.
Classif.:  * 04A20 Combinatorial set theory
                   03E35 Consistency and independence results (set theory)
                   03E15 Descriptive set theory (logic)
                   03E55 Large cardinals
Citations:  Zbl 100.28003

© 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