Relationen & Ordnungen BEWEIS < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe 19. (Äquivalenzrelationen & Halbordnungen)
Sei M eine Menge. Es sei [mm]R[/mm] eine Äquivalenzrelation auf [mm]M[/mm] und [mm] \le [/mm] sei eine Halbordnungsrelation auf M. Definiere die folgende Relation [mm] \le_R [/mm] auf der Quotientenmenge [mm]M/R : \left[ a \right] \le_R \left[ b \right][/mm] genau dann, wenn es [mm]a' \in \left[ a \right][/mm] und [mm]b' \in \left[ b \right][/mm] gibt mit [mm]a' \le b'[/mm]. Untersuchen Sie, ob [mm] \le_R [/mm] reflexiv, antisymmetrisch bzw. transitiv ist. (D.h.: entweder Sie beweisen die entsprechende Eigenschaft oder Sie widerlegen sie durch Angabe eines geeigneten Beispiels.) Ist mithin durch [mm] \le_R [/mm] eine Halbordnungsrelation auf [mm]M/R[/mm] gegeben? |
Also ich glaube die Reflexivität wie folgt nachweisen zu können:
[mm]\forall x \in M : (x,x) \in \le \gdw x \le x [/mm] (Reflexivität HOR)
[mm]\Rightarrow \forall x \in \left[ x \right] : x \le x[/mm]
[mm]\Rightarrow \forall \left[ x \right] \in M/R : \left[ x \right] \le_R \left[ x \right][/mm]
[mm]\Rightarrow x [/mm] ist also reflexiv!
Ich weiß auch, dass ich für den Nachweis der Antisymmetrie ausgehend von der Voraussetzung, dass [mm]R[/mm] eine Äquivalenzrelation und [mm] \le [/mm] eine Halbordnungsrelation ist zeigen müsste: [mm] \le_R [/mm] ist entweder antisymmetrisch oder nicht, aber wie mache das?? Ich habe beide elementweisen Voraussetzungen:
1. Die Symmetrie von [mm]R[/mm] :
[mm]\forall x,y \in M : xRy \Rightarrow yRx[/mm]
2. Die Antisymmetrie von [mm] \le [/mm] :
[mm]\forall x,y \in M : x \le y \wedge y \le x \Rightarrow x = y[/mm]
3. Wie ich vermute muss ich nun zeigen, dass die folgende Behauptung (Antisymmetrie von [mm] \le_R [/mm] ) nun wahr oder falsch ist:
[mm]( \exists a \in \left[ a \right] \wedge \exists b \in \left[ b \right] : a \le b )[/mm]
[mm]\wedge ( \exists b' \in \left[ b \right] \wedge \exists a' \in \left[ a \right] : b' \le a' )[/mm]
[mm]\Rightarrow \left[ a \right] = \left[ b \right][/mm]
Meine Überlegung ist: wenn ich die Falschheit nachweisen muss, dann muss ich zeigen, dass die Prämisse der Behauptung unter den gegebenen Voraussetzungen immer erfüllt ist, die Konklusion aber nicht. Möchte ich aber die Richtigkeit nachweisen, so müsste ich zeigen, dass die Prämisse immer falsch oder die Prämisse und die Konklusion immer richtig oder nur diese beiden Fälle möglich sind!
Ich vermute, dass die Behauptung falsch ist, weil es theoretisch ja ein [mm] a \in \left[ a \right] [/mm] und ein [mm] b \in \left[ b \right][/mm] geben könnte, für die [mm] a \le b [/mm] gilt und ein (völlig anderes) [mm] b' \in \left[ b \right] [/mm] sowie [mm] a' \in \left[ a \right] [/mm] für die die umgekehrte Behauptung gilt, so dass [mm] \left[ a \right] [/mm] und [mm] \left[ b \right] [/mm] nicht unbedingt gleich sein müssen.
Aber wie bringe ich das ganze jetzt in Beweisform ... wie gelange ich von der Voraussetzung zur Behauptung bzw. einer Widerlegung davon?? Ich habe stundenlang darüber gegrübelt, aber mir will kein griffiger Mathematischer Beweis einfallen!! Ist das normal oder bin ich vielleicht einfach unbegabt?
Welche Methodik empfiehlt sich in solchen Fällen? Jeder sagt einem: Das kann man nicht lernen aber es muss doch eine Methodik geben oder irgendwelche Ansatzpunkte die man in solchen Fällen einsetzen kann. Es kann doch nicht sein, dass man den Eindruck hat, vor Null zu stehen!
Also wer mir diesbezüglich helfen kann, dem sei im Voraus gedankt. Vielleicht hat auch noch jemand einen Literaturtipp parat für Übungsaufgaben dieser Art (am besten Tonnenweise) um in die Denkstrukturen reinzukommen. Vielen Dank!
Ich habe diese Frage auf keiner anderen Internetseite gestellt!
|
|
| |
|
Hallo,
Dein Nachweis der Reflexivit"at stimmt.
Zur Untersuchung auf Antisymmetrie: Um sie zu widerlegen, musst Du zeigen, dass
midenstens einmal (nicht notw.: immer) die Praemisse erfuellt ist, aber die
Folgerung nicht.
Deine Vermutung ist richtig, und Du kannst zB einfach eine Menge mit 4 Elementen angeben und einer Halbordungsstrukt. , die isomorph zu der des Potenzmengenverbandes
einer zweielem. Menge mit Inklusion ist:
d
/ [mm] \
[/mm]
b c
\ /
a
(Ich hoffe, man sieht es !). Dann nimm R mit den Klassen [mm] \{c,b\} [/mm] und [mm] \{a,d\}, [/mm] das
sollte Gegenbeispiel genug sein (es gibt ein kleineres mit drei Elementen und
linearer Ordnung !).
Methodik: Wenn Du zeigen willst, dass etwas im allg. nicht gilt: Konstruiere ein
gegenbeispiel. Die Idee hattest Du ja schon resp. die Vermutung, wie es aussehen muss.
Viele Gruesse,
Mathias
|
|
|
|
