Auswahlprinzip von Rado

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Rados Auswahlprinzip)
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

Im Folgenden bedeute für zwei Mengen und die Notation , dass eine endliche Teilmenge von ist. Rados Auswahlprinzip lässt sich damit formulieren wie folgt:[5][6][7]

Gegeben seien eine nicht-leere Indexmenge    , eine nicht-leere Grundmenge    und in    eine Mengenfamilie     , bestehend aus nicht-leeren Teilmengen     (  ).
Ferner sei zu jeder endlichen Unterfamilie   (   ) eine Auswahlfunktion     gegeben.
Dann existiert für   eine Auswahlfunktion    , welche eine teilweise Fortsetzung der    (   ) darstellt dergestalt, dass es zu jeder dieser Indexmengen     eine ebensolche Indexmenge     gibt mit     und   [8].

Einige Folgerungen

[Bearbeiten | Quelltext bearbeiten]

Unter Benutzung von Rados Auswahlprinzip ergeben sich unter anderem:

  • Der Satz von de Bruijn - Erdős:[9]
Ein Graph ist   -färbbar ) dann und nur dann, wenn jeder endliche induzierte Teilgraph   -färbbar ist.
Eine unendliche teilweise geordnete Menge der Breite     lässt sich stets in     paarweise disjunkte Ketten zerlegen.
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.

Artikel und Originalarbeiten

[Bearbeiten | Quelltext bearbeiten]
  • 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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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.   steht für die Einschränkung auf
  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.