×

On the complete subgraphs of graphs defined by systems of sets. (English) Zbl 0151.33702

Ein Mengensystem \({\mathfrak F}=(F,M,S)\) (\(F\) Abbildung von \(M\) in die Potenzmenge von \(S\)) heißt \((m,\alpha\))-System, wenn \(|M| =m\) und \(S\) wohlgeordnet vom Typ \(\text{tp}S = \alpha\); \(B \subseteq S\) heißt \(({\mathfrak F},k)\)-vollständig), wenn zu jedem \(A \subseteq B\) mit \(|A| = k\) (bzw. \(|A| < k\)) ein \(\mu \in M\) mit \(A \subseteq F_\mu\) existiert; \(C \subseteq S\) heißt \(({\mathfrak F},n)\)-frei, wenn \(|\{\mu \in M \mid {\mathfrak F}_\mu \cap C=\emptyset \} | \geq n\). Die Verff. untersuchen Relationen von folgender oder ähnlicher Art: (1) \(\alpha \to [\beta,\gamma]^k_m\); (2) \(\alpha \to [\beta,\gamma]_m\). (1), (2) besagen, daß zu jedem \((m,\alpha)\)-System \({\mathfrak F} = (F,M,S)\) ein \(({\mathfrak F},m)\)-freies \(C \subseteq S\) mit \(\text{tp}C = \gamma\) existiert oder im Fall (1) ein \(({\mathfrak F},k)\)-vollständiges \(B \subseteq S\) mit \(\text{tp}B = \beta\), im Fall (2) ein \(F_\mu\) mit \(\text{tp}{\mathfrak F}_\mu \geq \beta\). (1), (2) gehen in Relationen analogen Inhalts über, wenn \(\alpha,\beta,\gamma\) durch Kardinalzahlen ersetzt werden. \(\alpha \to [\beta,\gamma]_m^{<k}\) wird ähnlich wie (1) interpretiert (... oder ein \(({\mathfrak F},< k)\)-vollständiges \(B \subseteq S\) mit \(\text{tp}B = \beta)\).
Ein Hauptergebnis [unter Benutzung der G. C. H. (generalized continuum hypothesis)]: \(m \to [m,m]_n^{<\aleph_0}\) (\(m,n > \aleph_0\)), schärfer \(m \Rightarrow [m,m]_n\) falls \(m,n > \aleph_0\) und \(m' \neq n'\) (\(m' = \aleph_{cf(\alpha )},\) wenn \(m = \aleph_{\alpha}\)). Weiter wird \(\alpha \to [\beta,\gamma]_{\aleph_0}^{<\aleph_0}\) für \(\alpha , \beta , \gamma < \omega_1\) vollständig diskutiert. In der Folge werden höhere Fälle von (1) bewiesen, z.B.: \(\omega_1^\omega \to [\omega_1^\omega,\omega_1^n ]_{\aleph_1}^{< \aleph_0}\) \((n<\omega)\) und \(\omega_1^\lambda \to [\omega_1^\lambda,\omega_1^\omega]^2_{\aleph_0}\) \((\omega \leq \lambda < \omega_2)\). Die Relation (3) von der Form \((a,m,n,c)^k \to s\) beinhaltet, daß zu jedem \((m,a)\)-System \({\mathfrak F}=(F,M,S)\) ein \(({\mathfrak F},n)\)-freies \(C \subseteq S\) mit \(|C| = c\) oder eine Darstellung \(S = A \cup \bigcup_{i\in I} B_i\) mit \(|I| < s\), \(|A| < a\) und \(({\mathfrak F},k)\)-vollständigen \(B_i\) \((i \in I)\) existiert. Für \(k,m,n,s < \aleph_0\) wird die Äquivalenz von (3) mit einem endlichen Problem gezeigt und z. B. bewiesen: (\(a,m,n,c)^k \to s\), falls \(n \geq s\), \(m \geq k(n-s+1)+s-1\), \(a \geq \aleph_0\) und \(a \geq c \geq 1\).
Weitere Ergebnisse zu (3): \((\aleph_0,\aleph_0,\aleph_0,\aleph_0)^k \to 3\) \((k< \aleph_0)\) und \((a,m,m,m)^2 \to m\) (\( m \geq \aleph_0,\) \(m\) Nachfolgerzahl oder \(m'=\aleph_0\)).
In der Arbeit werden außerdem viele negative Resultate, z.B. \(m^+\not\to [m^+,m]^m_{m^+}\) (\(m \geq \aleph_0\)) bewiesen, einige Fragen auf den Partitionskalkül zurückgeführt und 15 Probleme explizite formuliert.
Reviewer: H.A.Jung

Keywords:

topology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos andN. G. de Bruijn, A colour problem for infinite graphs and a problem in the theory of relations,Indig. Math.,13 (1951), pp. 311–313.
[2] P. Erdos, A. Hajnal andR. Rado, Partition relations for cardinal numbers,Acta Math. Acad. Sci. Hung.,16 (1965), pp. 93–196. · Zbl 0158.26603
[3] P. Erdos andR. Rado, A partition calculus in set theory,Bull. Amer. Math. Soc. 62 (5), pp. 427–489. · Zbl 0071.05105
[4] P. Erdos andE. Specker, On a theorem in the theory of relations and a solution of a problem of Knaster,Coll. Math.,8 (1) (1961), pp. 19–21. · Zbl 0097.04202
[5] P. Erdos andA. Tarski, On some problems involving inaccessible cardinals,Essays on the foundations of Math., The Hebrew University, Jerusalem, 1961.
[6] M. Kneser, Aufgabe 360,Jahresbericht d. Deutschen Math. Vereinigung,58 (2) (1955).
[7] E. C. Milner andR. Rado, The pigeon-hole principle for ordinal numbers,Proc. London Math. Soc., (3)15 (1965). · Zbl 0145.24501
[8] F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc., (2)30 (1930), pp. 264–286. · JFM 55.0032.04
[9] E. Specker, Teilmengen von Mengen mit Relationen,Commentarii Math. Helvetici,31 (1957), pp. 302–314. · Zbl 0080.03703
[10] A. Tarski, Quelques theorems sur les alephs,Fund. Math. 7 (1925), pp. 1–13. · JFM 51.0164.03
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.