Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 048.28203
Autor: Erdös, Pál; Rado, R.
Title: Combinatorial theorems on classifications of subsets of a given set. (In English)
Source: Proc. Lond. Math. Soc., III. Ser. 2, 417-439 (1952).
Review: Es sei \Omegan(S) die Menge aller Teilmengen einer Menge S, die genau n Elemente enthalten. F. P. Ramsey zeigte: Zu irgend drei natürlichen Zahlen k,n,N gibt es eine natürliche Zahl M derart, daß für S = {1,2,...,M} und irgendeine Verteilung \Delta von \Omegan(S) in k Klassen stets ein Element S' von \Omegan(S) existiert mit der Eigenschaft, daß die {N \choose n} Elemente von \Omegan(S') derselben Klasse von \Delta angehören. Verff. geben als erstes für das kleinste M dieser Art eine Abschätzung nach oben (Satz 1), die besser ist als die bisherigen und sich vor allem explizit durch algebraische Grundoperationen [(n-1)-fache Potenzierung ] ausdrücken läßt. Weiter untersuchen sie bestimmte als invariant bzw. kanonisch bezeichnete Verteilungen von \Omegan(S). In einer früheren Arbeit der Verff. (Zbl 038.15301) wurde gezeigt, daß für S = {1,2,3,...} beide Arten von Verteilungen zusammenfallen. Hier ergibt sich, daß dies für endliche S nicht zutrifft, und es werden (Satz 2) notwendige und hinreichende Bedingungen für n und N angegeben, damit jede invariante Verteilung von \Omegan (1,2,...,N) auch kanonisch ist. Mittels Satz 1 und Satz 2 gelingt (Satz 3) eine finite Fassung des von den Verff. a.a.O. verallgemeinerten Ramseyschen Satzes (Anzahl k der Klassen beliebig bei abzählbar unendlichen S und S').
Es folgt eine Ausdehnung der Untersuchungen für k = n = 2 ins Transfinite. Hier geht es z.B. um die Frage, ob bei vorgeschriebenem Ordnungstypus stets eine Menge X reeller Zahlen von diesem Typus existiert derart, daß eine der Klassen die Menge \Omega2(X) enthält. Insbesondere ergibt sich (Satz 7), daß dies bei jedem Ordnungstypus \omega+m (m endlich) zutrifft. Andere Sätze deuten daraufhin, daß bei jeder Verteilung jede abzählbare Ordinalzahl in diesem Sinne "verwirklicht" werden könnte. Weiter wird durch Beispiele gezeigt, daß Ramseys Satz in gewissen Richtungen nicht zu verallgemeinern geht. Hier ergeben sich interessante, noch ungelöste Fragen.
Als letztes wird eine Abschätzung nach unten angegeben für das kleinste (in einem Satz von van der Waerden auftretende) m = m(k,l) mit der Eigenschaft, daß bei jeder Verteilung von {1,2,...,m} in k Klassen mindestens eine Klasse eine arithmetische Progression von l+1 Gliedern enthält.
Reviewer: H.Rohrbach
Classif.: * 05D10 Ramsey theory
04A20 Combinatorial set theory
03E05 Combinatorial set theory (logic)
Index Words: set theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag