Auswahlprinzip von Rado

Das Auswahlprinzip von Rado (oder Rados Auswahlprinzip^[1] genannt; englisch Rado’s Selection Principle^[2] oder Rado’s Selection Lemma^[3]) 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,^[4] dass sich Rados Auswahlprinzip als Anwendung des Tychonoffschen Satzes ergibt.

Formulierung des Auswahlprinzips

Im Folgenden bedeute für zwei Mengen ${\displaystyle X}$ und ${\displaystyle Y}$ die Notation ${\displaystyle X{\subset \subset }Y}$, dass ${\displaystyle X}$ eine endliche Teilmenge von ${\displaystyle Y}$ ist. Rados Auswahlprinzip lässt sich damit formulieren wie folgt:^[5][6][7]

Gegeben seien eine nicht-leere Indexmenge   ${\displaystyle I}$ , eine nicht-leere Grundmenge  ${\displaystyle M}$  und in  ${\displaystyle M}$  eine Mengenfamilie   ${\displaystyle {\mathcal {M}}=(M_{i})_{i\in I}}$  , bestehend aus nicht-leeren Teilmengen  ${\displaystyle M_{i}{\subset \subset }M}$   ( ${\displaystyle i\in I}$ ).

Ferner sei zu jeder endlichen Unterfamilie ${\displaystyle {\mathcal {M}}_{J}=(M_{j})_{j\in J}}$  (  ${\displaystyle J{\subset \subset }I}$  ) eine Auswahlfunktion  ${\displaystyle {{\alpha }_{J}}}$   gegeben.

Dann existiert für ${\displaystyle {\mathcal {M}}}$  eine Auswahlfunktion  ${\displaystyle {\alpha }}$  , welche eine teilweise Fortsetzung der  ${\displaystyle {{\alpha }_{J}}}$  (  ${\displaystyle J{\subset \subset }I}$  ) darstellt dergestalt, dass es zu jeder dieser Indexmengen   ${\displaystyle J{\subset \subset }I}$   eine ebensolche Indexmenge   ${\displaystyle K}$   gibt mit   ${\displaystyle J\subseteq K{\subset \subset }I}$   und  ${\displaystyle {{\alpha }_{K}}{{\upharpoonright }J}={\alpha }{{\upharpoonright }J}}$ ^[8].

Einige Folgerungen

Unter Benutzung von Rados Auswahlprinzip ergeben sich unter anderem:

• Der Satz von de Bruijn - Erdős:^[9]

Ein Graph ist   ${\displaystyle k}$-färbbar (  ${\displaystyle k\in \mathbb {N} }$ ) dann und nur dann, wenn jeder endliche induzierte Teilgraph   ${\displaystyle k}$-färbbar ist.

• Der Satz von Dilworth (transfinite Version):^[10][11][12]

Eine unendliche teilweise geordnete Menge der Breite   ${\displaystyle w\in \mathbb {N} }$  lässt sich stets in   ${\displaystyle w}$  paarweise disjunkte Ketten zerlegen.

• Der Heiratssatz (transfinite Version):^[13][14]

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:^[15]

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:^[16]

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

Literatur

Artikel und Originalarbeiten

• 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. 
• W. H. Gottschalk: Choice functions and Tychonoff's theorem. In: Proc. Amer. Math. Soc. Band 2, 1951, S. 172. 

Monographien

• Egbert Harzheim: Ordered Sets. Springer-Verlag, New York 2005, ISBN 0-387-24219-8. 
• Heinz Lüneburg: Kombinatorik. Birkhäuser Verlag, Basel u. a. 1971, ISBN 3-7643-0548-7. 
• Martin Aigner: Combinatorial Theory (= Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Band 234). Springer-Verlag, Berlin, New York 1979, ISBN 0-387-90376-3 (MR0542445). 
• Leonid Mirsky: Transversal Theory. Academic Press, New York/ London 1971, ISBN 0-12-498550-5. 

Einzelnachweise

1. ↑ H. Lüneburg: Kombinatorik. 1971, S. 61. 
2. ↑ L. Mirsky: Transversal Theory. 1971, S. 52. 
3. ↑ E. Harzheim: Ordered Sets. 2005, S. 234. 
4. ↑ W. H. Gottschalk: Choice functions and Tychonoff's theorem. 1951, S. 172. 
5. ↑ H. Lüneburg: Kombinatorik. 1971, S. 61–62. 
6. ↑ E. Harzheim: Ordered Sets. 2005, S. 234. 
7. ↑ L. Mirsky: Transversal Theory. 1971, S. 52. 
8. ↑ ${\displaystyle {{\upharpoonright }J}}$   steht für die Einschränkung auf ${\displaystyle J}$
9. ↑ M. Aigner: Combinatorial Theory. 1979, S. 410. 
10. ↑ M. Aigner: Combinatorial Theory. 1979, S. 410. 
11. ↑ E. Harzheim: Ordered Sets. 2005, S. 60. 
12. ↑ 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.
13. ↑ M. Aigner: Combinatorial Theory. 1979, S. 409. 
14. ↑ H. Lüneburg: Kombinatorik. 1971, S. 65. 
15. ↑ H. Lüneburg: Kombinatorik. 1971, S. 63. 
16. ↑ H. Lüneburg: Kombinatorik. 1971, S. 64.