Äquivalenz-/Ordnungsrelation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:57 Mo 17.11.2014 | | Autor: | steinole |
| Aufgabe 1 | Sei R eine reflexive Relation auf einer Menge M. Zeigen Sie:
R ist eine Äquivalenzrelation auf M <=> Für alle a, b, c [mm] \in [/mm] M gilt: a [mm] \sim [/mm] c [mm] \wedge [/mm] b [mm] \sim [/mm] c [mm] \rightarrow [/mm] a [mm] \sim [/mm] b |
| Aufgabe 2 | Nach dem Ende der Hinrunde in einer Basketball-Meisterschaft soll auf der Menge der Teams
die folgende Relation definiert werden: x [mm] \sim [/mm] y genau dann, wenn x höchstens so viele Siege
hat wie y und im Fall, dass x und y gleich viele Siege haben, x nicht gegen y gewonnen hat.
Kann man sicher sein, damit eine Ordnungsrelation zu bekommen? Begründen Sie dies. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich würde mich über Korrekturen und Tipps zum Lösen der Aufgaben freuen.
Hier meine bisherige Idee zu der ersten Aufgabe:
Damit eine Äquivalenzrelation gilt, muss für a, b, c [mm] \in [/mm] M gelten:
1. Reflexivität: a [mm] \sim [/mm] a
2. Symmetrie: a [mm] \sim [/mm] b [mm] \rightarrow [/mm] b [mm] \sim [/mm] a
3. Transivität: a [mm] \sim [/mm] b [mm] \wedge [/mm] b [mm] \sim [/mm] c [mm] \rightarrow [/mm] a [mm] \sim [/mm] c
Mit dieser Voraussetzung will ich nun beweisen, dass auch
"Für alle a, b, c [mm] \in [/mm] M gilt: a [mm] \sim [/mm] c [mm] \wedge [/mm] b [mm] \sim [/mm] c [mm] \rightarrow [/mm] a [mm] \sim [/mm] b" gelte.
Nun stell ich mir die Frage, ob ein einfaches einsetzen bzw. testen für einen Beweis ausreicht? (Mit beispielsweise der Menge M = {1, 2, 3} und R = { (1,1), (2,2), (3,3) })
Alternativ habe ich folgende Überlegung angestellt:
Wenn 3. gilt, dann gibt es auf jeden Fall die Elemente (a, b), (b, c) und (a, c) und wegen 2. auch (b, a), (c, b) und (c, a). Des Weiteren gibt es (a, a), (b, b) und (c, c) wegen 1. Da diese Elemente alle in R vorhanden sind setzt man einfach ein bzw. schaut in die Behauptung und sieht, dass "Für alle a, b, c [mm] \in [/mm] M gilt: aRc [mm] \wedge [/mm] bRc [mm] \rightarrow [/mm] aRb" wahr ist. Ausreichend?
Abschließende Frage zu der Aufgabe: Reicht es aus, wenn man A [mm] \rightarrow [/mm] B bewiesen hat, oder muss man auch B [mm] \rightarrow [/mm] A beweisen?
Nun meine Ideen zu der zweiten Aufgabe:
Ich habe erst einmal versucht, den Text als Formel darzustellen:
x [mm] \sim [/mm] y [mm] \gdw [/mm] x [mm] \le [/mm] y [mm] \vee [/mm] ( x = y [mm] \rightarrow [/mm] a < b )
Dabei gelten x bzw. y für die Anzahl der gesamten Siege und a bzw. b für den Sieg im direkten Aufeinandertreffen. ( (x, a), (y, b) ? )
Da aber in der Aufgabe lediglich eine Begründung gefordert ist, würde ich sagen:
Ja, es ist eine Ordnungsrelation. Wenn x weniger Siege hat als y, dann ist klar, dass y höher in der Tabelle steht als x. Sobald sie beide gleich viele Siege haben, kommt es darauf an, wer das direkte Duell gewonnen hat. In diesem Fall wird es immer y sein, weil x in Ordnungsrelation zu y steht.
Fragen: Ich bin bei der Recherche über den Begriff "lexikografische Ordnung" gestoßen, trifft dies zu? Und wie soll man das mit den Eigenschaften der Reflexivität, der Symmetrie und der Transitivität beweisen?
Ich bedanke mich jetzt schon einmal für jegliche Hilfe.
Mit freundlichen Grüßen
keinstein
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:32 Di 18.11.2014 | | Autor: | Teufel |
Hi!
Machen wir erst mal die 1. Ganz wichtig: Du kannst niemals eine allgemeingültige Aussage mit Beispielen zeigen! Das wäre in etwa, als wenn du folgendes "beweisen" würdest: Alle Primzahlen sind gerade. Beweis: Wenn ich die 2 nehme, dann stimmt das. qed
Natürlich ist der Beweis falsch, aber genau so hast du auch versucht vorzugehen. Was du so beweisen kannst, sind Existenzaussagen. Beispielsweise: Es existiert eine Primzahl, die größer als 20 ist. Beweis: 23. Hier wurde nur ein Beispiel gegeben, aber mehr wird auch nicht verlangt. Es soll nur eine Primzahl >20 geben und du hast eine geliefert. Ende.
Wie dem auch sei, zurück zu deiner Aufgabe. Vorab: Ja, du musst beide Richtungen zeigen, wie es auch in der Aufgabe verlangt wird. Die Rückrichtung ist ja nicht automatisch richtig, auch wenn das schon ganz praktisch wäre. ;) Beispiel (schon wieder Primzahlen...):
Sei $p>2$. Dann gilt $p$ ist Primzahl [mm] \Rightarrow [/mm] $p$ ist ungerade, klar. Es gilt aber nicht die Umkehrung, also $p$ ist ungerade [mm] \Rightarrow [/mm] $p$ ist Primzahl. Beweis durch Gegenbeispiel (hier kannst du das auch wieder machen, da es um die Existenz eines Gegenbeispiels geht): 15.
Machen wir mal die eine Richtung, also $R$ ist ÄR auf $M$ [mm] $\Rightarrow \forall a,b,c\inM: a\sim [/mm] c, [mm] b\sim [/mm] c [mm] \Rightarrow a\sim [/mm] b$
Beweis: Seien [mm] $a,b,c\in [/mm] M$ mit [mm] $a\sim [/mm] c$ und [mm] $b\sim [/mm] c$. Zu zeigen: [mm] $a\sim [/mm] b$.
Wegen [mm] $b\sim [/mm] c$ und weil [mm] \sim [/mm] eine ÄR ist, gilt nach Eigenschaft 2 (Symmetrie) auch [mm] $c\sim [/mm] b$ Damit folgt aus [mm] $a\sim [/mm] c$ und [mm] $b\sim [/mm] c$ eben [mm] $a\sim [/mm] c$ und [mm] $c\sim [/mm] b$. Wegen Eigenschaft 3 einer ÄR (Transitivität) folgt aus [mm] $a\sim [/mm] c$ und [mm] $c\sim [/mm] b$ aber schon [mm] $a\sim [/mm] b$, was zu zeigen war.
Nun zur anderen Richtung. Du hast folgendes gegeben: [mm] $\forall a,b,c\inM: a\sim [/mm] c, [mm] b\sim [/mm] c [mm] \Rightarrow a\sim [/mm] b$ und ferner weißt du, dass [mm] $a\sim [/mm] a$ gilt [mm] (\sim [/mm] ist reflexiv). Du musst jetzt die Symmetrie und Transitivität zeigen, also dass aus den zwei gegebenen Sachen [mm] $a\sim [/mm] b [mm] \Rightarrow b\sim [/mm] a$ und [mm] $a\sim [/mm] c, [mm] c\sim b\Rightarrow a\sim [/mm] b$ folgt.
Zur nächsten Aufgabe: Wie habt ihr denn Ordnungsrelation definiert?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:26 Di 18.11.2014 | | Autor: | steinole |
Das ist schon um einiges einleuchtender als vorher, danke dafür.
Nachvollziehen ist nun nicht das Problem, aber beim Rückbeweis finde ich den ersten Schritt nicht.
Meine Gedanken nochmal dazu, wenn ich es richtig verstanden habe:
Gegeben:
$ [mm] \forall a,b,c\inM: a\sim [/mm] c, [mm] b\sim [/mm] c [mm] \Rightarrow a\sim [/mm] b $ und Reflexivität ( Was bringt sie mir in dem Fall? )
Gesucht:
2. Symmetrie $ [mm] a\sim [/mm] b [mm] \Rightarrow b\sim [/mm] a $
und
3. Transitivität $ [mm] a\sim [/mm] c, [mm] c\sim b\Rightarrow a\sim [/mm] b $
Beweis:
2. Symmetrie:
Seien $ a,b [mm] \in [/mm] M $ mit $ [mm] a\sim [/mm] b $
Zu zeigen: $ [mm] b\sim [/mm] a $
Hier scheitert es bei mir:
$ [mm] \forall [/mm] a, b, c [mm] \inM [/mm] : [mm] a\sim [/mm] c $, $ [mm] b\sim [/mm] c [mm] \Rightarrow a\sim [/mm] b $ und $ [mm] a\sim [/mm] a $
Ein kleiner Tipp wäre hilfreich.
3. Transitivität:
Wenn man die Symmetrie bewiesen hätte, dann könnte man die Transitivität zeigen, indem man sagt:
Seien $ a,b,c [mm] \in [/mm] M $ mit $ [mm] a\sim [/mm] c $ und $ [mm] c\sim [/mm] b $
Zu zeigen: $ [mm] a\sim [/mm] b $
Weil $ [mm] c\sim [/mm] b $ gilt, muss auch $ [mm] b\sim [/mm] c $ gelten und man erhält $ [mm] a\sim [/mm] c $ und $ [mm] b\sim [/mm] c $, woraus sich laut Voraussetzung $ [mm] a\sim [/mm] b $ ergibt.
Bei der Definition der Ordnungsrelation heißt es nur:
R heißt eine OR, wenn R reflexiv, antisymmetrisch und transitiv ist.
Danke im Voraus.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:53 Di 18.11.2014 | | Autor: | MacMath |
> Das ist schon um einiges einleuchtender als vorher, danke
> dafür.
>
> Nachvollziehen ist nun nicht das Problem, aber beim
> Rückbeweis finde ich den ersten Schritt nicht.
>
> Meine Gedanken nochmal dazu, wenn ich es richtig verstanden
> habe:
>
> Gegeben:
>
> [mm]\forall a,b,c\inM: a\sim c, b\sim c \Rightarrow a\sim b[/mm] und
> Reflexivität ( Was bringt sie mir in dem Fall? )
>
>
> Gesucht:
>
> 2. Symmetrie [mm]a\sim b \Rightarrow b\sim a[/mm]
> und
> 3. Transitivität [mm]a\sim c, c\sim b\Rightarrow a\sim b[/mm]
>
>
> Beweis:
>
> 2. Symmetrie:
> Seien [mm]a,b \in M[/mm] mit [mm]a\sim b[/mm]
>
> Zu zeigen: [mm]b\sim a[/mm]
>
> Hier scheitert es bei mir:
>
> [mm]\forall a, b, c \inM : a\sim c [/mm], [mm]b\sim c \Rightarrow a\sim b[/mm]
> und [mm]a\sim a[/mm]
>
> Ein kleiner Tipp wäre hilfreich.
Im Prinzip erben wir die Symmetrie vom "und".
Wir haben [mm] $a\sim [/mm] b$ und [mm] $b\sim [/mm] b$, also [mm] $a\sim [/mm] b$
Sieht recht sinnfrei aus, oder? ;)
Aber wir haben doch auch:
[mm] $b\sim [/mm] b$ und [mm] $a\sim [/mm] b$, also auch $b [mm] \sim [/mm] a$ -much better!
>
>
> 3. Transitivität:
> Wenn man die Symmetrie bewiesen hätte, dann könnte man
> die Transitivität zeigen, indem man sagt:
>
> Seien [mm]a,b,c \in M[/mm] mit [mm]a\sim c[/mm] und [mm]c\sim b[/mm]
>
> Zu zeigen: [mm]a\sim b[/mm]
>
> Weil [mm]c\sim b[/mm] gilt, muss auch [mm]b\sim c[/mm] gelten und man erhält
> [mm]a\sim c[/mm] und [mm]b\sim c [/mm], woraus sich laut Voraussetzung [mm]a\sim b[/mm]
> ergibt.
>
>
>
> Bei der Definition der Ordnungsrelation heißt es nur:
>
> R heißt eine OR, wenn R reflexiv, antisymmetrisch und
> transitiv ist.
Joa, jetzt musst du entweder zeigen, dass diese drei erfüllt sind, oder eine Möglichkeit finden, zum Beispiel (*g*) die Transitivität zu verletzen.
Viele Grüße
|
|
|
|
