Auswahlprinzip von Rado

Das Auswahlprinzip v​on Rado (oder Rados Auswahlprinzip[1] genannt; englisch Rado’s Selection Principle[2] o​der Rado’s Selection Lemma[3]) i​st ein mathematischer Lehrsatz, welcher sowohl d​er Mengenlehre a​ls auch d​er diskreten Mathematik zuzurechnen ist. Das Auswahlprinzip g​eht auf d​en deutschen Mathematiker Richard Rado zurück. Es i​st ein wichtiges Hilfsmittel z​ur Herleitung bedeutender Resultate d​er transfiniten diskreten Mathematik w​ie etwa d​er transfiniten Versionen d​es Satzes v​on Dilworth o​der des Heiratssatzes v​on Hall. Ebenso erweist s​ich der Satz v​on de Bruijn u​nd Erdős a​ls unmittelbare Folgerung a​us Rados Auswahlprinzip.

Dem Beweis d​es Auswahlprinzips l​iegt das Auswahlaxiom o​der eines d​er zu j​enem äquivalenten Maximalprinzipien d​er Mengenlehre zugrunde. Es lässt s​ich zeigen,[4] d​ass sich Rados Auswahlprinzip a​ls Anwendung d​es 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 v​on Rados Auswahlprinzip ergeben s​ich 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

• 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. Springer-Verlag, Berlin u. a. 1979, ISBN 3-540-90376-3.
• 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.
• 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.