 |
 |
 |
 |
 |
 |
Startseite » Forum » Wohlfundierte Ordnung
Wohlfundierte Ordnung
Universität / Fachhochschule
Sonstiges
Tags: Ordnung, Ordnungsrelation, Sonstig, Wohlfundierte Ordnung
 
|
  |
|---|
|
Hallo, hier mal eine Aufgabe: Zeigen Sie, dass , mit , eine wohlfundierte Ordnung auf ist. Also das ist in der Aufgabe so ein Dreieck, also vermutlich ein Relationszeichen. Ok, wohlfundierte Ordnung, wann ist eine Ordnung wohlfundiert? Wenn sie keine absteigende unendliche Kette hat oder? Und wenn jede nicht-leere Teilmenge ein minimales Element hat? Ok schön, wie zeige ich das?? :-D) LG Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, wie sieht denn . eine Kette in dieser Ordnung aus? Nimm dir doch mal ein oder zwei Zahlen und schaue mal, wie hier maximale Ketten (also Ketten, mit maximal vielen Elementen) aussehen. Vlt bringt dich das auf eine Idee... Grüße Sina |
 |
|
Hallo Sina, vielen Dank für deine Antwort. Erstmal noch kurz eine Frage zur Angabe, bei zB , und nicht 4 oder gilt das trotzdem, weil 4 in der gleichen Restklasse wie 0 ist, also wegen Falls ja, dann wäre die Relation einfach eine aufsteigende Kette der geraden Zahlen, also Oder? LG |
|
|
|
Hallo, genau, die maximale Kette, die zu 2 und 4 gleichermaßen gehört, sind die geraden Zahlen. Genauso gehört zu 1 und 3 die Kette der ungeraden Zahlen. Offensichtlich zerfällt komplett in diese beiden Ketten... Nun solltest du dir folgende Frage stellen: Sind diese beiden Ketten nach unten beschränkt (wenn ja, wodurch)? Wenn ich nun eine beliebige andere Kette nehme, in welchem Zusammenhang steht diese dann zu den beiden Ketten? Grüße Sina |
|
|
|
Vielen Dank für deine Antwort. Also nach unten sind sie auf jeden Fall beschränkt und zwar durch die Definition der natürlichen Zahlen, d.h. 1 bzw. 2 ist das kleinste Element. Dass diese beliebige andere Kette auch nach unten beschränkt ist und zwar auch durch 1 bzw. 2. Oder? Dann müsste dies nur noch gezeigt (bewiesen) werden :-D) Wie gehe ich das am besten an? LG |
|
|
|
Warum ist denn jede beliebige andere Kette nach unten beschränkt? Welchen Zusammenhang hat eine beliebige Kette mit der Kette der geraden, bzw. die Kette der ungeraden Zahlen? |
|
|
|
Laut Definition kann eine Kette ja nur ungerade oder gerade sein oder? Und die sind dann jeweils durch 1 bzw. 2 beschränkt, da es um die natürlichen Zahlen geht. |
|
|
|
Was meinst du mit "eine Kette kann nur ungerade oder gerade sein"? Du scheinst mir auf den richtigen Weg zu sein. |
|
|
|
Hmmm... :-) Also wenn du Lust hast, kannst du mir gerne den Beweis vorführen, danach ist eh immer alles viel klarer :-) LG |
|
|
|
Und genau deswegen tue ich es nicht... Beweise sind wie das Ei des Kolumbus in der Mathematik. Wenn man den Beweis hat, ist alles klar und man sagt sich: hätte ich auch gekonnt. Man muss aber drauf kommen. Also, nehmen wir mal ein Beispiel. Angenommen ist eine Kette bzgl. der vorgegebenen Ordnung. Sei nun die Kette der geraden Zahlen, die Kette der ungeraden Zahlen. D.h. . Was kannst du nun über bzgl. und sagen? Und gehe diesmal bitte nur auf diese Frage ein und gebe dir Mühe damit (ich stelle diese Frage jetzt zum 3. mal). Wenn du mich noch mal nach einem fertigen Beweis fragst, verlasse ich den Thread... Grüße Sina |
|
|
|
Okay sorry :-P) Vielen Dank für deine Geduld!! Okay also und Genau und wie du bereits gesagt hast zerfällt in diese beiden Ketten. Wenn man jetzt eine beliebige Kette nimmt, dann muss diese, damit die Angabe stimmt, eine Teilmenge einer diesen beiden Ketten sein und diese Kette hat mindestens (genauer gesagt genau) ein minimales Element und deshalb ist die gegebene Ordnung wohlfundiert. |
|
|
|
Genau so ist es.... Jetzt hast du also einen Fahrplan, wie du den Beweis zeigen kannst. 1. Zeige, dass die vorgegebene wohlfundierte Ordnung in der Tag eine Ordnung ist (Reflexivität, Transitivität, Antisymmetrie)! 2. Zeige, dass und Ketten in dieser Ordnung sind (nach Definition einer Kette). 3. Zeige formal (nach Definition eines minimalsten Elements), dass das minimale Element von , bzw. das von ist. 4. Sei eine weitere beliebige Kette (egal ob endlich, oder nicht endlich). Zeige, dass , bzw. ist. 5. Folgere aus 4., dass die Ordnung wohlfundiert ist. |
|
|
|
Vielen Dank für deine Antwort. Ok zu 1. hier hab ich schon mal ein Problem, denn diese Ordnung kann keine Halbordnung sein, denn für Reflexivität müsste ich ja zeigen, dass , das wird aber problematisch, denn x ist nicht kleiner als x. Anti-Symmetrie kann ich auch nicht zeigen. Also ich würd jetzt mal vermuten, dass es eine strikte Totalordnung ist, aber eine wohlfundierte Ordnung ist doch immer eine Halbordnung oder?? Jetzt bin ich verwirrt :O //edit: Auf Wikipedia steht: "Wohlfundierte Relationen sind stets irreflexiv." Also muss ich nur Irreflexivität und Transitivität zeigen?? Ich probiers mal: Irreflexiv: , da x nicht kleiner als x ist, passt. Transitiv: , Falls x<y ist und y<z ist, muss x<z sein und wenn gilt, was nichts anderes heißt als , dann muss 2 auch x-z teilen. Die Relationsbedingung wird nur erfüllt, wenn man für x und y jeweils eine gerade oder eine ungerade Zahl einsetzt, dann und nur dann ist die Bedingung erfüllt, dass beide in der selben Restklasse bzw. sind. Man sieht zerfällt in eine aufsteigend unendliche Kette mit geraden Zahlen und in eine aufsteigend unendliche Kette mit ungeraden Zahlen . a ist ein minimales Element Das bedeutet nach Definition der natürlichen Zahlen ist 1 ein minimales Element bzw. sogar ein Minimum von und 2 ein minimales Element bzw. ein Minimum von . Da 1 bzw. 2 nie auf der rechten Seite der Relation sein kann. D.h. beide Ketten sind nach unten hin begrenzt durch 1 bzw. 2. Daraus folgt auch, dass jede nicht-leere Teilmenge von bzw. ein minimales Element hat. Und daraus folgt ist wohlfundiert. Okay vermutlich ist das mathematisch nicht wirklich korrekt, allerdings weiß ich nicht wie ich das besser machen kann. Eine "Kette" haben wir leider nie definiert, daher kenn ich davon auch keine Definition. LG |
|
|
|
Hallo, ja, hier hast du wohl Recht. Ich habe mich hier selber vom Begriff "Ordnung" irre leiten lassen. Du musst nur die Irreflexibilität und die Transitivität zeigen. BITTE NIEMALS AUF WIKIPEDIA BEZIEHEN, WENN ES UM DEINE AUFGABEN GEHT!!! Es kann nämlich sein, dass unterschiedliche Autoren (z.B. auf Wikipedia und dein Dozent) unterschiedliche Definitionen mit denselben Namen belegen. Deswegen ist Wikipedia ok, um sich mal eine Idee zu bilden. Aber wenn es ans Eingemachte geht, sind deine Vorlesungsunterlagen / das in der VL verwendete Buch die einzige Quelle, die du verwenden solltest. Zur Transitivität: Du schreibst: Das musst du beweisen bzw. dich hier auf einen bereits bewiesenen Satz aus der VL beziehen. "Die Relationsbedingung wird nur erfüllt, wenn man für x und y jeweils eine gerade oder eine ungerade Zahl einsetzt, dann und nur dann ist die Bedingung erfüllt, dass beide in der selben Restklasse [0]2 bzw. [1]2 sind." - Beweis? "Man sieht ℕ zerfällt in eine aufsteigend unendliche Kette mit geraden Zahlen :=Kg⊂ℕ und in eine aufsteigend unendliche Kette mit ungeraden Zahlen :=Ku⊂ℕ." - wenn du das vorherige gezeigt hast, ist dieser Zerfall klar. Jedoch solltest du den Begriff Kette nicht verwenden, wenn ihr ihn nicht definiert habt. Dann nimm lieber den Begriff "Teilmenge". "Das bedeutet nach Definition der natürlichen Zahlen ist 1 ein minimales Element bzw. sogar ein Minimum von Ku und 2 ein minimales Element bzw. ein Minimum von Kg." - das ist etwas schwammig, aber da du dich auf die Definition der natürlichen Zahlen berufst, würde ich es wohl durchgehen lassen. Ggf. solltest du das mit deinem Tutor (?) besprechen. "Daraus folgt auch, dass jede nicht-leere Teilmenge von Kg bzw. Ku ein minimales Element hat." - das ist richtig. Allerdings ist das nicht der Knackpunkt. Denn mit Teilmengen der beiden Teilmengen der geraden und ungeraden Zahlen deckst du nicht alle möglichen Teilmengen ab. Wir müssen jetzt erst mal rausfinden, was genau du zeigen musst. Ich kenne nur die Definition von wohlfundierten Ordnungen über absteigende Ketten. Wenn du keine Definition von einer Kette hast, dann macht das ganze keinen Sinn. Bitte schaue in deine Unterlagen, wie eine wohlfundierte Ordnung definiert ist und schreibe den Wortlaut hier hin. Der "schwierige" Part wäre nämlich nun, zu zeigen, dass jede Kette eine Teilmenge von entweder oder ist. Grüße Sina |
|
|
|
Hallo, vielen vielen Dank für deine Antwort, sorry dass ich erst so spät schreibe, bin aber nicht wirklich dazu gekommen. Zur Transitivität. Die Teilbarkeit beweisen, also die Definition von | und einsetzen oder scheiterts generell schon an der Transitivität? Bei der tue ich mir immer sehr schwer diese zu beweisen, obwohl ich die Definition genau kenne :( Wie beweise ich das am besten mit den Restklassen?? Ok, ja Teilmenge ist viel besser :-) Wohlfundierte Ordnung ist so definiert: "A strict partial order on M is called well-founded if every , with has at least one minimal element relative to . A poset is called a well-founded poset if is well-founded." Aber ist das normal, dass der Beweis so lang wird? Wir müssen sowas immer an der Tafel vorführen, wenn man das alles aufschreibt, wird man ja alt :-) LG |
|
|
|
Hallo nochmal, also das mit der Transitivität hab ich hinbekommen, einfach in eine Gleichung umgeformt, dann eingesetzt und darauf gekommen, dass 2|x-z. Laut unserer Definition aus dem Skript muss ich ja nur zeigen, dass es eben eine strenge Halbordnung ist, was ich ja schon gemacht habe, durch irreflexiv und transitiv und, dass jede nicht-leere Teilmenge ein minimales Element hat. D.h. ich zeige ist min. Element Da wir gezeigt haben, dass unsere Ordnung eine strenge Halbordnung ist mit , kann ja nie auf der rechten Seite stehen, somit hat unsere Menge ein minimales Element. Und wenn man daraus eine nicht-leere Teilmenge nimmt, und es ja kein gibt, muss auch diese wieder ein minimales Element haben. Eigentlich sollte das dann reichen, vielleicht könnte man die letzten zwei Absätze etwas mathematischer korrekt schreiben?? Wie? LG |
|
|
|
Hallo, das letzte ergibt nicht wirklich Sinn. Was soll denn sein? Ein beliebiges Element? Dann gilt das bestimmt nicht, z.B. kann auf jeden Fall mal auf der rechten Seite stehen. Ich finde diese Definition über "jede nicht-leere Teilmenge enthält mindestens ein minimales Element" äußerst seltsam... Aber gut, wenn das dort so steht. Das macht die Sache eigentlich etwas einfacher. Vergiss diese Argumentation über "x kann nie auf der rechten Seite stehen". Das versteht man nicht, außerdem wird die erste Frage sein: Warum kann nicht auf der rechten Seite stehen, kannst du das beweisen? Und damit bist du wieder raus. Nimm eine nicht leere Teilmenge . Dann kannst du diese Menge mit und schneiden. Mindestens einer dieser beiden Schnitte ist nicht leer (warum?). Nimm den nicht-leeren Schnitt (hier verwendet man dann so etwas wie "o.B.d.A. sei "). Und jetzt musst du überlegen, warum ein minimales Element besitzt. ACHTUNG! Die Begründung, dass ein minimales Element besitzt, reicht nicht aus, denn im Allgemeinen ist dieses nicht in enthalten. Das bedeutet zunächst mal nur, dass nach unten beschränkt ist. Das ist aber nicht gleichbedeutend mit der Existenz eines minimalen Elements! Was die Beweislänge angeht, dazu kann ich nichts sagen. Letztendlich musst du mit deinem Tutor / Dozent absprechen, was du alles vorführen musst. Vlt. kannst du auf ein paar Schritte verzichten. Aber der Beweis ist nun einmal, wie er ist... Beste Grüße und gute Nacht! Sina |
|
|
|
Hallo Sina, vielen Dank nochmal für deine Antwort, aber ich glaub ich kapituliere. Ja eine nichtleere Teilmenge muss ja irgendwelche Zahlen beinhalten und diese Zahl/Zahlen müssen ja entweder ungerade oder gerade sein, deshalb sind sie auch entweder in oder in Und logischerweise hat diese Teilmenge M wieder ein minimales Element bzw. 2, wenn naemlich M={1,2,3,4}, dann sind die minimalen Elemente 1 und 2. Aber ich habe keine Ahnung wie ich das beweise. Trotzdem vielen Dank! LG |
 |
|
Wollt mich nochmal bedanken!!! LG |
1304000
1303082