Ordnungsrelation R+ aus R

19.11.2013, 15:35

Josi91

Ordnungsrelation R+ aus R

Meine Frage:
Hey Leute, ich habe eine Frage zur einer Aufgabe aus meinem Studium.
Folgendes:
Es sei $\begin{eqnarray*} A = {a, b, c, d, e, f} \end{eqnarray*}$ und $\begin{eqnarray*} R \end{eqnarray*}$ sei die folgende Relation auf $\begin{eqnarray*} A: \end{eqnarray*}$
$\begin{eqnarray*} R = {(a,b), (b,c), (c,d), (b,e), (e,f)}. \end{eqnarray*}$

Aufgabe: Durch hinzufügen von möglichst wenigen Paaren soll erreicht werden, dass aus $\begin{eqnarray*} R \end{eqnarray*}$ eine Ordnungsrelation $\begin{eqnarray*} R^+ \end{eqnarray*}$ auf $\begin{eqnarray*} A \end{eqnarray*}$ entsteht. Welche Paare muss man hinzu fügen?

Meine Frage ist nun, was dieses $\begin{eqnarray*} R^+ \end{eqnarray*}$ ist?

Meine Ideen:
Also für eine Ordnungsrelation muss ja Reflexivität, Antisymmetrie und Transitivität gegeben sein.

Ich würde jetzt einfach die fehlenden Paare hinzu fügen, damit die drei Dinge gegeben sind. Aber ist das dann eine Ordnungsrelation $\begin{eqnarray*} R^+ \end{eqnarray*}$ ? dieses $\begin{eqnarray*} R^+ \end{eqnarray*}$ verwirrt mich so. Vor allem soll ich ja nur möglichst wenige Paare hinzu fügen. Allerdings sind das doch sehr viele wie ich finde.

Kann mir das jemand erklären, was damit wohl gemeint ist?
Vielen Dank!

19.11.2013, 17:04

Leopold

Auf diesen Beitrag antworten »

Schreibe, wenn $\begin{eqnarray*} x,y \end{eqnarray*}$ verschieden sind, statt $\begin{eqnarray*} (x,y) \end{eqnarray*}$ mehr suggestiv $\begin{eqnarray*} x<y \end{eqnarray*}$ und lies das als " $\begin{eqnarray*} x \end{eqnarray*}$ kommt vor $\begin{eqnarray*} y \end{eqnarray*}$ ". Dann überlege, was das Bild mit deiner Aufgabe zu tun hat.

[attach]32145[/attach]

$\begin{eqnarray*} R^+ \end{eqnarray*}$ ist einfach der Name der minimalen Relation, die $\begin{eqnarray*} R \end{eqnarray*}$ zu einer Ordnungsrelation macht, also der Name für die Lösung deiner Aufgabe.

19.11.2013, 17:37

Josi91

Auf diesen Beitrag antworten »

Okay, würde es dann nicht reichen, dass ich folgenden Paare hinzu füge:
$\begin{eqnarray*} (a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (a,c), (a,e), (b,d), (b,f) \end{eqnarray*}$

Das sollte doch eigentlich reichen, oder?
Demnach wäre
$\begin{eqnarray*} R^+ = {(a,b), (a,c), (a,e), (b,c), (b,d), (b,e), (b,f), (c,d), (e,f), (a,a), (b,b), (c,c), (d,d), (e,e), (f,f)} \end{eqnarray*}$

19.11.2013, 17:40

Leopold

Auf diesen Beitrag antworten »

Du bist auf dem richtigen Weg. Aber was ist mit $\begin{eqnarray*} (a,d) \end{eqnarray*}$ ? Und mit ...

19.11.2013, 17:51

Josi91

Auf diesen Beitrag antworten »

Okay das verstehe ich nicht smile

Also (a,d) und (a,f) brauche ich doch nicht. Ich habe das so "gelernt", dass wenn ich einen Punkt in zwei wegen erreiche, muss ich ihn auch in einem erreichen, damit die Transitivität gegeben ist. Also weil ich von (a,b) und (b,c) kann, brauche ich auch (a,c). Aber (a,d) würde ja bedeuten weil ich (a,b), (b,c), und (c,d) habe brauche ich dieses (a,d). Das wäre ja aber 3 "Wege".

Oder ist das wegen der Antisymmetrie? Weil die verstehe ich nicht so ganz :/

19.11.2013, 18:01

Leopold

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} a<b \end{eqnarray*}$ und $\begin{eqnarray*} b<c \end{eqnarray*}$ . Wegen der Transitivität sollte daher auch $\begin{eqnarray*} a<c \end{eqnarray*}$ gelten. Du mußt daher das Paar $\begin{eqnarray*} (a,c) \end{eqnarray*}$ mit dazunehmen, damit das gilt. So weit sind wir uns einig.
Von jetzt ab ist das Paar dabei, also $\begin{eqnarray*} a<c \end{eqnarray*}$ . Da von Anfang an $\begin{eqnarray*} c<d \end{eqnarray*}$ gilt, sollte wegen der Transitivität auch $\begin{eqnarray*} a<d \end{eqnarray*}$ gelten. Also mußt du auch $\begin{eqnarray*} (a,d) \end{eqnarray*}$ dazunehmen.
Vielleicht fällt es dir einfacher, den umgekehrten Gedanken zu verstehen. Nimm an, du hättest mit deinem vorigen Beitrag recht und das dort von dir angegebene $\begin{eqnarray*} R^+ \end{eqnarray*}$ wäre die Lösung. Es enthält $\begin{eqnarray*} (a,c) \end{eqnarray*}$ und $\begin{eqnarray*} (c,d) \end{eqnarray*}$ . Dann müßte es, weil ja $\begin{eqnarray*} R^+ \end{eqnarray*}$ eine Ordnungsrelation ist, auch $\begin{eqnarray*} (a,d) \end{eqnarray*}$ enthalten. Tut es aber nicht. Also haben wir deine Behauptung, die Lösung zu haben, ad absurdum geführt.

19.11.2013, 18:37

Josi91

Auf diesen Beitrag antworten »

Arrg, stimmt, du hast ja Recht. Hammer

Jetzt sehe ich es auch smile

Also fehlt bei meiner da oben nur noch das $\begin{eqnarray*} (a,d) \end{eqnarray*}$ und das $\begin{eqnarray*} (a,f) \end{eqnarray*}$ . Dann sollte es das aber sein smile

Dann noch eine andere Frage:
In der nächsten Aufgabe soll ich das gleiche mit einer Äquivalenzrelation machen.
$\begin{eqnarray*} A={a, b, c, d, e} \end{eqnarray*}$
$\begin{eqnarray*} R={(a,b), (b,c), (c,d), (b,e)} \end{eqnarray*}$ .
Durch hinzufügen von möglichst wenigen Paaren soll erreicht werden, dass aus R eine Äquivalenzrelation S entsteht ("kleinste Äquivalenzrelation, die R umfasst").

Da habe ich folgendes raus:
$\begin{eqnarray*} S={(a,b), (a,c), (a,d), (a,e), (b,a), (b,c), (b,d), (b,e), (c,a), (c,b), (c,d), (c,e), (d,a), (d,b), (d,c), (d,e), (e,a), (e,b), (e,c), (e,d), (a,a), (b,b), (c,c), (d,d), (e,e)} \end{eqnarray*}$

Ggf. das sei richtig lautet der nächste Schritt:
Wie kann man S kurz und knapp angeben, ohne alle Paare von S aufzuzählen?
Da habe ich die Idee, da ja jede Äquivalenzrelation durch eine Partition erzeugt wird, kann mann die Partition dazu angeben? Da weiß ich allerdings gar nicht wie das geht unglücklich

19.11.2013, 23:26

Leopold

Auf diesen Beitrag antworten »

Schreiben wir auch hier suggestiver $\begin{eqnarray*} x \sim y \end{eqnarray*}$ statt $\begin{eqnarray*} (x,y) \in R \end{eqnarray*}$ . Wie immer, wenn Transitivität gilt oder gelten soll, kann man Ketten bilden. Man schreibt also statt $\begin{eqnarray*} x \sim y \end{eqnarray*}$ und $\begin{eqnarray*} y \sim z \end{eqnarray*}$ kurz $\begin{eqnarray*} x \sim y \sim z \end{eqnarray*}$ , und wegen der gewünschten Transitivität ist dann $\begin{eqnarray*} x \sim z \end{eqnarray*}$ gleich ablesbar. Die ersten drei Paare von $\begin{eqnarray*} R \end{eqnarray*}$ liefern so

$\begin{eqnarray*} a \sim b \sim c \sim d \end{eqnarray*}$

Und damit müssen diese vier Elemente in der zu erstellenden Äquivalenzrelation $\begin{eqnarray*} S \end{eqnarray*}$ untereinander äquivalent sein. Jetzt soll aber auch noch $\begin{eqnarray*} b \sim e \end{eqnarray*}$ gelten. Da $\begin{eqnarray*} b \end{eqnarray*}$ schon zu den andern drei Elementen äquivalent ist und es jetzt auch noch zu $\begin{eqnarray*} e \end{eqnarray*}$ sein soll, sind alle fünf Elemente untereinander äquivalent:

$\begin{eqnarray*} a \sim b \sim c \sim d \sim e \end{eqnarray*}$

Es gibt also nur eine Äquivalenzklasse, die sämtliche Elemente von $\begin{eqnarray*} A \end{eqnarray*}$ enthält. Oder anders gesagt: Jedes Element $\begin{eqnarray*} x \end{eqnarray*}$ ist zu jedem anderen $\begin{eqnarray*} y \end{eqnarray*}$ (das auch $\begin{eqnarray*} x \end{eqnarray*}$ selbst sein darf) äquivalent. Jedes Paar $\begin{eqnarray*} (x,y) \end{eqnarray*}$ mit $\begin{eqnarray*} x,y \in A \end{eqnarray*}$ gehört also der Relation $\begin{eqnarray*} S \end{eqnarray*}$ an. Oder ohne jeden Schnörkel:

$\begin{eqnarray*} S = A^2 = A \times A \end{eqnarray*}$

Und genau das hast du bei deiner Aufzählung ja getan: alle möglichen Paare gebildet, ohne daß es dir aufgefallen wäre.

20.11.2013, 11:48

Josi91

Auf diesen Beitrag antworten »

Super, das hat mir wirklich geholfen Prost

Vielen Dank für deine Hilfe. Den Rest werde ich wohl so hinbekommen smile

20.11.2013, 15:43

Josi91

Auf diesen Beitrag antworten »

Hi, ich habe noch mal eine Frage zur nächsten Aufgabe Big Laugh

Ich soll wieder eine Äquivalenzrelation erstellen. Gegeben ist folgendes:

$\begin{eqnarray*} A = {a, b, c, d, e, f}<br /> R = {(a,b), (b,d) (e,f)} \end{eqnarray*}$

Reicht es wenn ich folgendes hinzufüge?

$\begin{eqnarray*} a \sim d, b \sim a, d \sim b, b \sim d, f \sim e, a \sim a, b \sim b, c \sim c, d \sim d, e \sim e, f \sim f \end{eqnarray*}$
so dass man dann
$\begin{eqnarray*} S = a \sim b, a \sim d, b \sim a, b \sim d, d \sim b, b \sim d, e \sim f, f \sim e, a \sim a, b \sim b, c \sim c, d \sim d, e \sim e, f \sim f \end{eqnarray*}$
bekommt?
Bei mir würde das dann so aussehen:
[attach]32152[/attach]

Also ist das zulässig, dass a, b, d in keiner Relation zu c und e, f und e, f in keiner Relation zu c stehen?

20.11.2013, 17:50

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Josi91
$\begin{eqnarray*} S = a \sim b, a \sim d, b \sim a, \color{red} b \sim d, \color{black} d \sim b, \color{red} b \sim d, \color{black} e \sim f, f \sim e, a \sim a, b \sim b, c \sim c, d \sim d, e \sim e, f \sim f \ \ \color{red} \text{fehlt:} \ d \sim a \end{eqnarray*}$
bekommt?
Bei mir würde das dann so aussehen:
[attach]32152[/attach]

Im wesentlichen richtig (siehe Korrekturen).

Zitat:

Original von Josi91
Also ist das zulässig, dass a, b, d in keiner Relation zu c und e, f und e, f in keiner Relation zu c stehen?

Das ist zulässig und macht sogar das Wesentliche einer Äquivalenzrelation aus. Während in der vorigen Aufgabe die Äquivalenzrelation $\begin{eqnarray*} S = A^2 \end{eqnarray*}$ alle Paare enthielt und es dort somit nur eine Äquivalenzklasse gab, es sich also um die triviale Äquivalenzrelation handelte, ist es hier ein bißchen interessanter: Es gibt drei Äquivalenzklassen mit drei bzw. einem bzw. zwei Elementen. Deswegen enthält $\begin{eqnarray*} S \end{eqnarray*}$ auch $\begin{eqnarray*} 3^2 + 1^2 + 2^2 = 14 \end{eqnarray*}$ Paare.

20.11.2013, 20:31

Josi91

Auf diesen Beitrag antworten »

Uh, solche Dusseligkeitsfehler immer. Klar, dass nicht 2 mal $\begin{eqnarray*} b \sim d \end{eqnarray*}$ gemeint war und das $\begin{eqnarray*} d \sim a \end{eqnarray*}$ fehlt leuchtet mir natürlich ein. Aber danke für die Korrektur.
Wichtig war mir vor allem ob das so korrekt ist, also ob man das so lassen darf. Aber das hast du mir ja super beantwortet. Danke dafür smile

Neue Frage »

Antworten »

Ordnungsrelation R+ aus R

Verwandte Themen