Auswahlprinzip von Rado

aus Wikipedia, der freien Enzyklopädie

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Y } die Notation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X {\subset \subset} Y} , dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X } eine endliche Teilmenge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Y} ist. Rados Auswahlprinzip lässt sich damit formulieren wie folgt:[5][6][7]

Gegeben seien eine nicht-leere Indexmenge   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I }  , eine nicht-leere Grundmenge  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M }   und in  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M }   eine Mengenfamilie   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal M = (M_i)_{i \in I}}   , bestehend aus nicht-leeren Teilmengen  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_i {\subset \subset} M }   ( Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in I }  ).
Ferner sei zu jeder endlichen Unterfamilie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal M_J = (M_j)_{j \in J}}   (  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J {\subset \subset} I}  ) eine Auswahlfunktion  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {{\alpha}_J} }   gegeben.
Dann existiert für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal M }   eine Auswahlfunktion  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\alpha} }  , welche eine teilweise Fortsetzung der  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {{\alpha}_J} }   (  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J {\subset \subset} I}  ) darstellt dergestalt, dass es zu jeder dieser Indexmengen   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J {\subset \subset} I }   eine ebensolche Indexmenge   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K }   gibt mit   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J \subseteq K {\subset \subset} I}   und  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -färbbar (  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \in \N }  ) dann und nur dann, wenn jeder endliche induzierte Teilgraph   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -färbbar ist.
Eine unendliche teilweise geordnete Menge der Breite   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \in \N }   lässt sich stets in   Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w }   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

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).
  • 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. ↑ Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {{\upharpoonright}J}}   steht für die Einschränkung auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.
Abgerufen von „https://de.wikiup.org/index.php?title=Auswahlprinzip_von_Rado&oldid=224291565“