Relation und Umkehrrelation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Wie muss ich mir
[mm] $R\circ R^{-1} [/mm] = [mm] \{ (x,y) \mid \exists z: xRz \text{ und } yRz\}$ [/mm]
vorstellen?
Sei [mm] $R\subseteq A\times [/mm] B$.
Sieht R in etwa so aus: [mm] \{(a_1,b_1),(a1,b_2),...,(a1,b_n),(a_2,b_1),...,(a_m,b_n)\} [/mm] ?
Mir ist klar dass R nicht für alle a etwas aussagen muss. (Im Gegensatz zu einer Funktion)
Aber wie sieht dann [mm] $R\circ R^{-1}$ [/mm] aus?
|
|
| |
|
> Wie muss ich mir
> [mm]R\circ R^{-1} = \{ (x,y) \mid \exists z: xRz \text{ und } yRz\}[/mm]
> vorstellen?
Hallo,
ich hoffe, daß ich mit meiner Antwort Deine Frage treffe.
Nehmen wir [mm] A:=\{a,b,c\}, B:=\{1,2,3,4\}.
[/mm]
Es ist [mm] A\times B=\{(a,1), (a,2), (a,3), (a,4),(b,1), (b,2), (b,3), (b,4), (c,1), (c,2), (c,3), (c,4)\}.
[/mm]
Eine jegliche Relation zwischen A und B ist eine Teilmenge dieser Menge.
Nehmen wir für das Beispiel mal
[mm] R:=\{\(a,1), (a,2),(b,1), (b,3), (c,4)\}.
[/mm]
Dann ist
[mm] R^{-1}=\{(1,a), (2,a), (1,b), (3,b), (4,c)\}.
[/mm]
Bevor wir und [mm] R\circ R^{-1} [/mm] betrachten, schauen wir erstmal, wie die Verkettung von Relationen definiert ist:
Für zwei Relationen
R ⊆ A × B und S ⊆ C × D
ist
S ∘ R := { ( a , d ) ∈ A × D ∣ ∃ b ∈ B ∩ C : ( a , b ) ∈ R und ( b , d ) ∈ S } .
Übertragen auf unser Beispiel:
Für zwei Relationen
[mm] R^{-1} [/mm] ⊆ [mm] B\times [/mm] A und R ⊆ A × B
ist
R ∘ [mm] R^{-1} [/mm] := { ( x,y) ∈ B × B ∣ ∃ z ∈ A : ( x , z ) ∈ [mm] R^{-1} [/mm] und ( z , y ) ∈ R }
[={ ( x,y) ∈ B × B ∣ ∃ z ∈ A : ( z,x) ∈ R und ( z , y ) ∈ R } ]
Wir stellen fest: R ∘ [mm] R^{-1} [/mm] ist eine Teilmenge von [mm] B\times [/mm] B.
Nun gucken wir mal, welche Elemente da drin sind:
R ∘ [mm] R^{-1} =\{(1,1), (1,2), (1,3), (2,1),(2,2), (3,3), (4,4)\}.
[/mm]
> Aber wie sieht dann [mm]R\circ R^{-1}[/mm] aus?
Um solche Fragen beantworten zu können, hilft mir immer zweierlei:
1. Die Definitionen hinschreiben.
2. Die Sache (wie hier jetzt geschehen) anhand eines kleinen, konkreten Beispiels nachzuvollziehen.
(Du könntest, wenn es Dir klargeworden ist, als nächstes ja mal
[mm] R^{-1}\circ [/mm] R anschauen.)
LG Angela
|
|
|
| |
|
Hallo Angela,
fehlt bei [mm] R^{-1} [/mm] nicht noch (1,b) ? Oder habe ich das falsch verstanden?
Zur Absicherung: wenn [mm] (a,b)\in [/mm] R, dann [mm] (b,a)\in R^{-1} [/mm] ?
So müsste in deinem Beispiel
[mm] R\circ R^{-1} [/mm] Elemente der Form (x,y) haben, wobei [mm] x,y\in \{a,b,c\}
[/mm]
Aber wie genau weiß ich nicht!
Und wie genau sich [mm] R^{-1}\circ [/mm] R zusammensetzt kann ich halt nicht nachvollziehen außer nach "Kochrezept" (die Definition für Verkettung)
Ich melde mich vielleicht später wenn ich eine (bessere) Frage formulieren kann.
|
|
|
| |
|
> Hallo Angela,
>
> fehlt bei [mm]R^{-1}[/mm] nicht noch (1,b) ? Oder habe ich das
> falsch verstanden?
Oh ja, das hatte ich vergessen.
Hab's korrigiert.
>
> Zur Absicherung: wenn [mm](a,b)\in[/mm] R, dann [mm](b,a)\in R^{-1}[/mm] ?
Ja.
>
> So müsste in deinem Beispiel
>
> [mm]R\circ R^{-1}[/mm] Elemente der Form (x,y) haben, wobei [mm]x,y\in \{a,b,c\}[/mm]
Nö.
[mm] R\circ R^{-1} [/mm] habe ich doch vorgemacht. Die Menge enthält Zahlenpaare.
[mm] R^{-1}\circ [/mm] R ingegen entält Buchstabenpaare.
>
> Aber wie genau weiß ich nicht!
>
> Und wie genau sich [mm]R^{-1}\circ[/mm] R zusammensetzt kann ich
> halt nicht nachvollziehen außer nach "Kochrezept" (die
> Definition für Verkettung)
Naja, das "Kochrezept" ist das A und O!
Ohne Definitionen läuft gar nichts! Sie sind docH das Allerwichtigste.
Du weißt:
es ist [mm] (a,1)\in [/mm] R.
Nun guckst Du, welche Paare aus [mm] R^{-1} [/mm] Du wie einen Dominostein dranlegen kannst.
An (a,1) passen (1,a) und (1,b),
also sind (a,a) und (a,b) [mm] \in[/mm] [mm]R^{-1}\circ[/mm] R .
So macst Du es bei allen Elementen aus R.
LG Angela
>
> Ich melde mich vielleicht später wenn ich eine (bessere)
> Frage formulieren kann.
|
|
|
| |
|
Also nach deinem Dominoprinzip:
[mm] R^{-1}\circ R=\{(a,a),(a,b),(b,b),(b,a),(c,c)\}
[/mm]
Jetzt meine Vermutungen:
Zunächst einmal gilt: wenn [mm] (\gamma,a)\in R^{-1}, [/mm] dann [mm] (a,a)\in R^{-1}\circ [/mm] R
Außerdem: Wenn R a n Elemente zuordnet, dann:
sind n Elemente der Gestalt (a,x) in [mm] R^{-1}\circ [/mm] R, wobei [mm] (a,x)\in A\times [/mm] A (Also Kreuzprodukt der Definitionsmenge)
Und: [mm] g:=R^{-1}\circ [/mm] R und auch [mm] h:=R\circ R^{-1} [/mm] sind _immer_ symmetrisch, egal was für eine Relation R ist.
Was muss ich wissen um obiges zu beweisen? (Oder besser zu formulieren)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:24 So 06.11.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:26 Fr 04.11.2016 | | Autor: | Omega91 |
Hallo sinnlos123,
Ich beziehe mich auf das Beispiel von Angela.
Es ist doch $R [mm] \circ R^{-1} \subseteq [/mm] B [mm] \times [/mm] B$.
Entsprechend ist natürlich [mm] $R^{-1} \circ [/mm] R [mm] \subseteq [/mm] A [mm] \times [/mm] A$
Wie sieht $A [mm] \times [/mm] A$ aus? (Angela sagte bereits Buchstabenpaare) -- schreib die Menge doch mal hin!
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:04 Fr 04.11.2016 | | Autor: | sinnlos123 |
[mm] \{(a,a),(a,b),(a,c),...(c,c)\} [/mm] ist [mm] A\times [/mm] A (das war mir aber auch schon klar ;) )
Angela's Hinweis mit dem Dominosteineffekt hat mir schon sehr geholfen.
Allerdings möchte ich halt eine "Down to earth" Regel für beides finden.
[mm] R\circ R^{-1} [/mm] und [mm] R^{-1}\circ [/mm] R.
Im Moment, versteh ich aber das noch nicht ganz.
Meine "sehr" unrigorose Annahme:
Egal ob [mm] R\circ R^{-1} [/mm] oder [mm] R^{-1}\circ [/mm] R, es werden nur solche Elemente behandelt, die von R überhaupt "angefasst" werden.
Naja, wie gesagt, ich formuliere eine genauere Frage, wenn ich es kann ;)
|
|
|
|
