Auswahlprinzip von Rado

mathematischer Satz

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

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

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.

Literatur

Bearbeiten

Artikel und Originalarbeiten

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.

Monographien

Bearbeiten

Einzelnachweise

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.