Halbordnung zu Totalordnung erweitern

04.05.2009, 12:36

pheips

Halbordnung zu Totalordnung erweitern

Servus!

Zu zeigen gilt es, dass jede Halbordnung auf einer endlichen Menge $\begin{eqnarray*} M \end{eqnarray*}$ zu einer Totalordnung fortgesetzt werden kann.

Mein Ansatz ist Induktion über die Anzahl der Elemente in $\begin{eqnarray*} M \end{eqnarray*}$ . Allerdings bin ich mir nicht ganz sicher, ob sich da ein Fehler eingeschlichen hat, weil manches nach Konstruktion offensichtlich erscheint, sodass man schon mal durcheinander kommmen kann.

IA:
$\begin{eqnarray*} |M|=1 \end{eqnarray*}$ , $\begin{eqnarray*} M=\{m\} \end{eqnarray*}$ , $\begin{eqnarray*} H\subseteq M\times M \end{eqnarray*}$ Halbordnung. Weil H Halbordnung ist, gilt $\begin{eqnarray*} (m,m) \in H \end{eqnarray*}$ und damit H bereits eine Totalordnung.

IS:
$\begin{eqnarray*} |M|=n \end{eqnarray*}$ , $\begin{eqnarray*} H_{n}\subseteq M\times M \end{eqnarray*}$ Halbordnung.
Da M endlich ist, existiert ein maximales Element $\begin{eqnarray*} m \in M \end{eqnarray*}$ , sodass
$\begin{eqnarray*} (m,a) \in M \end{eqnarray*}$ nur dann gilt, wenn $\begin{eqnarray*} a=m \end{eqnarray*}$ .

Sei $\begin{eqnarray*} M^{'}:=M\setminus \{m\} \end{eqnarray*}$ mit n-1 Elementen und
$\begin{eqnarray*} H_{n-1}:=H_{n}\setminus \{(a,m)|a\in M\} \end{eqnarray*}$

Es gilt $\begin{eqnarray*} H_{n-1}\subseteq M^{'}\times M^{'} \end{eqnarray*}$ , da m maximal ist.
Außerdem ist $\begin{eqnarray*} H_{n-1} \end{eqnarray*}$ Halbordnung (nach Konstruktion) auf $\begin{eqnarray*} M^{'} \end{eqnarray*}$ .

Nach Induktionsvoraussetzung existiert eine Totalordnung $\begin{eqnarray*} T_{n-1}\supseteq H_{n-1} \end{eqnarray*}$ auf $\begin{eqnarray*} M^{'} \end{eqnarray*}$ .

Sei $\begin{eqnarray*} T_{n}:=T_{n-1}\cup \{(a,m)|a\in M\} \end{eqnarray*}$ .

Zu zeigen $\begin{eqnarray*} T_{n} \end{eqnarray*}$ ist Totalordnung auf M und $\begin{eqnarray*} T_{n}\subseteq H_{n} \end{eqnarray*}$ :

Für $\begin{eqnarray*} a,b,c\in M^{'} \end{eqnarray*}$ folgt Transitivität, Reflexivität, Antisymmetrie und Totaliät direkt von $\begin{eqnarray*} T_{n-1} \end{eqnarray*}$ ist Totalordnung.

Es gilt also nur folgende Fälle zu betrachten, in denen m "mitspielt":
*) reflexiv für m: nach Konstruktion $\begin{eqnarray*} (m,m)\in T_{n} \end{eqnarray*}$
*) Antisymmterie für $\begin{eqnarray*} a\in M \end{eqnarray*}$ und m:
Also $\begin{eqnarray*} (a,m),(m,a) \in T_{n} \end{eqnarray*}$ , nach Konstruktion von $\begin{eqnarray*} T_{n} \end{eqnarray*}$ folgt a=m
*) Transitivität: $\begin{eqnarray*} a,b \in M \end{eqnarray*}$
1. Fall: Für $\begin{eqnarray*} (a,b),(b,m) \in T_{n} \end{eqnarray*}$ folgt $\begin{eqnarray*} (a,m) \in T_{n} \end{eqnarray*}$ nach Konstruktion.
2. Fall: Für $\begin{eqnarray*} (a,m),(m,b) \in T_{n} \end{eqnarray*}$ folgt b=m nach Konstruktion. Daraus folgt $\begin{eqnarray*} (a,b)=(a,m)\in T_{n} \end{eqnarray*}$
3. Fall: Für $\begin{eqnarray*} (m,a),(a,b) \in T_{n} \end{eqnarray*}$ folgt a=m nach Konstruktion, damit (a,b)=(m,b). Woraus nach Konstruktion b=m folgt und schlußendlich $\begin{eqnarray*} (m,b)=(m,m)\in T_{n} \end{eqnarray*}$
*) Totalität: Nach Konstruktion $\begin{eqnarray*} (a,m) \in T_{n} \end{eqnarray*}$ für alle $\begin{eqnarray*} a\in M \end{eqnarray*}$

Noch zu zeigen $\begin{eqnarray*} T_{n}\subseteq H_{n} \end{eqnarray*}$ :
Für $\begin{eqnarray*} a,b\neq m \end{eqnarray*}$ mit $\begin{eqnarray*} (a,b)\in H_{n} \end{eqnarray*}$ folgt:
$\begin{eqnarray*} (a,b)\in H_{n-1} \end{eqnarray*}$ -> $\begin{eqnarray*} (a,b)\in T_{n-1} \end{eqnarray*}$ -> $\begin{eqnarray*} (a,b)\in T_{n} \end{eqnarray*}$

Falls eines der Elemente gleich m ist, dann gibt es nur den Fall $\begin{eqnarray*} (a,m)\in H_{n} \end{eqnarray*}$ , da m maximal ist. Daraus folgt aber nach Konstruktion, dass
$\begin{eqnarray*} (a,m)\in T_{n} \end{eqnarray*}$ .

So, wie gesagt prinzipiell glaub ich, dass ich das richtig (wenn auch eventuell umständlich) gemacht habe. Allerdings, da viel aus der Konstruktion folgt, frage ich mich, ob ich eventueletwas übersehen habe, und würde daher bitte, dass vllt. jemand mal "drüberschaut".

Vielen Dank im voraus!

mfg
Philipp

04.05.2009, 16:53

Reksilat

Auf diesen Beitrag antworten »

RE: Halbordnung zu Totalordnung erweitern
Hi pheips,

Für mich sieht das alles fehlerfrei und auch bestens nachvollziehbar aus.
Liest sich gut. Freude

Zitat:

Original von pheips
Noch zu zeigen $\begin{eqnarray*} T_{n}\subseteq H_{n} \end{eqnarray*}$ :

Andersrum

Gruß,
Reksilat.

04.05.2009, 16:58

pheips

Auf diesen Beitrag antworten »

RE: Halbordnung zu Totalordnung erweitern

Zitat:

Original von Reksilat
Hi pheips,

Für mich sieht das alles fehlerfrei und auch bestens nachvollziehbar aus.
Liest sich gut. Freude

Vielen Dank! Das hört man gern. Bei konstruktiven Beweisen hab ich halt immer die Sorge, dass "sich die Katze in den Schwanz beißt".

Zitat:

Original von pheips
Noch zu zeigen $\begin{eqnarray*} T_{n}\subseteq H_{n} \end{eqnarray*}$ :

Andersrum

Genau

lG
Philipp

Neue Frage »

Antworten »

Halbordnung zu Totalordnung erweitern

Verwandte Themen