Relationen, reflexiv/.... < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:19 Do 18.12.2008 | | Autor: | dau2 |
Hi,
muss man nicht für die symmetrie einer relation für alle x x,y y,x bilden?
Wenn ich das mache wie unten in R1...ist die Relation dann nicht automatisch transitiv?
M = { a,b,c,d }
R1: soll reflexiv,symmetrisch aber nicht transitiv sein
reflexiv: a,a b,b c,c d,d
symmetrisch: a,b b,a a,c c,a a,d d,a b,c c,b b,d d,b c,d d,c
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:11 Do 18.12.2008 | | Autor: | dr-oetker |
> muss man nicht für die symmetrie einer relation für alle x
> x,y y,x bilden?
Klar, eine Relation [mm]R[/mm] ist symmetrisch, wenn für alle Paare [mm](x,y) \in R[/mm] auch [mm](y,x) \in R[/mm] ist.
> Wenn ich das mache wie unten in R1...ist die Relation dann
> nicht automatisch transitiv?
>
> M = { a,b,c,d }
>
> R1: soll reflexiv,symmetrisch aber nicht transitiv sein
> reflexiv: a,a b,b c,c d,d
> symmetrisch: a,b b,a a,c c,a a,d d,a b,c c,b b,d d,b
> c,d d,c
>
Was meinst Du damit?
Wenn Du meinst, daß [mm](a,b),(b,a),...,(d,c) \in R1[/mm] sind, dann steht jedes Element aus M mit jedem anderen in R1-Relation. Dann ist R1 trivialerweise transitiv.
Oder suchst Du nach Beispielen für reflexive, symmetrische, aber nicht transitive Relationen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:02 Do 18.12.2008 | | Autor: | dau2 |
> Oder suchst Du nach Beispielen für reflexive, symmetrische, aber nicht transitive Relationen?
- genau
aber ich glaube du hast die Frage schon beantwortet, dann reicht für symmetrisch also bereits
a,b b,a ?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:05 Fr 19.12.2008 | | Autor: | Fulla |
Hallo nochmal,
eine Relation heißt symmetrisch wenn gilt:
WENN [mm] (a,b)\in [/mm] R1 DANN FOLGT [mm] (b,a)\in [/mm] R1
Wenn du deine Relation [mm] $R_1$ [/mm] z.B. so "bastelst":
[mm] $R_1=\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(d,a),(a,d)\}$,
[/mm]
ist sie reflexiv ($(a,a), (b,b), (c,c), (d,d)$ sind drin),
symmetrisch (für jedes Paar in [mm] $R_1$ [/mm] ist auch das "vertauschte" drin),
aber nicht transitiv (z.B. [mm] $(a,b)\in R_1$ [/mm] und [mm] $(b,c)\in R_1$ [/mm] aber [mm] $(a,c)\not\in R_1$).
[/mm]
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:50 Fr 19.12.2008 | | Autor: | dau2 |
Ah, danke.
Wenn ich aus R1:
[mm] $R_1=\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(d,a),(a,d)\}$, [/mm]
jetzt eine reflexive/symmetrische/transitive machen möchte muss ich nur
(a,c) und (c,a) hinzufügen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:54 Sa 20.12.2008 | | Autor: | Marcel |
Hallo,
> Ah, danke.
>
> Wenn ich aus R1:
>
> [mm]R_1=\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(d,a),(a,d)\}[/mm],
>
> jetzt eine reflexive/symmetrische/transitive machen möchte
> muss ich nur
> (a,c) und (c,a) hinzufügen?
Du musst überlegen, was alles notwendig ist, und am Ende quasi überprüfen, ob das auch schon hinreichend ist (d.h. hier i.W., dass Du nichts "übersehen" oder "vergessen" hast).
Wenn Du obige Relation auch gerne transitiv hättest, reicht das nicht:
Ich sehe z.B. auch, dass $(b,c)$ und $(c,d)$ in [mm] $R_1$ [/mm] liegen. Wenn man also aus [mm] $R_1$ [/mm] eine Relation [mm] $\tilde{R}$ [/mm] basteln will, die transitiv ist, muss dann, neben [mm] $R_1 \subset \tilde{R}$ [/mm] auch sicher schonmal $(a,c),(c,a),(b,d) [mm] \in \tilde{R}$ [/mm] gelten. Und generell muss man eigentlich bei jedem Schritt immer prüfen, was dann noch alles neu entstehen könnte (hier müsste dann z.B., wegen Symmetrie, auch $(d,b)$ aufgenommen werden):
Also:
Wenn Du zunächst [mm] $\tilde{R}=R_1$ [/mm] hast, und feststellst: Ich muss $(a,c)$ in [mm] $\tilde{R}$ [/mm] aufnehmen, also definieren wir zunächst das (neue) [mm] $\tilde{R}:=R_1 \cup{(a,c)}\,,$ [/mm] so musst Du prüfen, was Du dann alles mit aufzunehmen hast:
1. Schritt:
[mm] $\bullet$ [/mm] Wegen Symmetrie muss auch $(c,a)$ aufgenommen werden (merken für später)
[mm] $\bullet$ [/mm] Nun muss man prüfen, welche neuen Elemente durch $(a,c)$ mit Transitivität gebildet werden können:
Dazu musst Du nun alle Elemente aus [mm] $\tilde{R}$ [/mm] abklappern, die "mit $c$ beginnen":
1.) [mm] $(a,\blue{c})$ [/mm] und [mm] $(\blue{c},c)$ [/mm] sind in [mm] $\tilde{R}$, [/mm] durch Transitivität entsteht da nichts neues (nur wieder $(a,c)$)
2.) Es ist auch $(c,b) [mm] \in \tilde{R}$, [/mm] also muss mit $(a,c) [mm] \in \tilde{R}$ [/mm] dann im nächsten Schritt, wegen $(a,c)$ und $(c,b)$ in [mm] $\tilde{R}$, [/mm] auch $(a,b)$ in [mm] $\tilde{R}$ [/mm] sein. Auch da ist nichts mehr zu tun.
3.) Analog mit $(a,c)$, $(c,d)$.
Also beenden wir den 1. Durchgang und [mm] $\tilde{R}$ [/mm] bekommt ein neues Element, welches wir uns gemerkt haben:
2. Schritt:
Nun ist [mm] $\tilde{R}=R_1 \cup\{(a,c)\} \cup\{(c,a)\}$.
[/mm]
$(c,a)$ ist ein neues Element in (dem neuen) [mm] $\tilde{R}$. [/mm] Das symmetrische Element $(a,c)$ ist eh schon im alten [mm] $\tilde{R}$ [/mm] und damit auch im neuen. Für die Transitivität:
Prüfe alle Elemente, die "mit $a$" beginnen (im [mm] $\tilde{R}$ [/mm] aus dem vorhergehenden Schritt, also [mm] $\tilde{R}=R_1 \cup\{(a,c)\}\,.$
[/mm]
Etc.
Einfaches Beispiel:
Wir wollen aus [mm] $R=\{(1,1), (2,1)\}$ [/mm] eine Äquivalenzrelation über [mm] $\{1,2,3\}$ [/mm] machen, die wir [mm] $\tilde{R}$ [/mm] nennen. Klar ist sconmal:
$(1,1), (2,2), (3,3)$ müssen dann alle in [mm] $\tilde{R}$ [/mm] liegen (Reflexivität!).
Aber zuerst erkennen wir, dass, wegen Symmetrie, auch $(1,2)$ in [mm] $\tilde{R}$ [/mm] liegen muss, also setzen wir
[mm] $\tilde{R}=R \cup\{(1,2)\}=\{(1,1), (2,1), (1,2)\}\,.$
[/mm]
Die Transitivität zeigt dann, dass auch $(2,2)$ aufgenommen werden muss, also im nächsten Schritt:
[mm] $\tilde{R}=R \cup\{(1,2)\} \cup\{(2,2)\}=\{(1,1), (2,1), (1,2),(2,2)\}\,.$
[/mm]
Zu guter letzt fehlt noch $(3,3)$ (Reflexivität!), also
[mm] $\tilde{R}=R \cup\{(1,2)\} \cup\{(2,2)\} \cup\{(3,3)\}=\{(1,1), (2,1), (1,2),(2,2),(3,3)\}\,.$
[/mm]
Und das Ding [mm] $\tilde{R}=\{(1,1), (2,1), (1,2),(2,2),(3,3)\}$ [/mm] ist dann nun wirklich eine ÄR auf [mm] $\{1,2,3\}$, [/mm] mit $R$ gebildet.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:00 Sa 20.12.2008 | | Autor: | dau2 |
Danke, jetzt ist es klar.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:51 Fr 19.12.2008 | | Autor: | Fulla |
Hallo dau2,
aus Symmetrie und Reflexivität folgt nicht automatisch die Transitivität.
Schau dir z.B. die Relation [mm] "$\sim$" [/mm] auf [mm] \mathbb{R} [/mm] an:
$a [mm] \sim [/mm] b\ [mm] \Leftrightarrow\ |a-b|\leq [/mm] 4$
Die ist symmetrisch ($|a-b|=|b-a|$), reflexiv [mm] ($|a-a|=0\leq [/mm] 4$), aber nicht transitiv: z.B. [mm] $2\sim [/mm] 5$ und [mm] $5\sim [/mm] 8$, aber [mm] $2\not\sim [/mm] 8$
Lieben Gruß,
Fulla
|
|
|
|
