×

Partition relations for cardinal numbers. (English) Zbl 0158.26603

Small Greek letters denote ordinal numbers, small Roman letters denote cardinal numbers (i.e. initial ordinal), always \(p,r,s < \omega_0\), \(|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 \to (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 \(\nu_0<\lambda\) and a subset \(Y \subseteq X\) such that \(|Y| =b\) and \([Y]^r \subseteq J_{\nu_0}\). The relation II: \(a \to (b_\nu)^{<\aleph_0}_{\nu<\lambda}\) means that for every partition \([X]^{<\aleph_0} = \bigcup_{\nu <\lambda} J_\nu\), where \([X]^{<\aleph_0} = \bigcup_{r < \omega_0} [X]^r\), there exista a \(\nu_0 < \lambda\) and a subset \(Y \subseteq X\), \(|Y| = b_{\nu_0}\) and \([Y]^{<\aleph_0} \subseteq J_{\nu_0}\). The relation III: \[ \begin{pmatrix} a_0 \\ \vdots \\a_s \end{pmatrix} \to \begin{pmatrix} b_{0\nu} \\ \vdots \\ b_{s\nu} \end{pmatrix}^{r_0,...,r_s}_{\nu < \lambda} \] is equivalent to the following condition. Let \(|X_p| = a_p\) for \(p \leq s\), \(X_p\) are disjoint, \([X_0,...,X_s]^{r_0,...r_s} = \{X: X \subseteq X_0 \cup \cdots \cup X_s,\) \(|X\cap X_p| = r_p\) for \(p \leq s\} = \bigcup_{\nu < \lambda} J_\nu\). Then there exist sets \(Y_r \subseteq X_r\), for \(r \leq s\) and a \(\nu_0 < \lambda\) such that \(|Y_r| =b_{r\nu_0}\) for \(r \leq s\) and \[ [Y_0,...,Y_s]^{r_0,...,r_s} \subseteq J_{\nu_0}. \] ”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 \(\aleph_0\), 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_{\xi_1} < a_{\xi_2}\) for \(\xi_1 < \xi_2 <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 \left[\bigcup_{\sigma < a'} S_\sigma \right]^r\), the relations \(|X\cap S_\sigma| = |Y\cap S_\sigma|\) for \(\sigma < a'\) are equivalent to the condition: there is a \(\nu_0<\lambda\) such that \(X,Y \in J_{\nu_0}\).
Define \(\alpha \dot- 1 = \alpha\) for \(\alpha\) limit \(\alpha \dot- 1=\beta\) if and only if \(\alpha = \beta+1\), \(\text{cr}(\alpha) = \text{cf(cf}(\alpha \dot- 1)\). Let us denote:
(R) \(\aleph_{\beta +(r-2)} \to (b_\xi)^r_{\xi}<\lambda\),
(IA) \(b_0=\aleph_\beta\),
(IB) \(b_\xi < \aleph_\beta\) for \(\xi < \lambda\),
(CA) \(\prod_{1 \leq \xi < \lambda} b_\xi \leq \aleph_{cr(\beta)}\),
(CB) \(\prod_{\xi < \lambda} b_\xi < \aleph_\beta\),
(D) \(r \geq 3\), \(\beta > \text{cf}(\beta)>\text{cf}(\beta) \dot- 1 > \text{cr}\beta\), \(b_\xi < \aleph_0\) 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 \(b_1 \geq \aleph_0\), 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) \(b_0 > \aleph_{\alpha \dot- (r-2)}\).
(IIB) \(b_\xi \leq \aleph_\gamma\), \(\xi < \lambda\), \(\alpha = \gamma +s\), \(\gamma\) limit and \(s < r-2\).
(IIC1) \(b_0=\aleph_{\alpha \dot- (r-2)}\),
(IIC2) \(b_\xi < \aleph_{\alpha \dot- (r-2)}\) for \(\xi < \lambda\).
(R0) \(\aleph_\alpha \to (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 \to (b_\xi)^r_{\xi<\lambda}\), then \(a^+ \to (b_\xi+1)^{r+1}_{\xi < \lambda}\)” and ”if \(a \not\to (b_\xi)^r_{\xi < \lambda}\), then \(2^a \not\to (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 \to [b_\xi ]^r_{\xi<c}\) (relation V: \(a \to [b]^r_{c,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 \(\xi_0 < c\) (a set \(D \subseteq c\)) such that \(|X| = b_{\xi_0}\) and \([X]^r \cap J_{\xi_0} = \emptyset\) (\(|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\to [\aleph_{\alpha +1} ]^2_{\aleph_{\alpha +1}}\) for any \(\alpha\).
(ii) Let \(r \geq 2\) and \(\alpha > \text{cf} (\alpha)\). Then \(\aleph_{\alpha} \not\to [\aleph_\alpha]^r_{2^{r-1}}\).
(iii) If \(\aleph_\alpha'\) is \(\aleph_0\) or a measurable cardinal, then \(\aleph_\alpha \to [\aleph_\alpha]^r_c\) for \(c >2^{r-1}\) and \(\aleph_{\alpha} \to [\aleph_\alpha]^r_{c2^{r-1}}\) for \(c < \aleph_\alpha\).
(iv) \(\aleph_2 \to [\aleph_0, \aleph_1, \aleph_1 ]^3\).
On the other hand, there are many open problems, e.g. \(\aleph_2 \to [\aleph_1]^3_4?\), \(\aleph_3 \to [\aleph_1]^2_{\aleph_2,\aleph_0}?\)
In the second part, the authors investigate the polarized partition relation \(\binom{a}{b} \to \begin{pmatrix} a_0, & a_1 \\ b_0, & b1 \end{pmatrix}\), 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ý

MSC:

05D10 Ramsey theory
03E05 Other combinatorial set theory
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
05E10 Combinatorial aspects of representation theory
03E10 Ordinal and cardinal numbers

Keywords:

set theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos andR. Rado, A partition calculus in set theory,Bull. Amer. Math. Soc.,62, (1956), pp. 427–489. · Zbl 0071.05105
[2] A. Tarski, Quelques théorèmes sur les alephs,Fundam. Math.,7 (1925), pp. 1–14. · JFM 51.0164.03
[3] P. Erdos andR. Rado, Combinatorial theorems on classifications of subsets of a given set,Proc. London Math. Soc., (3)2 (1952), pp. 417–439. · Zbl 0048.28203
[4] P. Erdos andA. Hajnal, On the structure of set mappings,Acta Math. Acad. Sci. Hung.,9 (1958), pp. 111–131. · Zbl 0102.28401
[5] A. Tarski, Some problems and results relevant to the foundation of set theory,Proc. Internat. Congress for Logic, Methodology and Philosophy of Sciences, Stanford,. Calif., USA, 1960.
[6] P. Erdos andG. Fodor, Some remarks on set theory. VI,Acta Sci. Math. Szeged,18 (1957) pp. 243–260. · Zbl 0078.04203
[7] P. Erdos andA. Tarski, On families of mutually exclusive sets,Annals of Math.,44 (1943), pp. 315–329. · Zbl 0060.12602
[8] P. Erdos andG. Szekeres, A combinatorial problem in geometry,Comp. Math. 2 (1935), pp. 463–470. · Zbl 0012.27010
[9] P. Erdos, Some remarks on the theory of graphs,Bull. Amer. Math. Soc.,53 (1947), pp. 292–294. · Zbl 0032.19203
[10] P. Erdos, Remarks on, a theorem of Ramsey,Bull. Research Council of Israel, Section F., 1947.
[11] P. Erdos, Graph theory and probability,Canad. Journ. of Math.,11 (1959), pp. 34–38. · Zbl 0084.39602
[12] R. E. Greenwood andR. M. Gleason, Combinatorial relations and chromatic graphs,Canad. Journ. of Math.,7 (1955), pp. 1–7. · Zbl 0064.17901
[13] P. Erdos, Graph theory and probability II,Canad. Journ. of Math.,13 (1961), pp. 346–352. · Zbl 0097.39102
[14] A. Hajnal, Some results and problems on set theory,Acta Math. Acad. Sci. Hung.,11 (1960), pp. 277–298. · Zbl 0106.00901
[15] A. Tarski, Sur la décomposition des ensembles en sousensembles presque disjoint,Fundam. Math. 14 (1929), pp. 205–215. · JFM 55.0053.04
[16] P. Erdos Some remarks on set theory,Proc. Amer. Math. Soc.,1 (1950), pp. 127–141.
[17] A. Hajnal, Proof of a conjecture of S. Ruziewicz,Fundam. Math.,50 (1961), pp. 123–128. · Zbl 0100.28003
[18] F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc., (2)30 (1930), pp. 264–286. · JFM 55.0032.04
[19] W. Sierpiński, Sur un problème de la théorie des relations,Annali R. Scuola Normale Superiore de Pisa, Ser. 2,2 (1933), pp. 285–287. · JFM 59.0092.01
[20] G. Kurepa, On the cardinal number of ordered sets and of symmetrical structures in dependence of the cardinal numbers of its chains and antichains,Glanick Mat. Fiz. i Astr.,14 (1952), pp. 183–203. · Zbl 0173.00901
[21] P. Erdos andG. Fodor, Some remarks on set theory V,Acta Sci. Math. Szeged,12 (1956), pp. 250–260. · Zbl 0072.04103
[22] W. Sierpiński, Concernant l’hypothèse du continu,Acad. Royale Serbe Bull. de l’acad. Sci. Math. et Naturelles, Sér. A. Sc. Math. et Phys.,1 (1933), pp. 67–73.
[23] P. Erdos andS. Kakutani, On non-denumerable graphs,Bull. Amer. Math. Soc. 49 (1963), pp. 457–461. · Zbl 0063.01275
[24] P. Erdos andA. Tarski, On some problems involving inaccessible cardinals,Essays on the foundations of mathematics, Jerusalem (1961), pp. 50–82.
[25] P. Hanf, On a problem of Erdos and Tarski,Notices of the AMS,9 (1962), p. 229.
[26] A. Hajnal, Remarks on a theorem of W. P. Hanf,Fundam. Math.,54 (1964), pp. 109–113.
[27] Dana Scott, Measurable cardinals and constructible sets,Bull. Acad. Polon. Sci., Ser. des Sci. Math., Astr. et Phys.,7 (1959), pp. 145–149.
[28] H. J. Kiesler, Some applications of the theory of models to set theory,Logic, Methodology and Philosophy of Science, Proceedings of the 1960. International Congress Stanford (1962), pp. 80–86.
[29] P. Erdos andA. Hajnal, On a property of families of sets,Acta Math. Acad. Sci. Hung.,12 (1961), pp. 87–123. · Zbl 0201.32801
[30] H. J. Kiesler andA. Tarski, From accessible to inaccessible cardinals,Fundam Math.,53 (1964), pp. 225–308.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.