Zornsches Lemma < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:38 Sa 24.06.2006 | | Autor: | Fulla |
| Aufgabe | Sei [mm] (M,\le) [/mm] eine geordnete, nicht-leere, endliche Menge.
Zeigen Sie:
(i) Für jedes x [mm] \in [/mm] M gibt es ein maximales Element y [mm] \in [/mm] M mit x [mm] \le [/mm] y.
Insbesondere besitzt M ein maximales Element (dies ist ein Spezialfall des Zornschen Lemmas, den man beweisen kann).
Tipp: vollständige Induktion über |M|.
(ii) Hat M genau ein maximales Element, so ist dieses auch das größte Element. |
hallo zusammen!
könnte mir vielleicht jemand bei dieser aufgabe helfen?
es ist mir schon klar, dass das gilt, aber beweistechnisch stehe ich leider aufm schlauch....
lieben gruß,
Fulla
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:15 So 25.06.2006 | | Autor: | Hanno |
Hallo Florian.
> (i) Für jedes x $ [mm] \in [/mm] $ M gibt es ein maximales Element y $ [mm] \in [/mm] $ M mit x $ [mm] \le [/mm] $ y.
> Insbesondere besitzt M ein maximales Element (dies ist ein Spezialfall des Zornschen Lemmas, den man beweisen kann).
> Tipp: vollständige Induktion über |M|.
Wenn das Ganze ein Spezialfall von Zorn sein soll, dann ist wohl gemeint: jede linear geordnete Teilmenge von $M$ besitzt eine obere Schranke in $M$.
Wie in der Aufgabenstellung angedacht, lässt sich die Aussage gut induktiv beweisen. Dazu wähle zwei [mm] $x,y\in [/mm] M, [mm] x\neq [/mm] y$ mit [mm] $x\leq [/mm] y$ (wenn diese nicht existieren, ist [mm] $\leq=\Delta$ [/mm] und jedes Element maximal). Nun betrachte die Menge [mm] $M\setminus \{x\}$ [/mm] mit der von [mm] $\leq$ [/mm] induzierten Ordnung. Auf sie kannst du nun, nachdem du bewiesen hast, dass die Voraussetzungen auch für die geordnete Menge [mm] $M\setminus \{x\}$ [/mm] gelten, die Induktionsvoraussetzung anwenden. Es bleibt dann lediglich zu zeigen, dass für das Maximale Element [mm] $z\in M\setminus \{x\}$ [/mm] auch [mm] $x\leq [/mm] z$ gelten muss, falls $x$ und $z$ vergleichbar sind. Dies ist nicht schwierig.
> (ii) Hat M genau ein maximales Element, so ist dieses auch das größte Element.
Nimm an, es sei $a$ maximal, nicht jedoch das größte Element in $M$. Dann existiert ein [mm] $b\in [/mm] M$, das mit $a$ nicht vergleichbar ist. Betrachte nun ein maximales Element der Menge der mit $b$ vergleichbaren Elemente. Warum ist dieses auch maximal in $M$?
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:14 Mi 28.06.2006 | | Autor: | Fulla |
hi hanno!
danke für deine antwort! leider verstehe ich nicht so ganz, was du meinst...
ich hab mir jetzt folgendes überlegt.... kannst du mir vielleicht sagen, ob das so auch ok ist?
[mm] (M,\le) [/mm] geordnet, nicht leer, endlich => [mm] \forall [/mm] x,y [mm] \in [/mm] M gilt x [mm] \le [/mm] y [mm] \vee [/mm] y [mm] \le [/mm] x und |M|=n.
|M|=1: trivial
|M|=2: M={x,y} --> [mm] \exists! x,y\in{M}: [/mm] o.B.d.A [mm] x\le{y} [/mm] --> y ist maximal
|M|=3: [mm] M=\{{x_{1},x_{2},y}\} [/mm] --> o.B.d.A: [mm] x_{1} \le x_{2} \le{y}
[/mm]
|M|=n: [mm] M=\{ x_{1}, ... , x_{n-1},y\} [/mm] --> o.B.d.A: [mm] x_{1}\le...\le{x_{n-1}}\le{y} [/mm] --> [mm] y\ge x_{i} \forall{i=1...n} [/mm] und y ist maximales Element von M.
M hat genau ein maximales Element <--> [mm] M=\{ x_{1}, ... , x_{n-1},y\} [/mm] mit [mm] x_{1}\le...\le{x_{n-1}}\le{y} [/mm] und [mm] x_{n-1}\not={y}
[/mm]
das größte Element y ist def. als: [mm] x\le{y} \forall{x\in{M}}, [/mm] was offenbar erfüllt ist.
ist das zu "schwammig", oder kann ich das so lassen?
lieben gruß,
Flo
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:03 Mi 28.06.2006 | | Autor: | piet.t |
Hallo Flo,
so wie ich (und wohl auch Hanno) die Aufgabe verstehe ist [mm] \le [/mm] nur eine Halbordnung auf M, d.h. zwei Elemente müssen nicht immer vergleichbar sein.
Das Problem stellt sich zum ersten Mal bei |M|=2. Hier sagst du, dass O.B.d.A. [mm] x\le [/mm] y. Für eine total geordnete Menge stimmt das, für eine Halbordnung kann aber auch [mm] x\not\le [/mm] y und [mm] y\not\le [/mm] x gleichzeitig gelten.
Beispiel:
[mm]M=\{\{1,2\},\{1,3\}\}[/mm] mit der Ordnungsrelation [mm] \subseteq.
[/mm]
Es ist ja [mm]\{1,2\}\not\subseteq\{1,3\}[/mm] und gleichzeitig [mm]\{1,3\}\not\subseteq\{1,2\}[/mm].
Man muss also schon noch etwas genauer auf die Definition eines maximalen Elements eingehen. Beachte: eine nicht total geordnete Menge kann durchaus mehrere maximale Elemente haben, denn ein maximales Element ist eines, wo es kein "größeres" gibt.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:20 Mi 28.06.2006 | | Autor: | Fulla |
ja, hast recht!
in unserem skript haben wir aber nur "lokale ordnung" und "totalordnung" definiert...
in einem beweis taucht allerdings ein beweis mit diesem $ [mm] M\setminus \{x\} [/mm] $ auf. ich versteh aber nicht, warum ich das x ausschließen muss!
kannst du mir das vielleicht noch ein bisschen genauer erklären?
gruß,
Flo
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:36 Mi 28.06.2006 | | Autor: | piet.t |
> ja, hast recht!
>
> in unserem skript haben wir aber nur "lokale ordnung" und
> "totalordnung" definiert...
"lokale Ordnung" finde ich jetzt auf die schnelle nicht, aber Du kannst ja mal im ![[]](/images/popup.gif) wikipedia-Artikel nachschauen, ob das mit Halbordnung identisch ist.
>
> in einem beweis taucht allerdings ein beweis mit diesem
> [mm]M\setminus \{x\}[/mm] auf. ich versteh aber nicht, warum ich das
> x ausschließen muss!
Das M und das x stehen hier etwas unmotiviert in der Landschaft, daher kann ich das jetzt nicht so richtig einordnen.
Aber nehmen wir mal an, dass M und x entsprechend der Aufgabe definiert sind. Dann wäre das Ausschließen von x eine Möglichkeit, den Induktionsschritt durchzuführen, denn auf [mm]M\smallsetminus\{x\}[/mm] kann man ja schon mal die Induktionsannahme anwenden.
Bleibt die Frage was passiert, wenn man nun x wieder hinzufügt. Und da ist m.E. eine Fallunterscheidung angebracht:
1.Fall: x ist maximal
2. Fall: x ist nicht maximal (was heißt das nochmal nach Definition?)
Die fehlenden Teile im Beweis müsstest Du jetzt eigentlich noch selbst ausfüllen können, oder?
> kannst du mir das vielleicht noch ein bisschen genauer
> erklären?
>
> gruß,
> Flo
Gruß
piet
|
|
|
|
