aus Menge Relationen finden < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei M eine Menge mit Betrag von M = 3
Es gibt ___ reflexive Relationen in sich.
Es gibt ___ symmetrische Relationen von M in sich.
Es gibt ___ reflexive und symmetrische Relationen von M in sich.
Setzen sie die passenden zahl ein! |
Jetzt ist ja jede Teilmenge des kartesische Produkt aus [mm] A\timesA [/mm] eine Relation. [mm] 3\times3 [/mm] = 9 --> [mm] 2^{9} [/mm] = 512 --> es gibt 512 Relationen.
Nur wie komme ich jetzt auf die einzelnen Eigenschaften der Relation? Zum Beispiel muss in einer reflexiven Relation das Zahlenpaar (a,a),(b,b),(c,c) sein?! Woher weiß ich in welchen Relationen das der Fall ist?
PS: Für die Berechnung der Eigenschaften, habe ich mir die Menge, deren Betrag = 3 ist, als Menge M = (a,b,c) gedacht! (Ist das zulässig?)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:50 Mo 13.07.2009 | | Autor: | statler |
Hi1
> Sei M eine Menge mit Betrag von M = 3
> Es gibt ___ reflexive Relationen in sich.
> Es gibt ___ symmetrische Relationen von M in sich.
> Es gibt ___ reflexive und symmetrische Relationen von M in
> sich.
> Setzen sie die passenden zahl ein!
> Nur wie komme ich jetzt auf die einzelnen Eigenschaften der
> Relation? Zum Beispiel muss in einer reflexiven Relation
> das Zahlenpaar (a,a),(b,b),(c,c) sein?! Woher weiß ich in
> welchen Relationen das der Fall ist?
>
>
> PS: Für die Berechnung der Eigenschaften, habe ich mir die
> Menge, deren Betrag = 3 ist, als Menge M = (a,b,c) gedacht!
> (Ist das zulässig?)
Mein Vorschlag: Du zeichnest dir M [mm] \times [/mm] M als Quadrat hin. Die Relationen sind Teilmengen, woran erkennst du jetzt die reflexiven Relationen? Sie enthalten die Diagonale, aber die anderen Elemente sind beliebig. Wie viele solche Teilmengen gibt es?
Und dann einen ähnlichen Versuch mit symmetrisch....
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Also ich konnte mir nichts anderes unter deinem Tip vorstellen, als die Zeichnung, die ich unten angfertigt habe, aber ich befürchte, dass sie nicht ganz richtig ist :-(
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:41 Di 14.07.2009 | | Autor: | statler |
Guten Morgen!
Ich hatte mir das so vorgestellt, daß du die Paare aus M [mm] \times [/mm] M wie eine Matrix aufschreibst, also
[mm] \pmat{ (a,a) & (a,b) & (a,c) \\ & \cdots & \\ (c,a) & \cdots & (c,c) }
[/mm]
Eine reflexive Relation ist dann eine Teilmenge, die die Diagonale von links oben nach rechts unten enthalten muß. Es bleiben noch 6 andere Paare, aus denen du beliebig wählen kannst. Dafür gibt es [mm] 2^6 [/mm] Möglichkeiten, die zu verschiedenen reflexiven Relationen führen.
Überleg dir mal selbst, was du für eine symmetrische Relation frei wählen kannst und wie viele Möglichkeiten es dafür gibt.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
$ [mm] \pmat{ (a,a) & (a,b) & (a,c) \\ (b,a) & (b,b) & (b,c) \\ (c,a) & (c,b) & (c,c) } [/mm] $
Jetzt habe ich 6 Elemente (a,a), (a,b), (a,c), (b,b), (b,c) und (c,c), bei denen ich prüfe ob sie in der Relation sind. Die anderen Werte beleiben außen vor, da die sich aufgrund der Symmetrie "selbst" verändern. Somit habe ich wieder [mm] 2^{6} [/mm] Möglichkeiten und somit 64 Relationen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:02 Di 14.07.2009 | | Autor: | statler |
> [mm]\pmat{ (a,a) & (a,b) & (a,c) \\ (b,a) & (b,b) & (b,c) \\ (c,a) & (c,b) & (c,c) }[/mm]
>
> Jetzt habe ich 6 Elemente (a,a), (a,b), (a,c), (b,b), (b,c)
> und (c,c), bei denen ich prüfe ob sie in der Relation
> sind. Die anderen Werte beleiben außen vor, da die sich
> aufgrund der Symmetrie "selbst" verändern. Somit habe ich
> wieder [mm]2^{6}[/mm] Möglichkeiten und somit 64 Relationen.
.... 64 symmetrische Relationen. Jetzt bleibt noch der letzte Fall: reflexiv & symmetrisch. Aber das ist jetzt so klar, daß du keine Hilfe mehr brauchst  .
Ciao
Dieter
|
|
|
| |
|
Mm, also so klar ist mir das nicht. Wenn ich mir das Paar (a,b) anschaue, dann muss doch für die Transitivität folgendes zeigen: (a,b) E R und (b,c) E R --> (a,c) E R. Nur welche Möglichkeiten bleiben denn da offen, die ich belegen kann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:58 Di 14.07.2009 | | Autor: | statler |
> Mm, also so klar ist mir das nicht. Wenn ich mir das Paar
> (a,b) anschaue, dann muss doch für die Transitivität
> folgendes zeigen: (a,b) E R und (b,c) E R --> (a,c) E R.
> Nur welche Möglichkeiten bleiben denn da offen, die ich
> belegen kann?
Von Transitivität ist in deiner ursprünglichen Aufgabe überhaupt keine Rede! Oder sind wir jetzt woanders unterwwegs?
D
|
|
|
| |
|
Ahja stimm, es ist ja reflexiv und symmetrisch gefragt. War mein Fehler! Ich mach momentan (vor der Klausur) so viele vers. Aufgaben ... 
Aber auch bei reflexiv und symmetrisch steh ich auf dem Schlauch. Die Paare der Diagonalen kann ich ja nicht mehr wählen, weil die durch die Reflexivität "fest" sind. Es können ja eigentlich nur noch die Paare (b,a), (c,a) und (b,c) sein. Aber wenn ich die Verändere, dann ändern sich ja auch die symmetrischen Paare oberhalb der Symmetrieachse. Also ich hätte dann [mm] 2^{3} [/mm] = 8 Relationen. Aber ganz klar ist mir das nicht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:20 Di 14.07.2009 | | Autor: | statler |
Mahlzeit!
> Aber auch bei reflexiv und symmetrisch steh ich auf dem
> Schlauch. Die Paare der Diagonalen kann ich ja nicht mehr
> wählen, weil die durch die Reflexivität "fest" sind. Es
> können ja eigentlich nur noch die Paare (b,a), (c,a) und
> (b,c) sein. Aber wenn ich die Verändere, dann ändern sich
> ja auch die symmetrischen Paare oberhalb der
> Symmetrieachse. Also ich hätte dann [mm]2^{3}[/mm] = 8 Relationen.
> Aber ganz klar ist mir das nicht.
Wieso denn das nicht? Die gesuchte Relation hat auf jeden Fall die 'reflexiven' Paare dabei, und von den 3 Paaren unterhalb der Diagonalen wählst du eine beliebige Teilmenge (8 Mögl.) und packst die gespiegelten Paare dazu. Fertig.
Gruß
Dieter
|
|
|
| |
|
Die Paare untehalb der Diagonalen sind doch dann nur noch (b,a), (c,a), (c,b). Aber wie wähle ich dann aus? Ich gehe doch nach der Formel [mm] 2^{n} [/mm] oder? Somit bei mir [mm] 2^{3}, [/mm] da ich noch 3 "freie" Paare unterhalb der Diagonalen habe?
|
|
|
| |
|
Ich habe mir zu Übung mal Gedanken gemacht, wie es wäre, wenn die Menge vierelementig wäre, als Betrag von M = 4.
reflexiv
$ [mm] \pmat{ (a,a) & (a,b) & (a,c) & (a,d) \\ (b,a) & (b,b) & (b,c) & (b,d) \\ (c,a) & (c,b) & (c,c) & (c,d) \\ (d,a) & (d,b) & (d,c) & (d,d)} [/mm] $
Dann wären hier die Paare auf der Diagonalen wieder fest (a,a), (b,b), (c,c) und (d,d). Das heißt ich habe noch [mm] 2^{12} [/mm] Möglichkeiten Paare zu finden, die mit den 4 festen eine Relation bilden.
symmetrisch
a) die Paare auf der Diagonalen
b) die Paare (a,b), (a,c), (a,d), (b,c), (b,d), (c,d) (alle anderen werden durch die Symmetrie geändert)
zusammen sind es 10 Paare und somit [mm] 2^{10} [/mm] mögliche Relationen.
Stimmt das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:33 Mi 15.07.2009 | | Autor: | statler |
Hi!
> Ich habe mir zu Übung mal Gedanken gemacht, wie es wäre,
> wenn die Menge vierelementig wäre, als Betrag von M = 4.
Sehr gut!
> reflexiv
> [mm]\pmat{ (a,a) & (a,b) & (a,c) & (a,d) \\ (b,a) & (b,b) & (b,c) & (b,d) \\ (c,a) & (c,b) & (c,c) & (c,d) \\ (d,a) & (d,b) & (d,c) & (d,d)}[/mm]
>
> Dann wären hier die Paare auf der Diagonalen wieder fest
> (a,a), (b,b), (c,c) und (d,d). Das heißt ich habe noch
> [mm]2^{12}[/mm] Möglichkeiten Paare zu finden, die mit den 4 festen
> eine Relation bilden.
... eine reflexive Relation ...
> symmetrisch
> a) die Paare auf der Diagonalen
> b) die Paare (a,b), (a,c), (a,d), (b,c), (b,d), (c,d)
> (alle anderen werden durch die Symmetrie geändert)
>
> zusammen sind es 10 Paare und somit [mm]2^{10}[/mm] mögliche
> Relationen.
... mögliche symmetrische Relationen ...
> Stimmt das?
Ja.
Dieter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:30 Mi 15.07.2009 | | Autor: | statler |
Guten Morgen!
> Die Paare untehalb der Diagonalen sind doch dann nur noch
> (b,a), (c,a), (c,b). Aber wie wähle ich dann aus? Ich gehe
> doch nach der Formel [mm]2^{n}[/mm] oder? Somit bei mir [mm]2^{3},[/mm] da
> ich noch 3 "freie" Paare unterhalb der Diagonalen habe?
Ja, du kannst aus dieser Menge mit 3 Elementen irgend eine Teilmenge wählen, dafür gibt es 8 Möglichkeiten. Dann ergänzt du das um die Menge der Diagonalpaare und um die Menge der gespiegelten Paare und erhältst eine symm. u. refl. Relation.
Für eine perfekte Lösung müßtest du das jetzt formal korrekt aufschreiben und nachweisen, daß die Beziehung zwischen diesen Teilmengen und den gesuchten Relationen bijektiv ist.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Uii, muss ich das für jede Teilmenge machen (also reflexiv, symmetrisch) oder für die ganzen Teilmengen zusammen. Ich versuche das ganze mal für die reflexiven Teilmengen anhand eines Pfeildiagramms.
a --> a
b --> b
c --> c
Diese Teilmenge wäre ja bijektiv.
(injketiv: zu jedem a wird ein Element aus B zugeordnet und jedes Elemenrt aus B hat höchstens ein Urbild.
surjektiv: jedes Element aus B hat mindestens ein Urbild)
Diese Bedingungen sind ja dann alle erfüllt.
Nur wenn ich mir nun die Teilmenge der symmtrischen Relationen ((a,a), (a,b), (a,c), (b,b), (b,c), (c,c) anschaue und in ein Pfeildiagramm einzeichne, dann hat zum Beispiel b zwei Urbilder und c sogar drei. Damit wären die ja nicht mehr injektiv???
PS: Also wenn ich dann in der Klausur den Beweis zur Bijektivität weglasse, kriege ich für die Anzahl der Relationen auch keine Punkte???
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:25 Mi 15.07.2009 | | Autor: | statler |
Mahlzeit!
Das wächst sich ja langsam aus...
> Uii, muss ich das für jede Teilmenge machen (also
> reflexiv, symmetrisch) oder für die ganzen Teilmengen
> zusammen. Ich versuche das ganze mal für die reflexiven
> Teilmengen anhand eines Pfeildiagramms.
>
> a --> a
> b --> b
> c --> c
>
> Diese Teilmenge wäre ja bijektiv.
Zur Sprache: Mengen sind nicht bijektiv, Mengen sind auch nicht rot oder grün oder schnell oder langsam. Abbildungen können bijektiv sein oder auch nicht.
Ich hatte mir das in etwa so vorgestellt. Du nimmst das untere Dreieck, also {(b,a), (c,a), (c,b)} =: M und davon die Potenzmenge Pot(M). Pot(M) hat 8 Elemente, das lernt man in der Mengenlehre. Wie hängt jetzt Pot(M) mit den symm. + refl. Relationen R auf {a, b, c} zusammen? Ich möchte eine Bijektion f zwischen Pot(M) und R haben.
Dazu definiere ich für (ein geordnetes Paar (x,y) (x,y)' := (y,x) und für) eine Menge N von geordneten Paaren N' := {(u,v) | (v,u) [mm] \in [/mm] N}. Außerdem soll noch D := {(a,a), (b,b), (c,c)} sein. Jetzt kann ich sagen und hinschreiben, was f sein soll.
f: Pot(M) [mm] \to [/mm] R, N [mm] \mapsto [/mm] N [mm] \cup [/mm] N' [mm] \cup [/mm] D.
Warum ist das eine Bijektion?
Weil es eine Umkehrabbildung gibt! Aber das hier und jetzt auseinanderzufriemeln, habe ich keinen Bock mehr. Versuch mal selbst dein Glück.
> PS: Also wenn ich dann in der Klausur den Beweis zur
> Bijektivität weglasse, kriege ich für die Anzahl der
> Relationen auch keine Punkte???
Das glaube ich eher nicht, aber zur Mathematik gehört auch die Fähigkeit, sich in der Fachsprache ausdrücken zu können. Durch multple-choice-Aufgaben wird dieses Können leider abgebaut, jedenfalls nicht gefördert.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:56 Mi 15.07.2009 | | Autor: | Lockenheld |
Gut, dann will ich mich zum Schluss nur noch für die geduldige und genaue Hilfe bedanken! Wirklich super nett!
|
|
|
|
