Auswahlprinzip von Rado

Das Auswahlprinzip von Rado (oder Rados Auswahlprinzip<ref>H. Lüneburg: Kombinatorik. 1971, S. 61. </ref> genannt; englisch Rado’s Selection Principle<ref>L. Mirsky: Transversal Theory. 1971, S. 52. </ref> oder Rado’s Selection Lemma<ref>E. Harzheim: Ordered Sets. 2005, S. 234. </ref>) ist ein mathematischer Lehrsatz, welcher sowohl der Mengenlehre als auch der diskreten Mathematik zuzurechnen ist. Das Auswahlprinzip geht auf den deutschen Mathematiker Richard Rado zurück. Es ist ein wichtiges Hilfsmittel zur Herleitung bedeutender Resultate der transfiniten diskreten Mathematik wie etwa der transfiniten Versionen des Satzes von Dilworth oder des Heiratssatzes von Hall. Ebenso erweist sich der Satz von de Bruijn und Erdős als unmittelbare Folgerung aus Rados Auswahlprinzip.

Dem Beweis des Auswahlprinzips liegt das Auswahlaxiom oder eines der zu jenem äquivalenten Maximalprinzipien der Mengenlehre zugrunde. Es lässt sich zeigen,<ref>W. H. Gottschalk: Choice functions and Tychonoff's theorem. 1951, S. 172. </ref> dass sich Rados Auswahlprinzip als Anwendung des Tychonoffschen Satzes ergibt.

Formulierung des Auswahlprinzips

Im Folgenden bedeute für zwei Mengen <math> X </math> und <math> Y </math> die Notation <math> X {\subset \subset} Y</math>, dass <math> X </math> eine endliche Teilmenge von <math> Y</math> ist. Rados Auswahlprinzip lässt sich damit formulieren wie folgt:<ref>H. Lüneburg: Kombinatorik. 1971, S. 61–62. </ref><ref>E. Harzheim: Ordered Sets. 2005, S. 234. </ref><ref>L. Mirsky: Transversal Theory. 1971, S. 52. </ref>

Gegeben seien eine nicht-leere Indexmenge <math> I </math> , eine nicht-leere Grundmenge <math> M </math> und in <math> M </math> eine Mengenfamilie <math> \mathcal M = (M_i)_{i \in I}</math> , bestehend aus nicht-leeren Teilmengen <math> M_i {\subset \subset} M </math> ( <math> i \in I </math> ).

Ferner sei zu jeder endlichen Unterfamilie <math> \mathcal M_J = (M_j)_{j \in J}</math> ( <math>J {\subset \subset} I</math> ) eine Auswahlfunktion <math> {{\alpha}_J} </math> gegeben.

Dann existiert für <math> \mathcal M </math> eine Auswahlfunktion <math>{\alpha} </math> , welche eine teilweise Fortsetzung der <math>{{\alpha}_J} </math> ( <math>J {\subset \subset} I</math> ) darstellt dergestalt, dass es zu jeder dieser Indexmengen <math> J {\subset \subset} I </math> eine ebensolche Indexmenge <math>K </math> gibt mit <math> J \subseteq K {\subset \subset} I</math> und <math> {{\alpha}_K}{{\upharpoonright}J} = {\alpha}{{\upharpoonright}J}</math> <ref><math> {{\upharpoonright}J}</math> steht für die Einschränkung auf <math> J </math></ref>.

Einige Folgerungen

Unter Benutzung von Rados Auswahlprinzip ergeben sich unter anderem:

Der Satz von de Bruijn - Erdős:<ref>M. Aigner: Combinatorial Theory. 1979, S. 410. </ref>

Ein Graph ist <math> k</math>-färbbar ( <math> k \in \N </math> ) dann und nur dann, wenn jeder endliche induzierte Teilgraph <math> k</math>-färbbar ist.

Der Satz von Dilworth (transfinite Version):<ref>M. Aigner: Combinatorial Theory. 1979, S. 410. </ref><ref>E. Harzheim: Ordered Sets. 2005, S. 60. </ref><ref>Der Satz von Dilworth (allgemeine Version) lässt sich sowohl unter direkter Benutzung von Rados Auswahlprinzip (Aigner) als auch mittels des Satzes von de Bruijn / Erdős (Harzheim) herleiten.</ref>

Eine unendliche teilweise geordnete Menge der Breite <math> w \in \N </math> lässt sich stets in <math> w </math> paarweise disjunkte Ketten zerlegen.

Der Heiratssatz (transfinite Version):<ref>M. Aigner: Combinatorial Theory. 1979, S. 409. </ref><ref>H. Lüneburg: Kombinatorik. 1971, S. 65. </ref>

Eine unendliche Familie endlicher Mengen besitzt eine Auswahl (Vertretersystem) dann und nur dann, wenn jede endliche Unterfamilie die Hall-Bedingung erfüllt.

Der Satz von B. H. Neumann:<ref>H. Lüneburg: Kombinatorik. 1971, S. 63. </ref>

Eine Gruppe besitzt eine mit der Gruppenstruktur verträgliche Totalordnung dann und nur dann, wenn jede endlich erzeugte Untergruppe eine solche besitzt.

Der Satz von F. W. Levi:<ref>H. Lüneburg: Kombinatorik. 1971, S. 64. </ref>

Eine abelsche Gruppe besitzt eine mit der Gruppenstruktur verträgliche lineare Anordnung dann und nur dann, wenn sie torsionsfrei ist.

Literatur

Artikel und Originalarbeiten

W. H. Gottschalk: Choice functions and Tychonoff's theorem. In: Proc. Amer. Math. Soc. Band 2, 1951, S. 172.
R. Rado: Axiomatic treatment of rank in infinite sets. In: Canad. J. Math. Band 1, 1949, S. 337–343.
R. Rado: A Selection Lemma. In: J. Comb. Theory. Band 10, 1971, S. 176–177.

Monographien

Martin Aigner: Combinatorial Theory (= Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Band 234). Springer-Verlag, Berlin/New York 1979, ISBN 0-387-90376-3 (MR0542445).
Heinz Lüneburg: Kombinatorik. Birkhäuser Verlag, Basel u. a. 1971, ISBN 3-7643-0548-7.

Einzelnachweise