Lexikographische Ordnung < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] \le [/mm] eine partielle Ordnung auf der nicht-leeren Menge M. Definiere eine Relation <|| auf [mm] M^{n} [/mm] durch:
u = [mm] (u_1,...,u_n) [/mm] <|| v = [mm] (v_1,...,v_n) [/mm] genau dann, wenn
(1) u = v oder
(2) [mm] u_i [/mm] < [mm] v_i [/mm] für das kleinste i mit [mm] u_i \not= v_i.
[/mm]
Zeige:
a) <|| ist eine partielle Ordnung auf [mm] M^n
[/mm]
b) Ist <= eine totale Ordnung auf M, so ist <|| eine totale Ordnung auf [mm] M^{n}. [/mm] |
Hallo zusammen,
ich bräuchte Hilfe bei der Aufgabe.
Zu a)
Also für die partielle Ordnung sind die Reflexivität, Antisymmetrie und die Transitivität zu zeigen:
Reflexivität:
[mm] \forall [/mm] u [mm] \in M^{n}: [/mm] u <|| u, denn
u = u (nach (1))
Antisymmetrie:
[mm] \forall [/mm] u,v [mm] \in M^{n}: [/mm] u <|| v und v <|| u => u = v, denn
[mm] u_i [/mm] < [mm] v_i [/mm] und [mm] v_i [/mm] < [mm] u_i [/mm] für das kleinste i mit [mm] u_i \not= v_i [/mm] ist ein Widerspruch, also muss in diesem Fall u = v (nach (1)).
Transitivität:
[mm] \forall [/mm] u,v,w [mm] \in M^{n}: [/mm] u <|| v und v <|| w => u <|| w, denn
...
Hier vermute ich fast, dass ich eine Fallunterscheidung brauche?
Also für die Fälle alle drei Elemente aus [mm] M^{n} [/mm] gleich, zwei gleich und alle Elemente unterschiedlich:
1. Fall u = v = w:
u = v => u <|| v (nach (1))
v = w => v <|| w (nach (1))
Einsetzen von u für v:
u <|| w
2. Fall u [mm] \not= [/mm] v [mm] \not= [/mm] w
Voraussetzung:
[mm] u_i [/mm] < [mm] v_i [/mm] für das kleinste i
und [mm] v_i [/mm] < [mm] w_i [/mm] für das kleinste i
Also ist [mm] u_i [/mm] < [mm] w_i [/mm] und damit
[mm] u_i [/mm] <|| [mm] w_i
[/mm]
Reicht das als Begründung? Kommt mir recht kurz vor, aber was soll man dazu noch zeigen?
3. Fall u [mm] \not= [/mm] v, v = w
Voraussetzung:
[mm] u_i [/mm] < [mm] v_i [/mm] für das kleinste i
v = w
Also ist
[mm] u_i [/mm] < [mm] w_i [/mm] da v = w.
Bin mir bei der ganzen Sache ziemlich unsicher. Sind die Fälle überhaupt richtig gewählt?
Zur b)
Hier weiß ich gar nicht was ich machen muss.
Die hinreichende Bedingung ist, dass <= eine totale Ordnung auf M ist, die notwendige dann, dass <|| eine totale Ordnung auf [mm] M^{n} [/mm] ist.
Muss ich jetzt hier erstmal zeigen, dass [mm] \le [/mm] eine totale Ordnung auf M ist? Also Reflexivität, Antisymmetrie, Transitivität und Totalität? Dies könnt ich mir noch vorstellen, aber wie ich dann die Implikation zeige, dass dann <|| eine totale Ordnung auf [mm] M^{n} [/mm] ist, kann ich mir überhaupt nicht vorstellen.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=146765&post_id=1076971
Danke und Grüße,
Franky
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:51 Sa 13.11.2010 | | Autor: | moudi |
> Sei [mm]\le[/mm] eine partielle Ordnung auf der nicht-leeren Menge
> M. Definiere eine Relation <|| auf [mm]M^{n}[/mm] durch:
>
> u = [mm](u_1,...,u_n)[/mm] <|| v = [mm](v_1,...,v_n)[/mm] genau dann, wenn
> (1) u = v oder
> (2) [mm]u_i[/mm] < [mm]v_i[/mm] für das kleinste i mit [mm]u_i \not= v_i.[/mm]
>
> Zeige:
> a) <|| ist eine partielle Ordnung auf [mm]M^n[/mm]
> b) Ist <= eine totale Ordnung auf M, so ist <|| eine
> totale Ordnung auf [mm]M^{n}.[/mm]
> Hallo zusammen,
>
> ich bräuchte Hilfe bei der Aufgabe.
>
> Zu a)
> Also für die partielle Ordnung sind die Reflexivität,
> Antisymmetrie und die Transitivität zu zeigen:
> Reflexivität:
> [mm]\forall[/mm] u [mm]\in M^{n}:[/mm] u <|| u, denn
> u = u (nach (1))
>
>
> Antisymmetrie:
> [mm]\forall[/mm] u,v [mm]\in M^{n}:[/mm] u <|| v und v <|| u => u = v, denn
> [mm]u_i[/mm] < [mm]v_i[/mm] und [mm]v_i[/mm] < [mm]u_i[/mm] für das kleinste i mit [mm]u_i \not= v_i[/mm]
> ist ein Widerspruch, also muss in diesem Fall u = v (nach
> (1)).
>
>
> Transitivität:
> [mm]\forall[/mm] u,v,w [mm]\in M^{n}:[/mm] u <|| v und v <|| w => u <|| w,
> denn
> ...
> Hier vermute ich fast, dass ich eine Fallunterscheidung
> brauche?
> Also für die Fälle alle drei Elemente aus [mm]M^{n}[/mm] gleich,
> zwei gleich und alle Elemente unterschiedlich:
Ich glaube die Faelle $u=v=w$, $u=v<w$ und $u<v=w$ sind klar und brauchen keine Erlaeuterung. Es geht vor allem um den Fall $u<v<w$, denn es zu untersuchen gilt, also dein Fall 2.
> 1. Fall u = v = w:
> u = v => u <|| v (nach (1))
> v = w => v <|| w (nach (1))
> Einsetzen von u für v:
> u <|| w
>
> 2. Fall u [mm]\not=[/mm] v [mm]\not=[/mm] w
> Voraussetzung:
> [mm]u_i[/mm] < [mm]v_i[/mm] für das kleinste i
> und [mm]v_i[/mm] < [mm]w_i[/mm] für das kleinste i
> Also ist [mm]u_i[/mm] < [mm]w_i[/mm] und damit
> [mm]u_i[/mm] <|| [mm]w_i[/mm]
> Reicht das als Begründung? Kommt mir recht kurz vor, aber
> was soll man dazu noch zeigen?
Hier musst du aufpassen, denn dass minimale i fuer das [mm] $u_i\neq v_i$ [/mm] muss nicht mit dem minimalen j fuer das [mm] $v_j\neq w_j$ [/mm] ist, uebereinstimmen. Hier brauchst du die Fallunterscheidung i<j, i=j und i>j. Aber alle drei Faelle sind einfach.
>
> 3. Fall u [mm]\not=[/mm] v, v = w
> Voraussetzung:
> [mm]u_i[/mm] < [mm]v_i[/mm] für das kleinste i
> v = w
> Also ist
> [mm]u_i[/mm] < [mm]w_i[/mm] da v = w.
>
> Bin mir bei der ganzen Sache ziemlich unsicher. Sind die
> Fälle überhaupt richtig gewählt?
>
>
> Zur b)
> Hier weiß ich gar nicht was ich machen muss.
> Die hinreichende Bedingung ist, dass <= eine totale
> Ordnung auf M ist, die notwendige dann, dass <|| eine
> totale Ordnung auf [mm]M^{n}[/mm] ist.
> Muss ich jetzt hier erstmal zeigen, dass [mm]\le[/mm] eine totale
> Ordnung auf M ist? Also Reflexivität, Antisymmetrie,
> Transitivität und Totalität? Dies könnt ich mir noch
> vorstellen, aber wie ich dann die Implikation zeige, dass
> dann <|| eine totale Ordnung auf [mm]M^{n}[/mm] ist, kann ich mir
> überhaupt nicht vorstellen.
Es geht nur darum zu zeigen wenn [mm] $\leq$ [/mm] eine totale Ordnung auf M ist, dann ist $<||$ eine totale Ordnung auf [mm] $M^n$. [/mm] Nimm also an, dass in M alle Elemente vergleichbar sind. Jetzt musst du zeigen, dass wenn [mm] $u=(u_1,\dots, u_n)$ [/mm] und [mm] $v=(v_1,\dots,v_n)$ [/mm] zwei Elemente in [mm] $M^n$ [/mm] sind, sie auch vergleichbar sind, d.h. es gilt entweder $u<v$ oder $u=v$ oder $u>v$.
>
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
>
> http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=146765&post_id=1076971
>
> Danke und Grüße,
> Franky
mfG Moudi
|
|
|
|
