Äquivalenzrelation beweisen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wir nennen eine Relation R [mm] \subseteq [/mm] A x A zirkulär, falls gilt:
[mm] \forall [/mm] a,b,c [mm] \in [/mm] A : aRb [mm] \wedge [/mm] bRc => cRa
Beweisen Sie: R ist reflexiv und zirkulär genau dann, wenn R Äquivalenzrelation ist. |
Hallo,
bei der Reflexivität habe ich folgendes Problem: Ich habe 3 Variablen [mm] \in [/mm] A , wie soll ich da die Reflexivität beweisen. Wenn es nur zwei wären, wäre es kein Problem. Ist auch die Frage, ob ich unbedingt alle 3 Variablen (a,b,c) brauche.
Stehe hier also auf dem Schlauch. Wäre für jeden Ansatz dankbar.
Weitere Frage: Wie kann ich mir dieses "zirkulär" vorstellen anhand der vorgegebenen Relation ? Ist das so ähnlich wie die Transitivität ? Denn mal bildlich vorgestellt: " von a gehe ich nach b , von b nach c und von c nach a " sozusagen sowas wie ein "abgeschlossenes System" ?
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:23 So 06.04.2014 | | Autor: | tobit09 |
Hallo pc_doctor!
> Wir nennen eine Relation R [mm]\subseteq[/mm] A x A zirkulär, falls
> gilt:
> [mm]\forall[/mm] a,b,c [mm]\in[/mm] A : aRb [mm]\wedge[/mm] bRc => cRa
>
> Beweisen Sie: R ist reflexiv und zirkulär genau dann, wenn
> R Äquivalenzrelation ist.
> bei der Reflexivität habe ich folgendes Problem: Ich habe
> 3 Variablen [mm]\in[/mm] A , wie soll ich da die Reflexivität
> beweisen.
Bei welcher der beiden Richtungen bist du gerade?
Die Reflexivität ist bei beiden Richtungen doch schon vorausgesetzt.
> Stehe hier also auf dem Schlauch. Wäre für jeden Ansatz
> dankbar.
Fangen wir mal mit der Rück-Richtung an.
Sei also $R$ eine Äquivalenzrelation.
Zu zeigen ist, dass $R$ reflexiv und zirkulär ist.
Reflexiv ist $R$ natürlich nach Definition einer Äquivalenzrelation.
Zu zeigen ist also noch, dass $R$ zirkulär ist.
Seien also [mm] $a,b,c\in [/mm] A$ mit $aRb$ und $bRc$.
Zu zeigen ist $cRa$.
Was kannst du aus $aRb$ und $bRc$ mittels der Eigenschaften, die $R$ als Äquivalenzrelation besitzt, schlussfolgern?
> Weitere Frage: Wie kann ich mir dieses "zirkulär"
> vorstellen anhand der vorgegebenen Relation ? Ist das so
> ähnlich wie die Transitivität ?
Ja, nur dass die Konklusion $cRa$ anstelle von $aRc$ lautet.
> Denn mal bildlich
> vorgestellt: " von a gehe ich nach b , von b nach c und von
> c nach a " sozusagen sowas wie ein "abgeschlossenes System"
> ?
Wenn man sich $aRb$ als
"man kann von $a$ nach $b$ gelangen"
vorstellt, so sagt die Zirkularität:
"Wann immer man von einem Punkt [mm] $a\in [/mm] A$ über einen Punkt [mm] $b\in [/mm] A$ zu einem Punkt [mm] $c\in [/mm] A$ gelangen kann, kann man von $c$ zurück zu $a$ gelangen."
Mit
"man kann von $a$ über $b$ zu $c$ gelangen"
meine ich dabei
"man kann von $a$ zu $b$ gelangen und man kann von $b$ zu $c$ gelangen".
Ob diese Vorstellung weiterhilft, sei dahingestellt...
Viele Grüße
Tobias
|
|
|
| |
|
> Fangen wir mal mit der Rück-Richtung an.
>
> Sei also [mm]R[/mm] eine Äquivalenzrelation.
> Zu zeigen ist, dass [mm]R[/mm] reflexiv und zirkulär ist.
>
> Reflexiv ist [mm]R[/mm] natürlich nach Definition einer
> Äquivalenzrelation.
>
> Zu zeigen ist also noch, dass [mm]R[/mm] zirkulär ist.
>
> Seien also [mm]a,b,c\in A[/mm] mit [mm]aRb[/mm] und [mm]bRc[/mm].
> Zu zeigen ist [mm]cRa[/mm].
>
> Was kannst du aus [mm]aRb[/mm] und [mm]bRc[/mm] mittels der Eigenschaften,
> die [mm]R[/mm] als Äquivalenzrelation besitzt, schlussfolgern?
Ich kann schlussfolgern : die Symmetrieeigenschaft und die Transitivität.
aRb [mm] \wedge [/mm] bRc => bRa [mm] \wedge [/mm] cRb
aRb [mm] \wedge [/mm] bRc => aRc (transitiv)
Habe ich das richtig verstanden, dass man einfach nur bewesen muss, dass es eine Äq.rel. ist , also die drei bzw. zwei Eigenschaften beweisen muss ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:45 So 06.04.2014 | | Autor: | tobit09 |
> > Fangen wir mal mit der Rück-Richtung an.
> >
> > Sei also [mm]R[/mm] eine Äquivalenzrelation.
> > Zu zeigen ist, dass [mm]R[/mm] reflexiv und zirkulär ist.
> >
> > Reflexiv ist [mm]R[/mm] natürlich nach Definition einer
> > Äquivalenzrelation.
> >
> > Zu zeigen ist also noch, dass [mm]R[/mm] zirkulär ist.
> >
> > Seien also [mm]a,b,c\in A[/mm] mit [mm]aRb[/mm] und [mm]bRc[/mm].
> > Zu zeigen ist [mm]cRa[/mm].
> >
> > Was kannst du aus [mm]aRb[/mm] und [mm]bRc[/mm] mittels der Eigenschaften,
> > die [mm]R[/mm] als Äquivalenzrelation besitzt, schlussfolgern?
>
> Ich kann schlussfolgern : die Symmetrieeigenschaft und die
> Transitivität.
>
> aRb [mm]\wedge[/mm] bRc => bRa [mm]\wedge[/mm] cRb
>
> aRb [mm]\wedge[/mm] bRc => aRc (transitiv)
Das sind korrekte Schlussfolgerungen.
Zeigen wollen wir ja $cRa$.
Du hast in deiner letzten Zeile schon $aRc$ gefolgert.
Mit welcher Eigenschaft, die $R$ als Äquivalenzrelation besitzt, folgt nun $cRa$?
> Habe ich das richtig verstanden, dass man einfach nur
> bewesen muss, dass es eine Äq.rel. ist , also die drei
> bzw. zwei Eigenschaften beweisen muss ?
Nein. Zu zeigen sind zwei Richtungen
1. Hin-Richtung
2. Rück-Richtung.
Wir haben auf meinen Vorschlag hin mit 2. angefangen.
2. besagt:
WENN $R$ eine Äquivalenzrelation ist, ist $R$ reflexiv und zirkulär.
1. besagt:
WENN $R$ reflexiv und zirkulär ist, ist $R$ eine Äquivalenzrelation.
Zum Nachweis von 1.:
Sei also $R$ als reflexiv und zirkulär vorausgesetzt.
Zeigen musst du:
( i) $R$ ist reflexiv )
ii) $R$ ist symmetrisch
iii) $R$ ist transitiv.
|
|
|
| |
|
> Das sind korrekte Schlussfolgerungen.
>
> Zeigen wollen wir ja [mm]cRa[/mm].
> Du hast in deiner letzten Zeile schon [mm]aRc[/mm] gefolgert.
> Mit welcher Eigenschaft, die [mm]R[/mm] als Äquivalenzrelation
> besitzt, folgt nun [mm]cRa[/mm]?
Mit der Symmetrieeigenschaft der Äquivalenzrelation.
>
> Zum Nachweis von 1.:
>
> Sei also [mm]R[/mm] als reflexiv und zirkulär vorausgesetzt.
> Zeigen musst du:
> ( i) [mm]R[/mm] ist reflexiv )
> ii) [mm]R[/mm] ist symmetrisch
> iii) [mm]R[/mm] ist transitiv.
Also muss ich zeigen
i ) aRa , durch die Reflexivität von R ist das doch schon bewiesen , wenn wir diese voraussetzen ?
ii) aRb [mm] \wedge [/mm] bRc => bRa [mm] \edge [/mm] cRb
iii) aRb [mm] \wedge [/mm] bRc => aRc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:18 So 06.04.2014 | | Autor: | tobit09 |
> > Das sind korrekte Schlussfolgerungen.
> >
> > Zeigen wollen wir ja [mm]cRa[/mm].
> > Du hast in deiner letzten Zeile schon [mm]aRc[/mm] gefolgert.
> > Mit welcher Eigenschaft, die [mm]R[/mm] als Äquivalenzrelation
> > besitzt, folgt nun [mm]cRa[/mm]?
> Mit der Symmetrieeigenschaft der Äquivalenzrelation.
![[ok]](/images/smileys/ok.gif "[ok]")
> > Zum Nachweis von 1.:
> >
> > Sei also [mm]R[/mm] als reflexiv und zirkulär vorausgesetzt.
> > Zeigen musst du:
> > ( i) [mm]R[/mm] ist reflexiv )
> > ii) [mm]R[/mm] ist symmetrisch
> > iii) [mm]R[/mm] ist transitiv.
>
> Also muss ich zeigen
>
> i ) aRa ,
für alle [mm] $a\in [/mm] A$
> durch die Reflexivität von R ist das doch
> schon bewiesen , wenn wir diese voraussetzen ?
> ii) aRb [mm]\wedge[/mm] bRc => bRa [mm]\wedge[/mm] cRb
Habt ihr Symmetrie so komisch definiert?
Üblicherweise definiert man:
Eine Relation $R$ auf $A$ heißt symmetrisch, wenn für alle [mm] $a,b\in [/mm] A$ gilt:
[mm] $aRb\Rightarrow [/mm] bRa$.
> iii) aRb [mm]\wedge[/mm] bRc => aRc
Ja, das ist für alle [mm] $a,b,c\in [/mm] A$ zu zeigen.
Zeige zunächst ii). Zeige dann iii) mittels Zirkularität und ii).
Zum Nachweis von ii):
Seien [mm] $a,b\in [/mm] A$ mit $aRb$.
Zu zeigen ist $bRa$.
Gemäß Reflexivität gilt $bRb$.
Wende nun die Zirkularität auf $a$, $b$ und $b$ an.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:22 So 06.04.2014 | | Autor: | pc_doctor |
Alles klar, vielen vielen Dank für deine aufgebrachte Mühe. Habs endlich kapiert, dankeschön.
|
|
|
| |
|
Hallo nochmal , habe noch eineFrage, die mir eingefallen ist
>
>
> Zeige zunächst ii). Zeige dann iii) mittels Zirkularität
> und ii).
ALso die Symmetrieeigenschaft.
Wieso ist es falsch , wenn ich aRb [mm] \wedge [/mm] bRc habe und dann die Symmetrie so zeige : bRa [mm] \wedge [/mm] cRb , damit habe ich die zweite Eigenschaft doch gezeigt , oder ?
Und bei der Reflexivität hatte ich gesagt aRa , das ist aber nur für a [mm] \in [/mm] A , was ist mit b und c ? Muss ich dann seperat noch mal bRb und cRc schreiben ?
> Gemäß Reflexivität gilt [mm]bRb[/mm].
> Wende nun die Zirkularität auf [mm]a[/mm], [mm]b[/mm] und [mm]b[/mm] an.
Das verstehe ich leider nicht , wie meinst du das mit auf "a" und dann "b" und "c" , muss ich das 3 mal machen ?
Also speziell bei der Symmetrie würde ich das hier machen:
aRb => bRa
bRc => cRb damit habe ich die Symmetrie doch beiwesen oder ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:41 Mo 07.04.2014 | | Autor: | tobit09 |
> > Zeige zunächst ii). Zeige dann iii) mittels Zirkularität
> > und ii).
> ALso die Symmetrieeigenschaft.
> Wieso ist es falsch , wenn ich aRb [mm]\wedge[/mm] bRc habe und
> dann die Symmetrie so zeige : bRa [mm]\wedge[/mm] cRb , damit habe
> ich die zweite Eigenschaft doch gezeigt , oder ?
In der Tat ist die Eigenschaft
(*) [mm] $\forall a,b,c\in A\colon (aRb\wedge bRc\Rightarrow bRa\wedge [/mm] cRb)$
äquivalent zur Symmetrie, die durch
[mm] $\forall a,b\in A\colon (aRb\Rightarrow [/mm] bRa)$
definiert ist.
Du kannst die Symmetrie also durch (*) nachweisen, wenn du dir zusätzlich überlegst, dass aus (*) tatsächlich die Symmetrie folgt.
Aber warum so kompliziert? Die Symmetrie ist doch eine deutlich übersichtlichere Eigenschaft als Eigenschaft (*).
> Und bei der Reflexivität hatte ich gesagt aRa , das ist
> aber nur für a [mm]\in[/mm] A , was ist mit b und c ? Muss ich dann
> seperat noch mal bRb und cRc schreiben ?
Die Reflexivität ist definiert durch
[mm] $\forall a\in A\colon [/mm] aRa$.
Nicht mehr und nicht weniger.
Sie impliziert aber natürlich die Aussagen
[mm] $\forall b\in A\colon [/mm] bRb$
[mm] $\forall c\in A\colon [/mm] cRc$
[mm] $\forall d\in A\colon [/mm] dRd$
usw.
> > Gemäß Reflexivität gilt [mm]bRb[/mm].
> > Wende nun die Zirkularität auf [mm]a[/mm], [mm]b[/mm] und [mm]b[/mm] an.
>
> Das verstehe ich leider nicht , wie meinst du das mit auf
> "a" und dann "b" und "c" , muss ich das 3 mal machen ?
Nein. Ich meinte übrigens wirklich $a$, $b$ und $b$, nicht etwa $a$, $b$ und $c$.
Wir wollen die Symmetrie von $R$ aus der Reflexivität und Zirkularität von $R$ folgern.
Dazu habe wir beliebig vorgegebene [mm] $a,b\in [/mm] A$ mit $aRb$ betrachtet.
Zeigen müssen wir $bRa$.
(Ein [mm] $c\in [/mm] A$ haben wir nicht vorgegeben.)
Die Zirkularität besagt (mit anderen Variablen geschrieben, um Namenskollisionen mit unseren $a$ und $b$ zu vermeiden):
[mm] $\forall x,y,z\in A\colon (xRy\wedge yRz\Rightarrow [/mm] zRx)$.
Wende nun diese Eigenschaft auf $x=a$, $y=b$ und $z=b$ an.
> Also speziell bei der Symmetrie würde ich das hier
> machen:
>
> aRb => bRa
Warum gilt diese Implikation? Genau sie ist ja gerade zu beweisen.
Dazu benötigst du die Anwendung der Zirkularität auf $a$, $b$ und $b$.
> bRc => cRb damit habe ich die Symmetrie doch beiwesen oder
> ?
Leider nein.
|
|
|
|
