Partielle / totale Ordnung < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:00 Fr 04.11.2011 | | Autor: | erha06 |
| 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,
genau diese Aufgabe war schon einmal Thema hier im Forum (ich wusste nicht, ob ich im alten Thread hätte weiterschreiben sollen...) und zwar hier
Ich habe den alten Thread durchgearbeitet und auch das meiste verstanden. Allerdings habe ich noch ein paar kleinere Fragen:
Zu Teil a): Um die Transitivität zu zeigen, muss ich ja 4 Fälle betrachten: u=v=w, u=v<w, u<v=w und u<v<w. Die ersten 3 Fälle sind mir klar.
Nun zum 4. Fall: $u<v<w$:
Dieser Fall bedeutet: [mm] $u_{i}
Ich habe versucht, mir das anhand eines Beispiels herzuleiten. Z.B. für i<j:
$ u = (a,b) $
$ v = (b,b) $
$ w = (b,c) $
Es gilt: [mm] $u_{i}
Für die beiden anderen Fälle habe ich es entsprechend analog gemacht, also:
Für i>j:
[mm] $u_{i}=v_{i}
Für i=j
[mm] $u_{i}
Ist das korrekt?
----
Nun zu Teil b). Den verstehe ich leider überhaupt nicht... Ich weiß, dass für die totale Ordnung zusätzlich zu Reflexivität, Antisymmetrie und Transitivität hier auch noch gelten muss: [mm] $\forall [/mm] x,y [mm] \in [/mm] M:$ $x [mm] \le [/mm] y [mm] \quad \vee \quad [/mm] y [mm] \ge [/mm] x$. In meinen Aufschrieben steht auch, dass diese Relation nur eine totale Ordnung für n=1 ist. Warum? Kann mir das einer erklären?
Vielen Dank
erha06
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:49 So 06.11.2011 | | Autor: | erha06 |
Da wegen technischer Probleme matheraum.de gestern kaum erreichbar war, erlaube ich mir, die Frage noch einmal zu "pushen".
|
|
|
| |
|
> 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,
>
> genau diese Aufgabe war schon einmal Thema hier im Forum
> (ich wusste nicht, ob ich im alten Thread hätte
> weiterschreiben sollen...) und zwar
> hier
>
> Ich habe den alten Thread durchgearbeitet und auch das
> meiste verstanden. Allerdings habe ich noch ein paar
> kleinere Fragen:
>
> Zu Teil a): Um die Transitivität zu zeigen, muss ich ja 4
> Fälle betrachten: u=v=w, u=v<w, u<v=w und u<v<w. Die
> ersten 3 Fälle sind mir klar.
>
> Nun zum 4. Fall: [mm]u
> Dieser Fall bedeutet: [mm]u_{i}
> muss ich ja eine weitere Fallunterscheidung durchführen
> und zwar i<j, i=j und i>j.
>
> Ich habe versucht, mir das anhand eines Beispiels
> herzuleiten. Z.B. für i<j:
> [mm]u = (a,b)[/mm]
> [mm]v = (b,b)[/mm]
> [mm]w = (b,c)[/mm]
>
> Es gilt: [mm]u_{i}
> steht u in Relation zu w.
>
> Für die beiden anderen Fälle habe ich es entsprechend
> analog gemacht, also:
>
> Für i>j:
> [mm]u_{i}=v_{i}
> in Relation zu w.
>
> Für i=j
> [mm]u_{i}
> in Relation zu w.
>
> Ist das korrekt?
>
> ----
>
> Nun zu Teil b). Den verstehe ich leider überhaupt nicht...
> Ich weiß, dass für die totale Ordnung zusätzlich zu
> Reflexivität, Antisymmetrie und Transitivität hier auch
> noch gelten muss: [mm]\forall x,y \in M:[/mm] [mm]x \le y \quad \vee \quad y \ge x[/mm].
> In meinen Aufschrieben steht auch, dass diese Relation nur
> eine totale Ordnung für n=1 ist. Warum? Kann mir das einer
> erklären?
>
> Vielen Dank
> erha06
>
>
>
>
Wenn du die Sache anhand eines Beispiels verstehen willst, solltest du dir klar machen, dass die Relation nichts anderes als eine lexikographische Ordnung beschreibt, nach der Einträge z.B. in einem Lexikon oder Telefonbuch sortiert werden.
Zum Beweis der Transitivität musst du meines Erachtens nur zwei Fälle unterscheiden: u=v=w (trivial) und eben den Fall, dass nicht alle drei gleich sind.
Dann betrachtest du die erste Stelle i für die nicht gilt [mm] u_i=v_i=w_i.....
[/mm]
Für die Richtung => in b) musst du nur noch zusätzlich begründen, dass im Fall einer totalen Ordung <= beliebige u,v immer vergleichbar sind, also entweder u<||v oder v<|| u gilt.
Auch dazu betrachtest du wieder das kleinste i mit [mm] u_i\ne v_i
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:16 So 06.11.2011 | | Autor: | erha06 |
Hallo donquijote,
> Dann betrachtest du die erste Stelle i für die nicht gilt
> [mm]u_i=v_i=w_i[/mm]
An dieser Stelle ist [mm]u_i
Das wäre in einem Lexikon z.B.
Haus
Katze
Maus
Aber damit habe ich ja nicht den Fall abgedeckt, dass sich u, v und w an einem unterschiedlichen "i" unterscheiden.
Beispielsweise:
Hausbau
Hausfrau
Katze
D. h. ich brauche nach wie vor eine Fallunterscheidung. Oder ergibt sich dieser Fall automatisch aus dem oben genannten?
----
Zur b)
Im Falle einer totalen Ordnung gilt dann entweder, dass u=v ist, oder, dass [mm]u_iv_i[/mm] für das kleinste i ist. Aber das ist ja keine Begründung. Kannst du mir dort noch auf die Sprünge helfen?
Danke.
erha06
|
|
|
| |
|
> Hallo donquijote,
>
> > Dann betrachtest du die erste Stelle i für die nicht gilt
> > [mm]u_i=v_i=w_i[/mm]
>
> An dieser Stelle ist [mm]u_i
> v<||w und u<||w.
In jedem Fall gilt hier [mm] u_i<=v_i<=w_i, [/mm] wobei an mindestens einer der beiden Stellen ein striktes < steht (da nicht alle drei gleich sind).
Daraus folgt aus der Transitivität der ursprünglichen Relation [mm] u_i
>
> Das wäre in einem Lexikon z.B.
> Haus
> Katze
> Maus
>
> Aber damit habe ich ja nicht den Fall abgedeckt, dass sich
> u, v und w an einem unterschiedlichen "i" unterscheiden.
>
> Beispielsweise:
> Hausbau
> Hausfrau
> Katze
>
> D. h. ich brauche nach wie vor eine Fallunterscheidung.
> Oder ergibt sich dieser Fall automatisch aus dem oben
> genannten?
>
> ----
>
> Zur b)
> Im Falle einer totalen Ordnung gilt dann entweder, dass
> u=v ist, oder, dass [mm]u_iv_i[/mm] für das kleinste
> i ist. Aber das ist ja keine Begründung. Kannst du mir
> dort noch auf die Sprünge helfen?
Und das bedeutet nach Definition, dass entweder u=v oder u<||v oder v<||u gelten muss, also u und v vergleichbar sind.
>
> Danke.
> erha06
>
>
|
|
|
|
