Beweis für Äquivalenzrelation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:28 Sa 23.02.2013 | | Autor: | Felerian |
| Aufgabe | Es sei R eine binäre Relation über M und deltaM wie üblich die Diagonale über M.
Beweisen Sie: R ist Äquivalenzrelation genau dann, wenn deltaM Teilmenge von R ist und R°R^-1 Teilmenge von R ist. |
Meine Ideen:
Beweisen muss ich jetzt:
R ist Äquivalenzrelation (reflexiv, symmetrisch, transitiv) -> deltaM Teilmenge von R und R°R^-1 Teilmenge von R
und
deltaM Teilmenge von R und R°R^-1 Teilmenge von R -> R ist Äquivalenzrelation (reflexiv, symmetrisch, transitiv)
Die erste Richtung bekomm ich noch hin:
1. Da deltaM Teilmenge von R ist, gilt für alle x element M: (x,x) element deltaM und damit auch element R. Damit ist R reflexiv
2. Sei (x,z) e [mm] R^R^-1. [/mm] Dann existiert ein y element M so dass gilt: (x,y) e R und (y,z) e R^-1.
Da R symmetrisch ist (per Vorraussetzung) ist (y,x) e R und (y,z) e R und (z,y) e R.
Da R auch transitiv ist: Aus (x,y) e R und (y,z) e R folgt (x,z)e R
Also ist R°R^-1 Teilmenge von R und diese Richtung ist fertig
Jetzt kommt das Problem:
deltaM Teilmenge von R und R°R^-1 Teilmenge von R -> R ist Äquivalenzrelation (reflexiv, symmetrisch, transitiv)
Reflexivität krieg ich hin, das Problem hab ich mit den anderen beiden (symmetrisch, transitiv)
Ich komme nur bis hier:
Sei (x,z) e R°R^-1. Dann exisitert ein y e M, so dass gilt: (x,y) e R und (y,z)e R^-1.
Aus (x,y)e R folgt (y,x) e R^-1 und aus (y,z) e R^-1 folgt (z,y) e R
(durch die definition der inversen Relation.
Aus (z,y) e R und (y,x) e R^-1 folgt dann (z,x) e R°R^-1
Damit habe ich aber nur gezeigt das R°R^-1 symmetrisch ist, nicht komplett R.
Wie mache ich weiter?
Vielen Dank schonmal
PS: R°S ist das Relationenprodukt oder Hintereinanderausführung
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.matheboard.de/thread.php?threadid=515622
http://matheplanet.de/
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:49 Sa 23.02.2013 | | Autor: | Sax |
Hi,
> Beweisen muss ich jetzt:
>
> R ist Äquivalenzrelation (reflexiv, symmetrisch,
> transitiv) -> deltaM Teilmenge von R und R°R^-1 Teilmenge
> von R
>
> und
>
> deltaM Teilmenge von R und R°R^-1 Teilmenge von R -> R ist
> Äquivalenzrelation (reflexiv, symmetrisch, transitiv)
>
>
Stimmt, genau diese zwei Beweisrichtungen sind zu führen.
> Die erste Richtung bekomm ich noch hin:
>
> 1. Da deltaM Teilmenge von R ist, gilt für alle x element
> M: (x,x) element deltaM und damit auch element R. Damit ist
> R reflexiv
>
Das ist aber doch ein Teil des zweiten Beweises !
Im ersten Teil muss die Richtung umgekehrt sein :
zu zeigen ist : R reflexiv $ [mm] \Rightarrow \Delta [/mm] M [mm] \subseteq [/mm] R $
> 2. Sei (x,z) e [mm]R^R^-1.[/mm] Dann existiert ein y element M so
> dass gilt: (x,y) e R und (y,z) e R^-1.
Falls ihr die Reihenfolge von [mm] \circ [/mm] so definiert habt.
Häufig findet man $ R [mm] \circ R^{-1} [/mm] $ = {(a,b) | [mm] \exists [/mm] c [mm] \in [/mm] M : (a,c) [mm] \in R^{-1} [/mm] und (c,b) [mm] \in [/mm] R }
>
> Da R symmetrisch ist (per Vorraussetzung) ist (y,x) e R und
> (y,z) e R und (z,y) e R.
Die drei Aussagen sind zwar richtig, aber nicht alle folgen aus der Symmetrie von R, außerdem wird nur eine gebraucht. Specke den Beweis ab !
>
> Da R auch transitiv ist: Aus (x,y) e R und (y,z) e R folgt
> (x,z)e R
>
> Also ist R°R^-1 Teilmenge von R und diese Richtung ist
> fertig
>
>
> Jetzt kommt das Problem:
>
> deltaM Teilmenge von R und R°R^-1 Teilmenge von R -> R ist
> Äquivalenzrelation (reflexiv, symmetrisch, transitiv)
>
> Reflexivität krieg ich hin, das Problem hab ich mit den
> anderen beiden (symmetrisch, transitiv)
Reflexivität hast du ja oben schon gezeigt, die andere Richtung fehlt wie gesagt oben noch.
>
>
> Ich komme nur bis hier:
>
> Sei (x,z) e R°R^-1. Dann exisitert ein y e M, so dass
> gilt: (x,y) e R und (y,z)e R^-1.
> Aus (x,y)e R folgt (y,x) e R^-1 und aus (y,z) e R^-1 folgt
> (z,y) e R
> (durch die definition der inversen Relation.
>
> Aus (z,y) e R und (y,x) e R^-1 folgt dann (z,x) e R°R^-1
>
> Damit habe ich aber nur gezeigt das R°R^-1 symmetrisch
> ist, nicht komplett R.
>
> Wie mache ich weiter?
>
Indem du nicht von einem (x,z) [mm] \in [/mm] $ R [mm] \circ R^{-1} [/mm] $ ausgehst, sondern von einem (x,y) [mm] \in [/mm] R. Du musst zeigen, dass dann auch (y,x) [mm] \in [/mm] R gilt.
Das gelingt unter Zuhilfenahme von (x,x) [mm] \in [/mm] R und (y,y) [mm] \in [/mm] R, was wegen der Voraussetzung $ [mm] \Delta [/mm] M [mm] \subseteq [/mm] R $ benutzt werden kann.
Um Transitivität nachzuweisen kannst du dann die gerade bewiesene Symmetrie verwenden.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:58 Sa 23.02.2013 | | Autor: | Felerian |
EDIT: Ich hab noch nicht wirklich raus wie man direkt auf irgendwas antwortet, meine Lösung ist jetzt als weitere Frage zu dieser hier aufgeführt, das hier kann übersprungen werden
> Das ist aber doch ein Teil des zweiten Beweises !
> Im ersten Teil muss die Richtung umgekehrt sein :
> zu zeigen ist : R reflexiv [mm]\Rightarrow \Delta M \subseteq R[/mm]
Das hab ich wohl vertauscht, sollte dann so sein:
Da R reflexiv ist gilt für alle x e M: (x,x) e R. Das ist auch genau die Definition der Diagonalen, also ist deltaM Teilmenge von R
> Indem du nicht von einem (x,z) [mm]\in[/mm] [mm]R \circ R^{-1}[/mm]
> ausgehst, sondern von einem (x,y) [mm]\in[/mm] R. Du musst zeigen,
> dass dann auch (y,x) [mm]\in[/mm] R gilt.
> Das gelingt unter Zuhilfenahme von (x,x) [mm]\in[/mm] R und (y,y)
> [mm]\in[/mm] R, was wegen der Voraussetzung [mm]\Delta M \subseteq R[/mm]
> benutzt werden kann.
Das hab ich auch schon probiert, komme aber nicht weiter..
Sei (x,y) e R und zu zeigen ist (y,x) e R. Durch deltaM Teilmenge R sind (x,x) e R und (y,y) e R.
Ich muss ja irgendwie (y,x) e R rauskriegen, aber ich sehe keine möglichkeit x und y in ein Tupel zu bekommen..
Das ist mein Hauptproblem, Transitivität sollte ich dann wieder hinbekommen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:03 Sa 23.02.2013 | | Autor: | Felerian |
Ah, ich glaub ich hab´s:
Wenn ich annehme, dass (x,y) e R ist, und (x,x) e R und (y,y) e R, dann ist (y,x) e R^-1.
Aus (y,x) e R^-1 und (y,y e R) folgt dann (y,x) e R°R^-1, und da das ja Teilmenge von R ist, ist (y,x) auch Element von R.
Damit ist Symmetrie bewiesen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:14 Sa 23.02.2013 | | Autor: | Sax |
Hi,
> Sei (x,y) e R und zu zeigen ist (y,x) e R. Durch deltaM
> Teilmenge R sind (x,x) e R und (y,y) e R.
>
>
> Ich muss ja irgendwie (y,x) e R rauskriegen,
genau.
Das gelingt, indem du zeigst, dass (sogar) (y,x) [mm] \in [/mm] $ R [mm] \circ R^{-1} [/mm] $ gilt. Dann folgt die Behauptung aufgrund der vorausgesetzten Teilmengenbeziehung.
Der Nachweis sollte dir mit Hilfe von (x,y) [mm] \in [/mm] R (also (y,x) [mm] \in R^{-1}) [/mm] und (y,y) [mm] \in [/mm] R gelingen.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Sa 23.02.2013 | | Autor: | Felerian |
Ja, genau so hat´s auch geklappt, danke:)
Der Vollständigkeitshalber noch Transitivität:
Sei (x,y) e R und (y,z) e R. z.Z: (x,z) e R
Aufgrund der Symmetrie gilt: (z,y) e R, daraus folgt (y,z) e R^-1.
Und aus (x,y) e R und (y,z) e R^-1 folgt dann (x,z) e R°R^-1, woraus dann aufgrund der Vorraussetzung (x,z) e R folgt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Sa 23.02.2013 | | Autor: | Sax |
Schönen Feierabend !
|
|
|
|
