reflexive Relation < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:51 Mo 14.11.2005 | | Autor: | Becks |
Guten Morgen!
Ich habe eine kleine Frage zu einer reflexiven Relation.
Zum Beispiel haben wir eine Menge M = {1, 2, 3, 4, 5}
Eine Relation ist reflexiv wenn für alle a [mm] \in [/mm] M gilt (aRa)
Aber wieviele unterschiedliche reflexive Relationen gibt es dann für M?
Wären das dann:
R1 = {(1,1)}
R2 = {(1,1)(2,2)}
...
R5 = {(1,1)(2,2)(3,3)(4,4)(5,5)} ?
Weil dann steht jedes mal z.B. 1 und 1 in Relation. Weil 2 und 5 kann doch nicht in Relation stehen oder?
Ich wäre sehr dankbar, wenn mir jemand das etwas erklären könnte. Weil das mir reflexiv, transitiv geht bei mir nich in den Kopf :)
Viele Grüße
Becks
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:17 Mo 14.11.2005 | | Autor: | Sigrid |
Hallo Becks,
> Guten Morgen!
>
> Ich habe eine kleine Frage zu einer reflexiven Relation.
> Zum Beispiel haben wir eine Menge M = {1, 2, 3, 4, 5}
> Eine Relation ist reflexiv wenn für alle a [mm]\in[/mm] M gilt
> (aRa)
> Aber wieviele unterschiedliche reflexive Relationen gibt
> es dann für M?
> Wären das dann:
> R1 = {(1,1)}
Diese Relation ist nicht reflexiv, da z.B. [mm] (2,2) \not\in R_1 [/mm]
> R2 = {(1,1)(2,2)}
> ...
> R5 = {(1,1)(2,2)(3,3)(4,4)(5,5)} ?
Nur [mm] R_5 [/mm] ist reflexiv
> Weil dann steht jedes mal z.B. 1 und 1 in Relation. Weil 2
> und 5 kann doch nicht in Relation stehen oder?
Wrum nicht?
Wenn
[mm] (1,2) \in R [/mm],
widerspricht das doch nicht der Reflexivität.
> Ich wäre sehr dankbar, wenn mir jemand das etwas erklären
> könnte. Weil das mir reflexiv, transitiv geht bei mir nich
> in den Kopf :)
Wie du richtig gesagt hast, heißt reflexiv: aRa für alle [mm] a \in M [/mm]
oder anders gesagt [mm] (a,a) \in R [/mm] für alle [mm] a \in M [/mm]
Also ist schon mal
[mm] R_1 = \{(1,1), (2,2), (3,3), (4,4), (5,5) \} [/mm]
eine reflexive Relation.
Jetzt kannst du beliebig Paare dazu packen. Z.B.
[mm] R_2 = \{(1,1), (2,2), (3,3), (4,4), (5,5), (1,2) \} [/mm]
oder
[mm] R_3 = \{(1,1), (2,2), (3,3), (4,4), (5,5), (1,2), (2,3), (1,3) \} [/mm]
Diese Relationen sind auch transitiv.
Eine reflexive, nichttransitive Relation ist z.B.
[mm] R_4 = \{(1,1), (2,2), (3,3), (4,4), (5,5), (1,2), (2,4)\} [/mm]
Hilft dir das?
Gruß
Sigrid
> Viele Grüße
>
> Becks
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:27 Mo 14.11.2005 | | Autor: | Becks |
Hallo!
Hmm, also das verwirrt mich jetzt etwas. Wenn ich ich M = {1,2,3,4,5} habe und ne Relation R = {(1,1)} Dann ist diese doch reflexiv oder nicht?
Ok, wenn ich nun eine andere Relation habe:
R2 = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,2)}
Dann ist die noch reflexiv, weil (1,1) reflexiv ist und (2,2) ? Aber wenn ich
R2 = {(1,1), (3,3), (4,4), (5,5), (1,2)} habe, ist die Relation nicht mehr reflexiv wegen dem fehlenden (2,2)-Paar?
Ich glaub ich versteh das nie :-/
MFG Becks
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:13 Mo 14.11.2005 | | Autor: | Sigrid |
Hallo Becks,
> Hallo!
>
> Hmm, also das verwirrt mich jetzt etwas. Wenn ich ich M =
> {1,2,3,4,5} habe und ne Relation R = {(1,1)} Dann ist diese
> doch reflexiv oder nicht?
Aber es ist keine reflexive Relation auf M, da dann für alle Elemente [mm] a \in M [/mm] gelten muss: [mm] (a,a) \in R [/mm].
Beachte, dass R ja eine Teilmenge von M [mm] \times [/mm] M ist.
Es ist eine reflexive Relation auf der Menge [mm] N = {1} [/mm]
> Ok, wenn ich nun eine andere Relation habe:
> R2 = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,2)}
> Dann ist die noch reflexiv, weil (1,1) reflexiv ist und
> (2,2) ? Aber wenn ich
> R2 = {(1,1), (3,3), (4,4), (5,5), (1,2)} habe, ist die
> Relation nicht mehr reflexiv wegen dem fehlenden
> (2,2)-Paar?
Genau. Sie ist dann nicht mehr reflexiv auf M.
> Ich glaub ich versteh das nie :-/
Keine Sorge. Bald wirst du dich wundern, dass du es mal nicht verstanden hast.
Gruß
Sigrid
>
> MFG Becks
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:35 Mo 14.11.2005 | | Autor: | Becks |
Hallo!
Ich glaube mir wird das schon etwas klarer. Aber jetzt hätte ich so ne Art Masterfrage :)
Nehmen wir an ich hätte eine endliche Menge M mit n Elementen. Wieviel reflexive Relationen würde es dann geben?
Bei M = {1}
wären das eine. R = {(1,1)}
Bei M = {1, 2}
wären das R1 = {(1,1)}
R2 = {(2,2)}
R3 = {(1,1),(2,2)}
R4 = {(1,1),(2,2),(1,2)}
R5 = {(1,1),(2,2),(2,1)}
R6 = {(1,1),(2,2),(1,2),(2,1)}
Würde das so stimmen? Gibt es da überhaupt ne Abhängigkeit, sodass man das in ne Formel packen könnte?
Habe ich das mit der Reflexion jetzt besser verstanden?
Fragen über Fragen, ich hoffe ihr könnt mir da nochmal helfen.
Liebe Grüße
Becks
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:13 Di 15.11.2005 | | Autor: | Micha |
Hallo!
> Hallo!
>
> Ich glaube mir wird das schon etwas klarer. Aber jetzt
> hätte ich so ne Art Masterfrage :)
> Nehmen wir an ich hätte eine endliche Menge M mit n
> Elementen. Wieviel reflexive Relationen würde es dann
> geben?
Dazu später...
> Bei M = {1}
> wären das eine. R = {(1,1)}
![[ok]](/images/smileys/ok.gif "[ok]")
>
> Bei M = {1, 2}
> wären das R1 = {(1,1)}
![[notok]](/images/smileys/notok.gif "[notok]")
> R2 = {(2,2)}
Hier fehlt beides mal das jeweils andere Paar... für Reflexivität müssen beide Elemente aus M, also 1 und 2 in Relation mit sich selbst stehen... Es können also nur die Relationen auf M reflexiv sin, die sowohl (1,1) als auch (2,2) enthalten.
> R3 = {(1,1),(2,2)}
> R4 = {(1,1),(2,2),(1,2)}
> R5 = {(1,1),(2,2),(2,1)}
> R6 = {(1,1),(2,2),(1,2),(2,1)}
die anderen sind ok
Vielleicht stellst du dir R5 mal als eine Art Tabelle vor:
1 2
1 R
2 R R
Also (1,1), (2,1) und (2,2) sind in der Relation... reflexive Relationen haben die Eigenschaft auf der Diagonalen immer ein R stehen zu haben... es darf keine Lücke geben...
>
> Würde das so stimmen? Gibt es da überhaupt ne Abhängigkeit,
> sodass man das in ne Formel packen könnte?
> Habe ich das mit der Reflexion jetzt besser verstanden?
> Fragen über Fragen, ich hoffe ihr könnt mir da nochmal
> helfen.
Zu deiner Masterfrage: also auf M mit n Elementen gibt es [mm] $2^{n^2} [/mm] = [mm] 2^{n *n}$ [/mm] verschiedene Relationen (Entweder steht es in Relation oder nicht und das für jedes der n x n Felder in der Tabelle)
davon musst du alle rausrechnen, die auf der Diagonalen nicht durchgehend ein R haben... also [mm] $2^n$ [/mm] Stück... Macht also
#Anzahl der reflexiven Relationen = [mm] $\frac{2^n^2}{2^n}= \frac{2^n *2^n}{2^n} [/mm] = [mm] 2^n$
[/mm]
Ich hoffe das stimmt so...
Gruß Micha 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:41 Do 03.05.2007 | | Autor: | Lurchi |
> #Anzahl der reflexiven Relationen = [mm]\frac{2^n^2}{2^n}= \frac{2^n *2^n}{2^n} = 2^n[/mm]
>
> Ich hoffe das stimmt so...
Fast.
#Anzahl der reflexiven Relationen = [mm]\frac{2^n^2}{2^n}= 2^{n^2-n}[/mm]
|
|
|
|
