Aufgabenproblem: Mengen, Relationen und Funktionen

08.04.2006, 09:53

TheSentinel

Aufgabenproblem: Mengen, Relationen und Funktionen

Hallo allerseits,

ich sitz gerade an der Mathe-Klausurvorbereitung und hab ein paar Probleme.
Wir haben von unserem Dozenten Übungsaufgaben bekommen - allerdings ohne Rechenweg und Lösungen vielleicht könnte mit jemand bei der Lösung von ein paar Aufgaben, bei denen ich mir nicht so im Klaren bin wie sie funktionieren, behilflich sein. Vielen Dank schon mal.

Die erste Aufgabe lautet:

Sei $\begin{eqnarray*} M = \{ 1,2,3,4,5\} \end{eqnarray*}$ eine Menge.
a) Bestimmen Sie die Eigenschaften der Relation R1 über M, $\begin{eqnarray*} R1 = M\times M \end{eqnarray*}$ .

Frage dazu: Was bedeutet denn M X M (Ich hab noch mehr Aufgaben wo dann zum Beispiel A X A drin steht)? Wie sieht denn die Relation in extensionaler Schreibweise aus? Und welche Eigenschaften hat die dann?

b) Ergänzen Sie die Relation R2 über M, $\begin{eqnarray*} R2 = \{ (3,1),(5,2),(2,1),(1,4)\} \end{eqnarray*}$ so dass sie eine Ordnungsrelation bzw. eine Äquivalenzrelation ist.

Frage dazu: Was ist denn genau eine Ordnungsrelation bzw. eine Äquivalenzrelation und wie mach ich aus dem Gegebenen eine?

Das wärs mal fürs Erste...Vielleicht kann das mir mal eine(r) erklären - wär echt super. Vielen Dank schon mal....

Gruß
Martin

08.04.2006, 12:44

JochenX

Auf diesen Beitrag antworten »

zu 1)
AxB ist das kartesische Produkt zweier Mengen; dabei bedeutet das Paarbildung, das erste Element aus A, das zweite aus B.
[sind A,B algebraische Strukturen ist hier zumeist auch komponentenweise Verknüpfung zugegeben, man nennt das dann "direktes Produkt"]

MxM heißt dann also....?

Wie habt ihr denn Relationen über einer Menge M definiert? üblicherweise sind das TEILMENGEN von MxM, also sollte das auch in eurem Aufschrieb stehen.

2) was das genau ist, findest du in deinem Aufschrieb oder bei Wikipiedia
also nicht so faul, Definitionen selber nachschauen
die Definition mal posten, dann sehen wir weiter

08.04.2006, 13:59

TheSentinel

Auf diesen Beitrag antworten »

Hi LOED,

danke für die Info. Ja ich weiß...ich war ein bissl schnell. Sry. Mittlerweile habe ich auch noch selber ein bissl nachgedacht, Bücher durchgeschaut und gegoogelt.

Also MXM wären ja dann alle möglichen Kombinationen die ich bilden kann wenn ich M als Menge und nochmal die gleiche Menge M miteinander kombiniere.

Das mit den Teilmengen ist mir soweit klar. Also die Relation MxM wäre dann halt keine Teilmenge sondern die - ich nenns mal - Obermenge selbst.

Das mit den Äquivalenz- und Ordnungsrelationen hab ich ein bissl falsch ausgedrückt. Ich hab schon ne Definition was es ist, bzw. wann eine Relation eine der oben genannten ist.
Aber mein Problem ist eher, dass ich nicht so recht weiß, wie ich aus einer gegebenen Relation eine der beiden machen kann.
Gibt es da irgendein bestimmtes Verfahren, das einen das "relativ schnell" erweitern lässt?

Danke nochmal.

Gruß
Martin

08.04.2006, 14:12

JochenX

Auf diesen Beitrag antworten »

Zitat:

Das mit den Teilmengen ist mir soweit klar. Also die Relation MxM wäre dann halt keine Teilmenge sondern die - ich nenns mal - Obermenge selbst.

kein Problem, ist trotzdem ne Relation MxM ist ja auch (unechte) Teilmenge von MxM.
Bei dieser Relation steht dann wirklich JEDES Element mit JEDEM in Relation.

zu prüfen sind dann Reflexivität, Transitivität etc., da ist eigentlich alles sehr leicht.

Deine andere Frage:
was muss denn eine Äquivalenzrelation erfüllen?

Zitat:

Ich hab schon ne Definition was es ist, bzw. wann eine Relation eine der oben genannten ist.

dann sag mal an!

als Beispiel, wie du das "auffüllst" mal von mir; du suchst eine Teilmenge von MxM, die deine Menge enthält und die geforderten Eigenschaften erfüllt
Äquirels sind z.B. refelexiv, d.h. jedes Element muss in Relation mit sich selbst stehen, dafür muss NACH dem auffüllen einfach (i,i) für jedes i aus M drinstehen, also hier einfach die 5 fehlenden Paare reinschreiben

und schon ist der erste Schritt getan

08.04.2006, 15:15

TheSentinel

Auf diesen Beitrag antworten »

Vielen Dank für die schnell Antwort.

Zitat:

Original von LOED

Deine andere Frage:
was muss denn eine Äquivalenzrelation erfüllen?

Zitat:

Ich hab schon ne Definition was es ist, bzw. wann eine Relation eine der oben genannten ist.

dann sag mal an!

Definition: Eine Relation R ist genau dann eine Äquivalenzrelation (auf M) wenn sie reflexiv, symmetrisch und transitiv ist.

Zitat:

Original von LOED
als Beispiel, wie du das "auffüllst" mal von mir; du suchst eine Teilmenge von MxM, die deine Menge enthält und die geforderten Eigenschaften erfüllt
Äquirels sind z.B. refelexiv, d.h. jedes Element muss in Relation mit sich selbst stehen, dafür muss NACH dem auffüllen einfach (i,i) für jedes i aus M drinstehen, also hier einfach die 5 fehlenden Paare reinschreiben

und schon ist der erste Schritt getan

Also zu meiner Menge von oben:

M = {1,2,3,4,5}

R={(3,1),(5,2),(2,1),(1,4)}

wäre das dann noch (1,3)(2,5)(1,2)(4,1)(1,1)(2,2)(3,3)(4,4)(5,5)(5,1)(1,5) ????

Ich glaube mein Problem ist noch immer, dass ich noch net so ganz verstanden habe wie ich überprüfe ob eine Relation transitiv, reflexiv, symmetrisch, usw. ist.

Gruß Martin

09.04.2006, 19:06

TheSentinel

Auf diesen Beitrag antworten »

Aufgabe bitte überprüfen
Hallo nochmal,

ich hab nun ein bisschen weiter überlegt und gerechnet und hab nun mal versucht die Aufgabe von oben zu lösen:

Hier nochmal die Aufgabe:

Zitat:

Aufgabe

Sei $\begin{eqnarray*} M = \{1,2,3,4,5\} \end{eqnarray*}$ eine Menge.

a) Bestimmen Sie die Eigenschaften der Relation $\begin{eqnarray*} R_1 \end{eqnarray*}$ über $\begin{eqnarray*} M, R_1 = \{(1,1),(2,1),(2,2),(1,2)\} \end{eqnarray*}$ .

b) Bestimmen Sie die Eigenschaften der Relation $\begin{eqnarray*} R_2 \end{eqnarray*}$ über $\begin{eqnarray*} M, R_2 = \{(2,1),(1,3),(3,5)\} \end{eqnarray*}$ .

c) Ergänzen Sie die Relation $\begin{eqnarray*} R_3 \end{eqnarray*}$ über $\begin{eqnarray*} M, R_3 = M\times M \end{eqnarray*}$ .

d) Ergänzen Sie die Relation $\begin{eqnarray*} R_4 \end{eqnarray*}$ über $\begin{eqnarray*} M, R_4 = \{(3,1),(5,2),(2,1),(1,4)\} \end{eqnarray*}$ so dass sie eine Ordnungsrelation ist.

e) Ergänzen Sie $\begin{eqnarray*} R_4 \end{eqnarray*}$ so dass sie eine Äquivalenzrelation ist.

Hier ist nun meine Lösung:

a) $\begin{eqnarray*} R_1 \end{eqnarray*}$ ist transitiv, symmetrisch und antisymmetrisch.

b) $\begin{eqnarray*} R_2 \end{eqnarray*}$ ist asymmetrisch und irreflexiv.

c) $\begin{eqnarray*} R_3 \end{eqnarray*}$ wäre bei mir $\begin{eqnarray*} R_3 = \{(1,1),(1,2),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4), \end{eqnarray*}$
$\begin{eqnarray*} (2,5),(3,1),(3,2),(3,3,(3,4),(3,5),(4,1), \end{eqnarray*}$
$\begin{eqnarray*} (4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)\} \end{eqnarray*}$ .
Die Eigenschaften sind symmetrisch und transitiv und reflexiv.

d) Ergänzen zur Ordnungsrelation: $\begin{eqnarray*} \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(2,5),(1,2),(4,1)\} \end{eqnarray*}$

e) Ergänzen zur Äquivalenzrelation: $\begin{eqnarray*} \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(2,5),(1,2),(4,1)\} \end{eqnarray*}$

Es wäre nett wenn mal irgendwer die Aufgaben bzw. die Lösungen von mir überprüfen könnte. Danke schonmal....

Und dann noch ne allgemeine Frage: wenn eine Relation symmetrisch ist, ist sie dann automatisch antisymmetrisch?

Viele Grüße

Martin

09.04.2006, 19:38

JochenX

Auf diesen Beitrag antworten »

Hallo, hatte deinen gestrigen Beitrag gar nicht gesehen, sorry!

zunächst:
a) stimmt nicht; wieso ist das antisymmetrisch?
b) Asymmetrie (also nicht Symmetrie) ist kein sonderlich wichtiges Kriterium
stattdessen wäre Antisymmetrie hier passend
c) da fehlt (1,3), sonst okay

d) da müsstest du erst mal eure "Ordnungsrelation" definieren, da habe ich bei Wiki selbst nicht genau gefunden, was das ist

e) Du hast das reflexiv und symmetrisch ergänzt
Ist es denn schon tranisitiv?

09.04.2006, 20:02

TheSentinel

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
Hallo, hatte deinen gestrigen Beitrag gar nicht gesehen, sorry!

zunächst:
a) stimmt nicht; wieso ist das antisymmetrisch?
b) Asymmetrie (also nicht Symmetrie) ist kein sonderlich wichtiges Kriterium
stattdessen wäre Antisymmetrie hier passend
c) da fehlt (1,3), sonst okay

d) da müsstest du erst mal eure "Ordnungsrelation" definieren, da habe ich bei Wiki selbst nicht genau gefunden, was das ist

e) Du hast das reflexiv und symmetrisch ergänzt
Ist es denn schon tranisitiv?

Hmmm...kannst du mir mal erklären - in einfachen Worten - was denn symmetrisch, antisymmetrisch und transitiv ist? Reflexiv und irreflexiv ist mir wohl klar. Ich hab das glaub ich noch net so ganz verstanden wie ich das seh...

Definition von Ordnungsrelation: ist dann ORel wenn sie reflexiv, antisymmetrisch und transitiv ist.

zu e) es fehlt noch (5,1) und (1,5) damit es transitiv ist?

09.04.2006, 20:12

JochenX

Auf diesen Beitrag antworten »

Zitat:

e) Du hast das reflexiv und symmetrisch ergänzt
Ist es denn schon tranisitiv?

quatsch ist ja noch nicht mal symmetrisch Augenzwinkern

habe ich mich verguckt

symmetrisch heißt einfach: wenn du (a,b) drin hast, dann muss auch (b,a) drin liegen
<-- sollte klar sein!?

transitiv besagt einfach: wenn (a,b) drinliegt und (b,c), dann liegt auch (a,c) drin
stell dir die Relation als Pfeilr zwischen den Knoten vor: (a,b) heißt Pfeil von a nach b, (b,c) heißt Pfeil nach (b,c)
Transitiv bedeutet nun anschaulich: da du von a nach b und davon weiter nach c gehen kannst, muss das auch direkt verbunden sein

antisymmetrie ist das komplizierteste:
merke dir die Bedingung: aus (a,b) und (b,a) in R => a=b
anschaulich: zwei UNTERSCHIEDLICHE Elemente x,y können niemals beides gleichzeitig erfüllen, also (x,y) UND (y,x)
entweder nur eines, oder gar keines

09.04.2006, 20:24

TheSentinel

Auf diesen Beitrag antworten »

Zitat:

Original von LOED

symmetrisch heißt einfach: wenn du (a,b) drin hast, dann muss auch (b,a) drin liegen
<-- sollte klar sein!?

Jo also symmetrisch ist mir denke ich klar. Das muss dann auch nur für ein Element gelten - also es müssen nicht alle möglichen symmetrischen Kombinationen drin sein.

transitiv besagt einfach: wenn (a,b) drinliegt und (b,c), dann liegt auch (a,c) drin
stell dir die Relation als Pfeilr zwischen den Knoten vor: (a,b) heißt Pfeil von a nach b, (b,c) heißt Pfeil nach (b,c)
Transitiv bedeutet nun anschaulich: da du von a nach b und davon weiter nach c gehen kannst, muss das auch direkt verbunden sein

Transitiv ist mir auch klar, wenn (1,3) drin ist und (3,1) und dann noch (1,1) dann ist es transitiv - wenn das (1,1) fehlt dann nicht.

antisymmetrie ist das komplizierteste:
merke dir die Bedingung: aus (a,b) und (b,a) in R => a=b
anschaulich: zwei UNTERSCHIEDLICHE Elemente x,y können niemals beides gleichzeitig erfüllen, also (x,y) UND (y,x)
entweder nur eines, oder gar keines

Das antisymmetrisch macht mir echt noch die meisten Probleme. Könntest du mir da mal noch ein Zahlenbeispiel machen für eine Relation die Antisymmetrisch ist und eine dies nicht ist? Das wär super...

09.04.2006, 20:31

JochenX

Auf diesen Beitrag antworten »

Zitat:

symmetrisch heißt einfach: wenn du (a,b) drin hast, dann muss auch (b,a) drin liegen
<-- sollte klar sein!?

Jo also symmetrisch ist mir denke ich klar. Das muss dann auch nur für ein Element gelten - also es müssen nicht alle möglichen symmetrischen Kombinationen drin sein.

deinen Hinweis verstehe ich nicht, das muss einfach für alle Elemente gelten, die du in dr Relation findest
wenn z.B. in einer der obigen Relationen (1,3) und (3,1) drin sind, ist das für dieses Element okay.
Wenn beide nicht drin liegen auch.
wenn abe (3,1) drin ist, (1,3) nicht, dann ist es nicht mehr symmetrisch.

Zitat:

transitiv besagt einfach: wenn (a,b) drinliegt und (b,c), dann liegt auch (a,c) drin
stell dir die Relation als Pfeilr zwischen den Knoten vor: (a,b) heißt Pfeil von a nach b, (b,c) heißt Pfeil nach (b,c)
Transitiv bedeutet nun anschaulich: da du von a nach b und davon weiter nach c gehen kannst, muss das auch direkt verbunden sein

Transitiv ist mir auch klar, wenn (1,3) drin ist und (3,1) und dann noch (1,1) dann ist es transitiv - wenn das (1,1) fehlt dann nicht.

können natürlich auch 3 verschiedene Elemente sein
(1,3) liegt drin, (3,5), dann MUSS auch (1,5) drin liegen
dein Beispiel ist auch richtig

Antisymmetrie: wir nehmen deine Menge M von oben

S1 enthalte folgende Paare: {(2,3), (3,4), (2,2)}
schauen wirs uns an: es gibt tatsächlich Paar(e) von Elementen, für die (a,b) und (b,a) in S1 liegt; daraus muss a=b folgen
hier nur für a=b=2 der Fall
antisymmetrisch!

S2={(2,3), (3,4), (4,3)}
S2 enthält wieder Paar(e), für die (a,b) und (b,a) drinliegt; diesmal aber 3<>4!
nicht antisymmetrisch

S3={(1,1), (2,2), (3,4),(4,3)}
S3 ist auch nicht antisymmetrisch, denn wieder stört (3,4) und (4,3)
dass (1,1) und (2,2) das ganze erfüllen stört niemanden

S4={}
leere Relation, kein Paar a,b für das sowohl (a,b) als auch (b,a) in S2 liegen
also antisymmetrisch

S5={(1,2), (2,4), (4,5), (5,2), (3,3)}
selbst prüfen....

09.04.2006, 20:44

TheSentinel

Auf diesen Beitrag antworten »

Zitat:

Original von LOED

Antisymmetrie: wir nehmen deine Menge M von oben

S1 enthalte folgende Paare: {(2,3), (3,4), (2,2)}
schauen wirs uns an: es gibt tatsächlich Paar(e) von Elementen, für die (a,b) und (b,a) in S1 liegt; daraus muss a=b folgen
hier nur für a=b=2 der Fall
antisymmetrisch!
Warum das hier antisymm. ist versteh ich noch net so ganz. Ich hätte gesagt, es ists nicht.
Doch jetzt hab ichs glaub auch da...die Bedinung dass x,y in S und y,x in S ist, ist nicht erfüllt also ist die Gesamtaussage wahr und S ist antisymmetrisch.

S2={(2,3), (3,4), (4,3)}
S2 enthält wieder Paar(e), für die (a,b) und (b,a) drinliegt; diesmal aber 3<>4!
nicht antisymmetrisch

S3={(1,1), (2,2), (3,4),(4,3)}
S3 ist auch nicht antisymmetrisch, denn wieder stört (3,4) und (4,3)
dass (1,1) und (2,2) das ganze erfüllen stört niemanden

S4={}
leere Relation, kein Paar a,b für das sowohl (a,b) als auch (b,a) in S2 liegen
also antisymmetrisch

S5={(1,2), (2,4), (4,5), (5,2), (3,3)}
selbst prüfen....

S5 ist antisymmetrisch. Weil die Bedingung x,y ist in S und y,x ist in S nicht erfüllt wird. Damit wird die gesamte Aussage wahr.l

09.04.2006, 20:47

JochenX

Auf diesen Beitrag antworten »

warum sollte das erste NICHT antisymmetrisch sein?
fragen wir mal so smile

S5 ist antisymm., aber es gibt ein solches Paar trotzdem
a=3, b=3

aber dann MUSS eben a=b folgen und zum Glück tut es das hier smile

09.04.2006, 20:54

TheSentinel

Auf diesen Beitrag antworten »

Ja also wie oben geschrieben, hab ich das erste nun auch auf antisymmetrisch raus....

Ich werd nun mal noch ein paar Aufgaben machen. Ich hoffe wir bekommen mal morgen die Lösungen. Das ist halt bissl doof, dass wir für unsere Übungsaufgaben keine Lösungen haben zum das Gerechnete überprüfen.

Vielen vielen Dank mal für deine Hilfe!

smile

09.04.2006, 20:58

JochenX

Auf diesen Beitrag antworten »

jo, noch wegen deiner "Auffüllarbeit" oben

Reflexiv auffüllen, kein Problem
Symmetrisch an sich auch nicht, denke ich

für das Berechnen der Transitiven Hülle gabs so einen schönen Algorithmus, den habt ihr vermutlich besprochen, schau mal nach
Weiß grad nimmer wie der heißt verwirrt

Ansonsten: gern geschehen und viel Spaß damit noch

Neue Frage »

Antworten »

Aufgabenproblem: Mengen, Relationen und Funktionen

Verwandte Themen