Zorns Lemma - Zorn's lemma

Mit dem Lemma von Zorn kann man zeigen, dass jeder zusammenhängende Graph einen aufspannenden Baum hat . Die Menge aller Untergraphen, die Bäume sind, ist nach Inklusion geordnet, und die Vereinigung einer Kette ist eine obere Schranke. Das Lemma von Zorn besagt, dass ein maximaler Baum existieren muss, der ein aufspannender Baum ist, da der Graph zusammenhängend ist. Für endliche Graphen, wie den hier abgebildeten, wird das Lemma von Zorn nicht benötigt.

Zorns Lemma , auch bekannt als Kuratowski-Zorn-Lemma , nach den Mathematikern Max Zorn und Kazimierz Kuratowski , ist ein Satz der Mengenlehre . Sie besagt, dass eine partiell geordnete Menge mit oberen Schranken für jede Kette ( dh jede total geordnete Teilmenge ) notwendigerweise mindestens ein maximales Element enthält .

Bewiesen durch Kuratowski 1922 und unabhängig von Zorn im Jahr 1935, das Lemma tritt in den Beweisen von mehreren Sätzen von entscheidenden Bedeutung, zum Beispiel des Satz von Hahn-Banach in Funktionsanalyse der Satz, dass jeder Vektorraum eine hat Basis , Satz von Tychonoff in Topologie dass jedes Produkt kompakter Räume kompakt ist, und die Sätze der abstrakten Algebra, dass in einem Ring mit Identität jedes echte Ideal in einem maximalen Ideal enthalten ist und dass jeder Körper einen algebraischen Abschluss hat .

Zorns Lemma ist äquivalent zum Wohlordnungssatz und auch zum Auswahlaxiom in dem Sinne, dass eines der drei zusammen mit den Zermelo-Fraenkel-Axiomen der Mengenlehre ausreicht, um die anderen beiden zu beweisen. Eine frühere Formulierung von Zorns Lemma ist das Maximumprinzip von Hausdorff, das besagt, dass jede total geordnete Teilmenge einer gegebenen partiell geordneten Menge in einer maximalen total geordneten Teilmenge dieser partiell geordneten Menge enthalten ist.

Motivation

Um die Existenz eines mathematischen Objekts zu beweisen, das in irgendeiner Weise als maximales Element in einer teilweise geordneten Menge angesehen werden kann , kann man versuchen, die Existenz eines solchen Objekts zu beweisen, indem man annimmt, dass es kein maximales Element gibt und die transfinite Induktion und die Annahmen von die Situation einen Widerspruch zu bekommen. Das Lemma von Zorn räumt die Bedingungen auf, die eine Situation erfüllen muss, damit ein solches Argument funktioniert, und ermöglicht es Mathematikern, das transfinite Induktionsargument nicht jedes Mal von Hand wiederholen zu müssen, sondern nur die Bedingungen von Zorns Lemma zu überprüfen.

Wenn Sie ein mathematisches Objekt in Etappen bauen und feststellen, dass (i) Sie auch nach unendlich vielen Etappen noch nicht fertig sind und (ii) nichts Sie davon abhält, weiter zu bauen, dann kann Zorns Lemma möglicherweise hilfreich sein Sie.

-  William Timothy Gowers , "Wie man Zorns Lemma verwendet"

Aussage des Lemmas

Vorbemerkungen:

  • Eine Menge P, die mit einer reflexiven , antisymmetrischen und transitiven binären Relation ≤ ausgestattet ist, heißt (teilweise) geordnet nach . Gegeben seien zwei Elementen x und y von P mit xy , y wird gesagt, dass mehr als oder gleich zu x . Das Wort "partiell" soll andeuten, dass nicht jedes Paar von Elementen einer teilgeordneten Menge unter der Ordnungsrelation vergleichbar sein muss, d.h. in einer teilgeordneten Menge P mit der Ordnungsrelation ≤ kann es Elemente x und y geben wobei weder xy oder yx . Eine geordnete Menge, in der jedes Paar von Elementen vergleichbar ist, heißt total geordnet .
  • Jede Teilmenge S einer teilgeordneten Menge P kann selbst als teilgeordnet angesehen werden, indem die von P auf S vererbte Ordnungsrelation eingeschränkt wird . Eine Teilmenge S einer teilweise geordneten Menge P heißt Kette (in P ), wenn sie in der ererbten Ordnung vollständig geordnet ist.
  • Ein Element m einer teilweise geordneten Menge P mit Ordnungsrelation ≤ ist maximal (bezüglich ≤) , wenn es kein anderes Element ist P größer ist als m , das heißt, wenn es keine s in P mit nm und ms . Je nach Ordnungsrelation kann eine teilgeordnete Menge beliebig viele maximale Elemente haben. Eine total geordnete Menge kann jedoch höchstens ein maximales Element haben.
  • Gegeben eine Teilmenge S einer teilweise geordneten Menge P ist ein Element u von P eine obere Schranke von S, wenn es größer oder gleich jedem Element von S ist . Hier muss S keine Kette sein und u muss mit jedem Element von S vergleichbar sein, muss aber nicht selbst ein Element von S sein .

Das Lemma von Zorn kann dann wie folgt formuliert werden:

Lemma von Zorn  —  Angenommen, eine partiell geordnete Menge P hat die Eigenschaft, dass jede Kette in P eine obere Schranke in P hat . Dann enthält die Menge P mindestens ein maximales Element .

Manchmal werden Varianten dieser Formulierung verwendet, wie zum Beispiel, dass die Menge P und die Ketten nicht leer sein müssen.

Lemma von Zorn  (für nichtleere Mengen)  —  Angenommen, eine nichtleere, teilweise geordnete Menge P hat die Eigenschaft, dass jede nichtleere Kette eine obere Schranke in P hat . Dann enthält die Menge P mindestens ein maximales Element.

Obwohl diese Formulierung formal schwächer zu sein scheint (da sie an P die zusätzliche Bedingung stellt, nicht leer zu sein, aber die gleiche Schlussfolgerung über P erhält ), sind die beiden Formulierungen tatsächlich äquivalent. Um dies zu überprüfen, nehmen wir zunächst an, dass P die Bedingung erfüllt, dass jede Kette in P eine obere Schranke in P hat . Dann ist die leere Teilmenge von P eine Kette, da sie die Definition leer erfüllt ; die Hypothese impliziert also, dass diese Teilmenge eine obere Schranke in P haben muss , und diese obere Schranke zeigt, dass P tatsächlich nicht leer ist. Umgekehrt, wenn P als nichtleer angenommen wird und die Hypothese erfüllt, dass jede nichtleere Kette eine obere Schranke in P hat , dann erfüllt P auch die Bedingung, dass jede Kette eine obere Schranke hat, da ein beliebiges Element von P als dient eine obere Schranke für die leere Kette (d. h. die leere Teilmenge, die als Kette betrachtet wird).

Der Unterschied mag subtil erscheinen, aber in vielen Beweisen, die Zorns Lemma berufen, nimmt man Vereinigungen irgendeiner Art, um eine obere Schranke zu erzeugen, und so kann der Fall der leeren Kette übersehen werden; das heißt, die Überprüfung, dass alle Ketten obere Schranken haben, muss möglicherweise mit leeren und nicht leeren Ketten getrennt umgehen. Daher ziehen es viele Autoren vor, die Nichtleerheit der Menge P zu verifizieren, anstatt sich im allgemeinen Argument mit der leeren Kette zu befassen.

Beispielanwendung

Mit dem Lemma von Zorn kann man zeigen, dass jeder nichttriviale Ring R mit Eins ein maximales Ideal enthält .

Sei P die Menge aller (zweiseitigen) Ideale in R außer R selbst. Das Ideal R wurde ausgeschlossen, weil maximale Ideale per Definition nicht gleich R sind . Da R nicht trivial ist, enthält die Menge P das triviale Ideal {0}, und daher ist P nicht leer. Weiterhin P teilweise durch geordnete Satz Aufnahme (siehe Aufnahme Reihenfolge ). Ein maximales Ideal in R zu finden ist dasselbe wie ein maximales Element in P zu finden .

Um das Lemma von Zorn anzuwenden, nehmen Sie eine Kette T in P (dh T ist eine Teilmenge von P , die vollständig geordnet ist). Wenn T die leere Menge ist, dann ist das triviale Ideal {0} eine obere Schranke für T in P . Angenommen, T ist nicht leer. Es muss gezeigt werden, dass T eine obere Schranke hat, d. h. es gibt ein Ideal IR, das größer ist als alle Mitglieder von T, aber immer noch kleiner als R (sonst wäre es nicht in P ). Nehmen Sie I als die Vereinigung aller Ideale in T an . Wir wollen zeigen, dass I eine obere Schranke für T in P ist . Wir werden zuerst zeigen, dass I ein Ideal von R ist , und dann, dass es ein echtes Ideal von R und somit ein Element von P ist . Da jedes Element von T in I enthalten ist , zeigt dies, dass I wie erforderlich eine obere Schranke für T in P ist.

Da T mindestens ein Element enthält und dieses Element mindestens 0 enthält, enthält die Vereinigung I mindestens 0 und ist nicht leer. Um zu beweisen, dass I ein Ideal ist, beachte, dass, wenn a und b Elemente von I sind , es zwei Ideale J , KT gibt, so dass a ein Element von J und b ein Element von K ist . Da T total geordnet ist, wissen wir , dass JK oder KJ . Im ersten Fall sind sowohl a als auch b Glieder des Ideals K , daher ist ihre Summe a + b ein Glied von K , was zeigt, dass a + b ein Glied von I ist . Im zweiten Fall sind sowohl a als auch b Glieder des Ideals J , also a + bI . Außerdem, wenn rR , dann ar und RA sind Elemente J und somit Elemente von I . Somit ist I ein Ideal in R .

Nun ist ein Ideal gleich R genau dann, wenn es 1 enthält. (Es ist klar, dass wenn es gleich R ist , es 1 enthalten muss; wenn es andererseits 1 enthält und r ein beliebiges Element von R , dann ist r1 = r ein Element des Ideals, und daher ist das Ideal gleich R .) Wenn ich also gleich R wäre , dann würde es 1 enthalten, und das bedeutet, dass eines der Mitglieder von T 1 enthalten würde und wäre somit gleich R – aber R ist explizit aus P ausgeschlossen .

Die Hypothese von Zorns Lemma wurde überprüft, und somit gibt es ein maximales Element in P , also ein maximales Ideal in R .

Der Beweis hängt davon ab, dass der Ring R eine multiplikative Einheit 1 hat. Ohne diese würde der Beweis nicht funktionieren und tatsächlich wäre die Aussage falsch. Zum Beispiel hat der Ring mit als additive Gruppe und trivialer Multiplikation (dh für alle ) kein maximales Ideal (und natürlich keine 1): Seine Ideale sind genau die additiven Untergruppen. Die Faktorgruppe durch eine echte Untergruppe ist eine teilbare Gruppe , also sicherlich nicht endlich erzeugt , hat also eine echte nicht-triviale Untergruppe, die eine Untergruppe und ein Ideal mit enthält .

Beweisskizze

Es folgt eine Skizze des Beweises von Zorns Lemma unter Annahme des Auswahlaxioms . Angenommen, das Lemma ist falsch. Dann existiert eine partiell geordnete Menge oder ein Poset P, so dass jede total geordnete Teilmenge eine obere Schranke hat und dass für jedes Element in P ein anderes Element größer ist. Für jede total geordnete Teilmenge T können wir dann ein größeres Element b ( T ) definieren, weil T eine obere Schranke hat und diese obere Schranke ein größeres Element hat. Um die Funktion b tatsächlich zu definieren , müssen wir das Auswahlaxiom verwenden.

Mit der Funktion b werden wir Elemente a 0 < a 1 < a 2 < a 3 < ... in P definieren . Diese Folge ist wirklich lang : Die Indizes sind nicht nur die natürlichen Zahlen , sondern alle Ordinalzahlen . Tatsächlich ist die Folge für die Menge P zu lang ; es gibt zu viele Ordinalzahlen (eine richtige Klasse ), mehr als Elemente in irgendeiner Menge, und die Menge P wird bald erschöpft sein und dann werden wir auf den gewünschten Widerspruch stoßen.

Die a i sind durch transfinite Rekursion definiert : wir wählen eine 0 in P beliebig (dies ist möglich, da P eine obere Schranke für die leere Menge enthält und somit nicht leer ist) und für jede andere Ordinalzahl w setzen wir a w = b ( { ein v  : v < w }). Da die a v total geordnet sind, ist dies eine fundierte Definition.

Dieser Beweis zeigt, dass tatsächlich eine etwas stärkere Version von Zorns Lemma wahr ist:

Lemma  —  Wenn P ein Poset ist, in dem jede wohlgeordnete Teilmenge eine obere Schranke hat, und wenn x ein Element von P ist , dann hat P ein maximales Element größer oder gleich x . Das heißt, es gibt ein maximales Element, das mit x vergleichbar ist .

Geschichte

Das Hausdorffsche Maximalprinzip ist eine frühe Aussage ähnlich dem Lemma von Zorn.

Kazimierz Kuratowski bewies 1922 eine Version des Lemmas, die seiner modernen Formulierung nahe kommt (es gilt für Mengen, die durch Inklusion geordnet und unter Vereinigungen wohlgeordneter Ketten abgeschlossen sind). Im Wesentlichen dieselbe Formulierung (abgeschwächt durch die Verwendung beliebiger Ketten, nicht nur wohlgeordneter) wurde 1935 unabhängig von Max Zorn gegeben , der sie als neues Axiom der Mengenlehre vorschlug, das den wohlgeordneten Satz ersetzte, und zeigte einige ihrer Anwendungen in der Algebra , und versprach, seine Äquivalenz mit dem Auswahlaxiom in einem anderen Papier zu zeigen, das nie erschienen ist.

Der Name „Zorns Lemma“ erscheint aufgrund sein John Tukey , der es in seinem Buch verwendet Konvergenz und Homogenität in Topologie in 1940. Bourbaki ‚s Théorie des Ensembles von 1939 bezieht sich auf eine ähnliche maximale Prinzip als‚le THÉORÈME de Zorn‘. Der Name „ Kuratowski-Zorn-Lemma “ herrscht in Polen und Russland vor.

Äquivalente Formen von Zorns Lemma

Das Lemma von Zorn ist äquivalent (in ZF ) zu drei Hauptergebnissen:

  1. Hausdorff-Maximalprinzip
  2. Axiom der Wahl
  3. Ordnungssatz .

Ein bekannter Witz, der auf diese Äquivalenz anspielt (die der menschlichen Intuition widersprechen mag), wird Jerry Bona zugeschrieben : "Das Axiom der Wahl ist offensichtlich wahr, das Wohlordnungsprinzip offensichtlich falsch, und wer kann von Zorns Lemma erzählen?"

Zorns Lemma ist auch äquivalent zum starken Vollständigkeitssatz der Logik erster Ordnung.

Darüber hinaus impliziert Zorns Lemma (oder eine seiner äquivalenten Formen) einige wichtige Ergebnisse in anderen mathematischen Bereichen. Zum Beispiel,

  1. Banachs Erweiterungssatz, der verwendet wird, um eines der grundlegendsten Ergebnisse der Funktionalanalysis zu beweisen, den Hahn-Banach-Satz
  2. Jeder Vektorraum hat eine Basis , ein Ergebnis der linearen Algebra (zu der es äquivalent ist). Insbesondere besitzen die reellen Zahlen als Vektorraum über den rationalen Zahlen eine Hamelsche Basis.
  3. Jeder kommutative unitale Ring hat ein maximales Ideal , ein Ergebnis aus der Ringtheorie, bekannt als Krulls Satz , zu dem Zorns Lemma äquivalent ist
  4. Satz von Tychonoff in der Topologie (zu dem er auch äquivalent ist)
  5. Jeder richtige Filter ist in einem Ultrafilter enthalten , ein Ergebnis, das den Vollständigkeitssatz der Logik erster Ordnung liefert

In diesem Sinne sehen wir, wie Zorns Lemma als mächtiges Werkzeug angesehen werden kann, insbesondere im Sinne der vereinheitlichten Mathematik.

Analoga unter Abschwächung des Auswahlaxioms

Eine abgeschwächte Form von Zorns Lemma lässt sich aus ZF + DC beweisen (Zermelo-Fraenkel-Mengentheorie mit dem Auswahlaxiom ersetzt durch das Axiom der abhängigen Auswahl ). Das Lemma von Zorn kann einfach ausgedrückt werden, indem man beobachtet, dass die Menge ohne maximales Element der Aussage entspricht, dass die Ordnungsrelation der Menge vollständig ist, was es uns ermöglichen würde, das Axiom der abhängigen Wahl anzuwenden, um eine abzählbare Kette zu konstruieren. Folglich muss jede partiell geordnete Menge mit ausschließlich endlichen Ketten ein maximales Element haben.

Ganz allgemein erlaubt uns die Stärkung des Axioms der abhängigen Wahl auf höhere Ordinalzahlen, die Aussage im vorherigen Absatz auf höhere Kardinalitäten zu verallgemeinern. Im Grenzfall, in dem wir beliebig große Ordinalzahlen zulassen, führen wir den Beweis des vollständigen Zorn-Lemmas mit dem Auswahlaxiom aus dem vorhergehenden Abschnitt zurück.

In der Populärkultur

Der Film Zorns Lemma von 1970 ist nach dem Lemma benannt.

Das Lemma wurde auf Die Simpsons in der Episode „ Barts neuer Freund “ erwähnt.

Siehe auch

Anmerkungen

Verweise

Externe Links