Halbordnung zu Totalordnung < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:23 Mo 04.05.2009 | | Autor: | pheips |
| Aufgabe | | Zu zeigen gilt es, dass jede Halbordnung auf einer endlichen Menge [mm]M[/mm] zu einer Totalordnung fortgesetzt werden kann. |
Servus!
Mein Ansatz ist Induktion über die Anzahl der Elemente in [mm]M[/mm]. 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:
[mm]|M|=1[/mm], [mm]M=\{m\}[/mm], [mm]H\subseteq M\times M[/mm] Halbordnung. Weil H Halbordnung ist, gilt [mm](m,m) \in H[/mm] und damit H bereits eine Totalordnung.
IS:
[mm]|M|=n[/mm], [mm]H_{n}\subseteq M\times M[/mm] Halbordnung.
Da M endlich ist, existiert ein maximales Element [mm]m \in M[/mm], sodass
[mm](m,a) \in M[/mm] nur dann gilt, wenn [mm]a=m[/mm].
Sei [mm]M^{'}:=M\setminus \{m\}[/mm] mit n-1 Elementen und
[mm]H_{n-1}:=H_{n}\setminus \{(a,m)|a\in M\}[/mm]
Es gilt [mm]H_{n-1}\subseteq M^{'}\times M^{'}[/mm], da m maximal ist.
Außerdem ist [mm]H_{n-1}[/mm] Halbordnung (nach Konstruktion) auf [mm]M^{'}[/mm].
Nach Induktionsvoraussetzung existiert eine Totalordnung [mm]T_{n-1}\supseteq H_{n-1}[/mm] auf [mm]M^{'}[/mm].
Sei [mm]T_{n}:=T_{n-1}\cup \{(a,m)|a\in M\}[/mm].
Zu zeigen [mm]T_{n}[/mm] ist Totalordnung auf M und [mm]T_{n}\subseteq H_{n}[/mm]:
Für [mm]a,b,c\in M^{'}[/mm] folgt Transitivität, Reflexivität, Antisymmetrie und Totaliät direkt von [mm]T_{n-1}[/mm] ist Totalordnung.
Es gilt also nur folgende Fälle zu betrachten, in denen m "mitspielt":
*) reflexiv für m: nach Konstruktion [mm](m,m)\in T_{n}[/mm]
*) Antisymmterie für [mm]a\in M[/mm] und m:
Also[mm](a,m),(m,a) \in T_{n}[/mm], nach Konstruktion von [mm]T_{n}[/mm] folgt a=m
*) Transitivität: [mm]a,b \in M[/mm]
1. Fall: Für [mm](a,b),(b,m) \in T_{n}[/mm] folgt [mm](a,m) \in T_{n}[/mm] nach Konstruktion.
2. Fall: Für [mm](a,m),(m,b) \in T_{n}[/mm] folgt b=m nach Konstruktion. Daraus folgt [mm](a,b)=(a,m)\in T_{n}[/mm]
3. Fall: Für [mm](m,a),(a,b) \in T_{n}[/mm] folgt a=m nach Konstruktion, damit (a,b)=(m,b). Woraus nach Konstruktion b=m folgt und schlußendlich[mm](m,b)=(m,m)\in T_{n}[/mm]
*) Totalität: Nach Konstruktion [mm](a,m) \in T_{n}[/mm] für alle [mm]a\in M [/mm]
Noch zu zeigen [mm]T_{n}\subseteq H_{n}[/mm]:
Für [mm]a,b\neq m[/mm] mit [mm](a,b)\in H_{n}[/mm] folgt:
[mm](a,b)\in H_{n-1}[/mm]->[mm](a,b)\in T_{n-1}[/mm]->[mm](a,b)\in T_{n}[/mm]
Falls eines der Elemente gleich m ist, dann gibt es nur den Fall [mm](a,m)\in H_{n}[/mm], da m maximal ist. Daraus folgt aber nach Konstruktion, dass
[mm](a,m)\in T_{n}[/mm].
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
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mi 06.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
