Induktion und partielle Ordnung

15.11.2005, 17:45	Andre86	Auf diesen Beitrag antworten »
Induktion und partielle Ordnung Hi Leute! Ich habe ein Problem mit der folgenden Aufgabe. Mir fällt noch nichtmal ein Anfang ein! Kann mir jemand helfen und eine Lösungvorschlag machen (bitte mit Erklärung)! Ich danke euch schon mal im voraus! Aufgabe: Zeigen Sie, dass sich eine partielle Ordnung <= auf einer endlichen Menge M stets zu einer totalen Ordnung fortsetzen lässt. (Beweis durch Induktion)
15.11.2005, 17:59	IchDerRobot	Auf diesen Beitrag antworten »
Hallo Andre, meine Idee ist folgende: Der Induktionsanfang M = {} ist trivial. Nun haben wir also eine nichtleere Menge M mit einer partiellen Ordnung $\begin{eqnarray} \leq \end{eqnarray}$ . Wählen wir ein Element x von M. Dann ist M' := M \ {x} durch $\begin{eqnarray} \leq \end{eqnarray}$ immer noch partiell geordnet, die partielle Ordnung $\begin{eqnarray} \leq\|_{M'} \end{eqnarray}$ von M' lässt sich also zu einer totalen Ordnung $\begin{eqnarray} \leq_t \end{eqnarray}$ auf M' fortsetzen. In diese Ordnung müssen wir nun das x einfügen, ohne die alte partielle Ordnung $\begin{eqnarray} \leq \end{eqnarray}$ zu zerstören. Wenn uns das gelingt, haben wir $\begin{eqnarray} \leq \end{eqnarray}$ zu einer totalen Ordnung auf M fortgesetzt. Dazu müssen wir x hinter allen Elementen einfügen, die bezüglich $\begin{eqnarray} \leq \end{eqnarray}$ kleiner sind als x, und vor allen Elementen, die bzgl. $\begin{eqnarray} \leq \end{eqnarray}$ größer sind als x. Die mit x unvergleichbaren Elemente interessieren dabei nicht. Robot
15.11.2005, 18:13	Andre86	Auf diesen Beitrag antworten »
Was bedeutet $\begin{eqnarray} [latex]\leq\|_{M'} \end{eqnarray}$ [/latex]?
15.11.2005, 18:47	JochenX	Auf diesen Beitrag antworten »
"eingeschränkt auf"
16.11.2005, 10:35	IchDerRobot	Auf diesen Beitrag antworten »
Hallo Andre, wie LOED schon sagte: $\begin{eqnarray} \leq \|_{M'} \end{eqnarray}$ ist die partielle Ordnung auf M', die entsteht, wenn ich die Elemente von M' gemäß der partiellen Ordnung $\begin{eqnarray} \leq \end{eqnarray}$ vergleiche. Wenn wir die Ordnungsrelation als Teilmenge von M x M betrachten (wie es ja für zweistellige Relationen üblich ist), dann ist $\begin{eqnarray} \leq \|_{M'} := \leq \cap (M' \times M') \end{eqnarray}$ . Ich hab eine Variante meines Weges gefunden, bei der der letzte Schritt etwas bequemer ist: Du wählst für x ein maximales Element (nicht das größte, das muss nicht existieren). Ein solches existiert, weil M endlich ist. Dann ordnest du M' wie oben beschrieben, und kannst dann x als größtes Element hinzufügen: Alle Elemente, mit denen x vergleichbar war, waren vorher und sind jetzt kleiner als x. Robot

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »