Relationen (refl., symm.) < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Angegeben ist die Anzahl der Elemente (3,4) einer Menge M, anhand derer man angeben soll wieviele
a) Relationen
b) reflexive Relationen
c) symmetrische Relationen
es gibt. |
Hallo!
zu a)
Dazu habe ich mir überlegt, dass die verschiedenen Elemente einer Relation Tupel sind, d. h. dass eine Menge mit drei Elementen [mm] 3^2 [/mm] = 9 Tupel hat und man diese nun unterschiedlich miteinander kombinieren kann um die Relationen zu erhalten.
Ja und da ist jetzt mein Problem meine Lösung sagt, dass es nun [mm] 2^9 [/mm] verschiedene Relationen gibt und ich verstehe nicht warum. Man kann natürlich alle aufmalen und nachzählen, aber das wird bei mehr als zwei Elementen doch relativ viel ;)
zu b) Da gab es eine ähnliche Frage in diesem Forum (reflexive Relation ist der Titel) Und das habe ich da schon ziemlich gut verstanden. Ich könnte also die Relationen für zwei oder auch mehr Elemente alle aufschreiben.
Dort ist auch eine Formel angegeben, nach der man die reflexiven Relationen bestimmen kann
[mm] \bruch{2^{n^2}}{2^n} [/mm] = [mm] 2^{n^2-n}
[/mm]
und wie man auf diese Formel kommt ist dort zwar erklärt jedoch verstehe ist das nicht ganz. Also im Prinzip ist das ja die Anzahl der reflexiven Relationen durch die Anzahl der möglichen Tupel oder?
zu c) Da bin ich leider noch nicht so weit gekommen. Also symmetrisch bedeutet ja das wenn x [mm] \cong [/mm] y => y [mm] \cong [/mm] x
dass heißt mögliche symmetrische Relationen zu M = {1,2,3} wären:
R1 : {(1,2) (2,1)}
R2 : {(1,3) (3,1)}
R3 : {(1,3) (3,1) (2,3) (3,2)}
R4: {(1,3) (3,1) (2,3) (3,2) (1,1)}
Stimmt es, dass man wenn symmetrische Paare hat man andere beliebig dazupacken kann?
Also zu M = {1,2}
wären alle symmetrischen Relationen dann
R1 = {(1,2) (2,1)}
R2 = {(1,2) (2,1) (1,1)}
R3 = {(1,2) (2,1) (2,2)}
R4 = {(1,2) (2,1) (1,1) (2,2)}
oder?
Ich habe auch für symmetrische Relationen eine Formel gefunden weiß jedoch nicht, ob sie stimmt und wie man auf sie kommt, sie lautet:
[mm] 2^{\bruch{n\cdot (n+1)}{2}}
[/mm]
Gibt es so etwas auch für transitive Relationen?
Danke schonmal im Voraus
LG WiebkeMarie
|
|
| |
|
Hallo WiebkeMarie!
> Angegeben ist die Anzahl der Elemente (3,4) einer Menge M,
Soll (3,4) bedeuten, dass es zwei Aufgaben sind, einmal mit 3 und einmal mit 4, oder wie?
> anhand derer man angeben soll wieviele
> a) Relationen
> b) reflexive Relationen
> c) symmetrische Relationen
> es gibt.
> Hallo!
> zu a)
> Dazu habe ich mir überlegt, dass die verschiedenen Elemente
> einer Relation Tupel sind, d. h. dass eine Menge mit drei
> Elementen [mm]3^2[/mm] = 9 Tupel hat und man diese nun
> unterschiedlich miteinander kombinieren kann um die
> Relationen zu erhalten.
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> Ja und da ist jetzt mein Problem meine Lösung sagt, dass
> es nun [mm]2^9[/mm] verschiedene Relationen gibt und ich verstehe
> nicht warum. Man kann natürlich alle aufmalen und
> nachzählen, aber das wird bei mehr als zwei Elementen doch
> relativ viel ;)
Also, Relation bedeutet ja, dass zwei Elemente in Relation stehen, sagen wir mal, wenn sie dies tun, bilden wir sie auf 1 ab, ansonsten auf 0. Also für alle Elemente aus [mm] M\times [/mm] M haben wir eine Abbildung [mm] $M\times M\to\{0,1\}$. [/mm] Nun haben wir in [mm] $M\times [/mm] M$ 9 Elemente - wie viele mögliche Abbildungen gibt es nun? Ich habe dies sicher schon mal hier erklärt, aber ich tue es immer gerne wieder.  Also für das erste Element, von mir aus das Tupel (a,a), gibt es genau zwei Möglichkeiten, worauf es abgebildet werden kann, nämlich 0 oder 1. Für das zweite Element, von mir aus (a,b), gibt es wieder diese zwei Möglichkeiten, also haben wir insgesamt schon 4 Möglichkeiten, denn es kann sein, dass sowohl (a,a) als auch (a,b) auf 0 abgebildet werden, oder dass beide auf 1 abgebildet werden (das sind dann schon zwei Möglichkeiten), oder dass jeweils eins von beiden auf 0 und das andere auf 1 abgebildet werden, das sind die anderen beiden Möglichkeiten. Und für das dritte Element gibt es wieder 2 Möglichkeiten, macht dann schon 4*2=8 usw.. Bei 9 Elementen erhältst du also [mm] 2^9. [/mm] Falls dir das so noch nicht klar ist, dann schreib es dir für die ersten paar Elemente mal auf.
> zu b) Da gab es eine ähnliche Frage in diesem Forum
> (reflexive Relation ist der Titel) Und das habe ich da
Du kannst Diskussionen auch hier verlinken, kopiere dazu einfach die URL (das, was oben in der Leiste steht) von der Diskussion, und füge es als Link ein (wie man Links einfügt, steht in den Eingabehilfen). Wenn du das machst, kann ich mir die Diskussion auch durchlesen und kann auch verstehen, was da steht.
> schon ziemlich gut verstanden. Ich könnte also die
> Relationen für zwei oder auch mehr Elemente alle
> aufschreiben.
> Dort ist auch eine Formel angegeben, nach der man die
> reflexiven Relationen bestimmen kann
> [mm]\bruch{2^{n^2}}{2^n}[/mm] = [mm]2^{n^2-n}[/mm]
> und wie man auf diese Formel kommt ist dort zwar erklärt
> jedoch verstehe ist das nicht ganz. Also im Prinzip ist das
> ja die Anzahl der reflexiven Relationen durch die Anzahl
> der möglichen Tupel oder?
Ich würde es mir so herleiten: Reflexiv bedeutet ja, dass z. B. die Elemente (a,a), (b,b) und (c,c) alle zueinander in Relation stehen (also nach obigem auf 1 abgebildet werden). Von diesen drei Tupeln steht die Abbildung also fest, denn wenn sie auf 0 abgebildet würden, ständen sie ja nicht in Relation, also wäre die Relation nicht reflexiv! Nun bleiben uns noch 9-3=6 Tupel übrig, für die es wieder viele Möglichkeiten gibt, auf was sie abgebildet werden können - nämlich wie viele Möglichkeiten? Naja, genau [mm] 2^6 [/mm] - ist doch klar, oder? Also haben wir auch insgesamt [mm] 2^6 [/mm] mögliche reflexive Relationen.
Bei c) möchte ich mich lieber nicht festlegen, aber ich würde mir nicht unbedingt Formeln merken sondern versuchen, es mir jeweils selbst herzuleiten. In diesem Fall würde ich das so machen:
Die Elemente (a,a), (b,b) und (c,c) können sowohl auf 0 oder auf 1 abgebildet werden, dafür gibt's also schon mal [mm] 2^3 [/mm] Möglichkeiten. Für die restlichen Elemente gilt, dass (a,b) und (b,a) jeweils auf das Gleiche abgebildet werden, also entweder beide auf 0 oder beide auf 1. Dies gilt ebenso für (a,c) und (c,a) sowie für (b,c) und (c,b). Für diese 3 "Paare von Paaren" haben wir also ebenfalls [mm] 2^3 [/mm] Möglichkeiten, macht insgesamt [mm] 2^3*2^3=2^6 [/mm] Möglichkeiten. Aber evtl. habe ich hier etwas vergessen oder so, deswegen lasse ich das mal noch jemanden anders erklären...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo Bastiane!
Danke für deine ausführliche Antwort so habe ich das noch gar nicht gesehen.
zu a) Also dann kann man sich das ja wie ein Baumdiagramm vorstellen, dass sozusagen jedes Element eine neue Spalte aufmacht und die Möglichkeit hat enweder in Relation zu stehen oder nicht, also entweder auf 1 abgebildet zu werden oder auf 0. Und dadurch verdoppelt sich natürlich mit jedem neuen Element die Pfade. Das habe ich jetzt wirklich verstanden.
zu b) Also der Link wär gewesen
https://matheraum.de/read?t=106774&v=t
hätte ich auch drauf kommen können den sofort reinzustellen... nächstes Mal.
Das habe ich jetzt auch verstanden, dass wird wirklich sehr logisch so. Denn die (a,a) (b,b) und (c,c) stehen ja sozusagen fest und bei den restlichen 6 Tupeln hat man jewails wieder die zwei Möglichkeiten, dass sie entweder in Relatione stehen also auf 0 abgebildet werden oder nicht also auf 1 abgebildet werden. Danke!
zu c) Also ich muss sagen auch c finde ich jetzt sehr logisch. Ich habe vorhin die Lösung dazu in meinen Unterlagen gefunden (ich wiederhole alten Stoff) und die lautet auch [mm] 2^6 [/mm] .
Finde das auch sehr verständlich denn das ist ja dann im Prinzip dasselbe wie bei a). also ich denke ich habe es verstanden.
Wenn man nun eine Menge mit vier Elementen hat, würde dass also bedeuten, dass es [mm] 2^4 [/mm] = 16 tupel geben würde. Davon würden dann also 6 Paare von Tupel, nämlich
(a,b) (b,a)
(a,c) (c,a)
(a,d) (d,a)
(b,c) (c,b)
(b,d) (d,b)
(c,d) (d,c)
entweder auf 0 abgebildet oder nicht. Es gebe also [mm] 2^6 [/mm] Möglichkeiten.
Es würden dann 16-12=4 Tupel überbleiben die frei abgebildet werden könnten also [mm] 2^4 [/mm] Möglichkeiten hätten. Das macht dann [mm] 2^6 \cdot 2^4 [/mm] = 2^10 verschieden symmetrische Relationen. Stimmt das soweit?
Danke für deine Hilfe!
Lg WiebkeMarie
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:39 Mi 02.04.2008 | | Autor: | DaMenge |
Hallo,
> Danke für deine ausführliche Antwort so habe ich das noch
> gar nicht gesehen.
> zu a) Also dann kann man sich das ja wie ein Baumdiagramm
> vorstellen, dass sozusagen jedes Element eine neue Spalte
> aufmacht und die Möglichkeit hat enweder in Relation zu
> stehen oder nicht, also entweder auf 1 abgebildet zu werden
> oder auf 0. Und dadurch verdoppelt sich natürlich mit jedem
> neuen Element die Pfade. Das habe ich jetzt wirklich
> verstanden.
Die toll beschriebene Abbildung könnte man sich auch einfacher als Matrix vorstellen - stell dir mal eine Relation auf der Menge M vor, die genau n viele Elemente hat und wir schreiben diese Relation jetzt in eine nxn Matrix.
Dabei schreiben wir an Position (i,j) eine 1, wenn das Element i mit dem Element j in Relation steht, ok?
D.H wir haben eine nxn Matrix und müssen uns für jeden Eintrag nun entscheiden, ob wir eine 1 oder ein 0 reinschreiben wollen.
Die Anzahl der verschiedenen Matrizen ist nun [mm] $2^{(n*n)}$
[/mm]
Für reflexive Relationen gilt ja, dass alle (i,i) automatisch in der Relation sein müssen, d.h. bei unserer Matrix wissen wir, dass die Diagonale schon mit Einsen gefüllt ist - es bleibt also noch die restlichen $n*n-n=n(n-1)$ vielen Einträge zu wählen, also gerade : [mm] $2^{n(n-1)}$
[/mm]
Bei Symmetrie wissen wir ja, dass mit jedem (i,j) auch ein (j,i) mit in der Relation sein muss, wenn wir also in unserer Matrix einen Eintrag in der oberen Dreiecksmatrix vornehmen, taucht dieselbe Zahl auch an der entsprechenden Stelle in der unteren Dreiecksmatrix auf. Wir haben also die Wahl für die obere Dreiecksmatrix zu treffen. (Die Diagonal muss mit gewählt werden !)
Das macht gerade [mm] $n+(n-1)+\ldots [/mm] +1 = [mm] \frac{n(n+1)}{2}$ [/mm] Einträge zu wählen , also [mm] $2^{\frac{n(n+1)}{2}}$
[/mm]
Jetzt die Zusatzfrage: wieviele Relationen gibt es, die sowohl reflexiv als auch symmetrisch sind ?!?
> Das macht dann [mm]2^6 \cdot 2^4[/mm] = 2^10 verschieden
> symmetrische Relationen. Stimmt das soweit?
Jap, das stimmt dann natürlich n=4 !
viele Grüße,
DaMenge
|
|
|
|
