Äquivalenzrelation und partielle Ordnung

10.02.2011, 16:58

Mö

Äquivalenzrelation und partielle Ordnung

Meine Frage:
Also
ich habe eine Grundmenge M={a,b,c,d} gegeben
dann habe ich noch die Relation
R={(a,a),(c,c),(b,a),(b,c)}
die Aufgabe besteht jetzt darin die Relation so zu erweitern das jeweils eine Äquivalenzrelation, sowie eine partielle Ordnung rauskommt.

Ich hab das jetzt soweit mal gemacht und wollt eigentlich nur wissen ob ich die Eigenschaften soweit richtig verstanden habe...
also ob die von mir angegebene Lösung richtig ist

Meine Ideen:
Äquivalenzrelation(reflexiv, symmetrisch und transitiv)

damit die Relation reflexiv wird füge ich die Tupel (b,b) und (d,d) hinzu
für die Symmetrie das Tupel (a,b)
und für die Transitivität (a,c)

partielle Ordnung(reflexiv, antisymmetrisch und transitiv)

für die Reflexivität füge ich wieder (b,b) und (d,d) hinzu

Für die Antisymmetrie brauche ich kein Tupel hinzufügen, da die Relation schon antisymmetrisch ist...

für die Transitivität füge ich (c,d) und (b,d) hinzu da durch hinzufügen von (a,b) und (a,c) die Relation durch das erste Tupel nicht mehr antisymmetrisch wäre...

gruß Mö

10.02.2011, 23:14

saladin

Auf diesen Beitrag antworten »

RE: Äquivalenzrelation und partielle Ordnung
Du kannst es ganz einfach überprüfen ob du deine Äquivalenzrelation richtig erweitert hast, indem du es durch eine matrix veranschaulichst.

Du hast M={a,b,c,d}

$\begin{eqnarray*} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \end{eqnarray*}$

4x4 Matrix deswegen, weil M 4 Elemente hat.

(die erste Zeile entspricht a,.........., die vierte Zeile entspricht d

die erste Spalte entspricht a,........, die letzte Spalte entspricht d)

(a,a),(b,b),(c,c),(d,d) sind enthalten wie du richtig erkannt hast, also:

$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

dann sagtest du sind (b,a),(b,c) enthalten... also:

$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

Wegen der Symmetrie... müssen jetzt auch folgende Elemente enthalten sein...:

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

dass sind genau (a,b) und (c,b)

Und wegen der Transitivität müssen folgende Elemente enthalten sein:

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

das sind genau (a,c) und (c,a)

Äquivalenzrelationen können also nicht so aussehen:

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

oder so:

$\begin{eqnarray*} \begin{pmatrix} 0& 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

sie sehen immer wie folgt aus:
$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 0& 0 & 0 & 0 \\1 & 1 & 0& 0 & 0 & 0 \\ 0 & 0 & 1& 0 & 0 & 0 \\ 0 & 0 & 0& 1 & 0 & 0 \\0 & 0 & 0& 0 & 1 & 0 \\0 & 0 & 0& 0 & 0 & 1 \\ \end{pmatrix} \end{eqnarray*}$

oder

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1& 0 & 0 & 0 \\1 & 1 & 1& 0 & 0 & 0 \\ 1 & 1 & 1& 0 & 0 & 0 \\ 0 & 0 & 0& 1 & 0 & 0 \\0 & 0 & 0& 0 & 1 & 0 \\0 & 0 & 0& 0 & 0 & 1 \\ \end{pmatrix} \end{eqnarray*}$

oder
$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1& 1 & 1 & 0 \\1 & 1 & 1& 1 & 1 & 0 \\ 1 & 1 & 1& 1 & 1 & 0 \\ 1 & 1 & 1& 1 & 1 & 0 \\1 & 1 & 1& 1 & 1 & 0 \\0 & 0 & 0& 0 & 0 & 1 \\ \end{pmatrix} \end{eqnarray*}$

oder

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1& 1 & 1 & 1 \\1 & 1 & 1& 1 & 1 & 1 \\ 1 & 1 & 1& 1 & 1 & 1 \\ 1 & 1 & 1& 1 & 1 & 1 \\1 & 1 & 1& 1 & 1 & 1 \\1 & 1 & 1& 1 & 1 & 1 \\ \end{pmatrix} \end{eqnarray*}$

Ich hoffe ich konnte es irgendwie anschaulich und verständlich erklären.

11.02.2011, 10:05

Mystic

Auf diesen Beitrag antworten »

RE: Äquivalenzrelation und partielle Ordnung
oder

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1& 1 & 0 & 0 \\1 & 1 & 1& 1 & 0 & 0 \\ 1 & 1 & 1& 1 & 0 & 0 \\ 1 & 1 & 1& 1 & 0 & 0 \\0 & 0 & 0& 0 & 1 & 1 \\0 & 0 & 0& 0 & 1 & 1 \\ \end{pmatrix} \end{eqnarray*}$

Man soll ja schließlich aus deinen Beispielen nicht den falschen Schluss ziehen, dass es immer nur eine Äquivalenzklasse gibt mit mehr als einem Element... Big Laugh

Übrigens glaube ich nicht, dass dieser Weg über Matrizen für eine manuelle Rechnung der beste ist, da er bei größeren Grundmengen sehr viel Schreibarbeit mit sich bringt... Meiner Meinung nach der beste Weg geht so, dass man die bijektive Zuordnung von Aquivalentzrelationen auf einer Menge M und den Partitionen von M ausnützt und versucht, die Partition P zu bestimmen, welche der von R erzeugten Äquivalenzrelation entspricht...

In unserem Beispiel geht das so (wobei [x] die Äquivalenzklasse von x in der Partition P bezeichnet)

$\begin{eqnarray*} (b,a) \in R \Rightarrow [b]=[a] \end{eqnarray*}$
$\begin{eqnarray*} (b,c) \in R \Rightarrow [b]=[c] \end{eqnarray*}$

Die "feinste" Partition P, welche diese Bedingungen erfüllt, ist offenbar

$\begin{eqnarray*} P=\{\{a,b,c\},\{d\}\} \end{eqnarray*}$

und man braucht jetzt nur mehr die Relation $\begin{eqnarray*} \bar R \end{eqnarray*}$ zu bilden, welche definiert ist durch

$\begin{eqnarray*} x \bar R y : \Leftrightarrow [x]=[y] \text{ in } P \end{eqnarray*}$

und diese ist dann offenbar auch die von R erzeugte Äquivalenzrelation...

11.02.2011, 15:50

Mö

Auf diesen Beitrag antworten »

ok an dieser stelle möchte ich mich erstmal für beide Beiträge bedanken Freude

haben mir sehr beim Verständnis geholfen

um das nochmal zusammen zu fassen
es müssen also alle in der Relation vorhandenen, oder hinzugefügten, Tupel die Eigenschaften der Symmetrie oder Transitivität erfüllen

wie schaut das jetzt eigentlich mit der partiellen Ordnung in dem Beispiel aus
stimmt es denn das die gegebene Relation von Anfang an schon antisymmetrisch ist und ich kein weiteres Tupel hinzufügen muss
und wie gehe ich dort mit der Transitivität um
denn eigentlich müsst ich doch noch (a,b) und (a,c) hinzufügen. Jedoch wäre die Relation dann nicht mehr antisymmetrisch...

11.02.2011, 17:52

Mystic

Auf diesen Beitrag antworten »

Was die Antisymmetrie betrifft ist, so ist in Hinblick auf eine Erweiterung zu einer partiellen Ordnung

1) richtig, dass R dazu bereits selbst antisymetrisch sein muss
2) falsch, dass jede Erweiterung von R auch antisymmetrisch bleibt

Nimm z.B. die Relation R={(a,b),(b,c),(c,a)}, welche antisymmetrisch ist, aber sobald du z.B. (a,c) dazu gibst, um die Transitivität zu erreichen, ist sie es nicht mehr... Du musst also zuerst versuchen, durch eine "minimale" Erweiterung von R die Reflexität und Transitivität zu erreichen und wenn diese Erweiterung dann noch immer antisymmetrisch ist, dann bist du am Ziel, ansonsten ist die Aufgabe unlösbar...

Was übrigens deine Relation R={(a,a),(c,c),(b,a),(b,c)} betrifft, so ist diese bereits transitiv, warum in aller Welt willst du also Elemente zur Erreichung der Transitivität hinzufügen??? Oder kannst du mir ein Gegenbeispiel zur Transitivität nennen? verwirrt

11.02.2011, 19:35

Mö

Auf diesen Beitrag antworten »

ok das mit der Antisymmetrie ist klar soweit
jetzt hab ich aber noch zu der Transitivität eine frage
du meintest meine Gegebene Relation sei schon transitiv
nach Definition müsste doch gelten: für alle a,b,c Element A gilt (a,b) Element R und (b,c) Element R => (a,c) auch Element R ist.
Nun wäre meine Relation trotzdem Transitiv auch wenn nur die Tupel (a,b) und (a,c) enthalten wären? Also ohne (b,c)?

11.02.2011, 20:32

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Mö
ok das mit der Antisymmetrie ist klar soweit
jetzt hab ich aber noch zu der Transitivität eine frage
du meintest meine Gegebene Relation sei schon transitiv
nach Definition müsste doch gelten: für alle a,b,c Element A gilt (a,b) Element R und (b,c) Element R => (a,c) auch Element R ist.
Nun wäre meine Relation trotzdem Transitiv auch wenn nur die Tupel (a,b) und (a,c) enthalten wären? Also ohne (b,c)?

Ich schreib die Definition der Transivität noch einmal mit anderen Variablennamen hin, weil deine Probleme möglcherweise daher kommen, dass diese gleiche Namen haben wie die Elemente von A:

$\begin{eqnarray*} \forall x,y,z \in A: (x,y) \in R \land (y,z) \in R \Rightarrow (x,z) \in R \end{eqnarray*}$

Die Verneinung davon ist

$\begin{eqnarray*} \exists x,y,z \in A: (x,y) \in R \land (y,z) \in R \land (x,z) \not \in R\quad (*) \end{eqnarray*}$

Wenn du sagst, R sei nicht transitiv, musst du ein Gegenbeispiel nennen können, d.h., Elemente $\begin{eqnarray*} x,y,z \in \{a,b,c,d\} \end{eqnarray*}$ , welche (*) erfüllen... Noch einmal daher die Frage: Kannst du das? verwirrt

11.02.2011, 21:10

Mö

Auf diesen Beitrag antworten »

hm... also ein Gegenbeispiel kann ich jetzt nicht finden

ich hoffe folgende Folgerung, für R={(a,a),(c,c),(b,a),(b,c)}l, ist korrekt

aus (b,a) und (a,a) folgt (b,a) und
aus (b,c) und (c,c) folgt (b,c)

ich wüsste sonst nicht aus welchen Teilen der Gegebenen Relation sich die Transitivität zeigen lassen würde

(sry das ich mich grad nen bissel blöd anstelle Hammer

)

11.02.2011, 21:35

Mystic

Auf diesen Beitrag antworten »

Noch einmal, wenn du an der Transitivität zweifelst, solltest du versuchen Elemente $\begin{eqnarray*} x,y,z \in \{a,b,c,d\} \end{eqnarray*}$ zu finden welche obige Beziehung (*) erfüllen... Deine zwei Beispiele oben zeigen nur, dass die Wahl x=b,y=a,z=a bzw. auch x=b,y=c,z=c kein Gegenbeispiel liefert... Tja, und da gibt es noch zwei weitere Fälle, nämlich x=y=z=a und x=y=z=c, welche aber ebenfalls kein Gegenbeispiel zur Transtivität liefern... Dies lässt aber nur einen Schluss zu: R ist transitiv!

Mein Rat daher: Lass endlich die Transitivität, welche eh erfüllt ist, und wende dich der Reflexivität zu, die noch nicht gilt!!!

11.02.2011, 22:33

Mö

Auf diesen Beitrag antworten »

naja um die Relation reflexiv zu machen
müsste ich die Tupel (b,b) und (d,d) hinzufügen

12.02.2011, 09:19

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Mö
naja um die Relation reflexiv zu machen
müsste ich die Tupel (b,b) und (d,d) hinzufügen

Genau! Und das war's dann auch schon... Freude

Ich hoffe, du siehst wenigstens im Nachhinein, wo du gedanklich auf Abwege geraten bist, um diesen Fehler dann in Zukunft zu vermeiden...

12.02.2011, 10:32

Mö

Auf diesen Beitrag antworten »

hm... ok dann bedank ich mich für deine hilfe ^^
hat mir sehr beim Verständnis geholfen
ich werde das jetzt einfach noch selber ein bisschen an anderen Beispielen üben
damit sich das alles ein bisschen festigt smile

also nochmal großes Danke Wink

Neue Frage »

Antworten »

Äquivalenzrelation und partielle Ordnung

Verwandte Themen