Transitivität < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Kreuzen Sie alle Eigenschaften an, die die Relation R auf N erfuellt.
a) N = {1,2,3,4,5} und R = {(1,1),(2,2),(2,3),(3,3),(3,4),(4,4),(5,5)}
b) N = {1,2,3,4,5} und R = {(1,1),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} |
Hallo Leute,
wieder einmal wende ich mich an euch mit einer Frage:
Laut Loesung ist das R in a) nicht transitiv und das R in b) transitiv.
Das ist mir raetselhaft, weil wenn das R in b) transitiv ist so muss gelten:
((3,4) [mm] \in [/mm] R [mm] \wedge [/mm] (4,4) [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (3,4) [mm] \in [/mm] R
((2,4) [mm] \in [/mm] R [mm] \wedge [/mm] (4,4) [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (2,4) [mm] \in [/mm] R
((2,3) [mm] \in [/mm] R [mm] \wedge [/mm] (3,3) [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (2,3) [mm] \in [/mm] R
Ausserdem muesste gelten
((1,1) [mm] \in [/mm] R [mm] \wedge [/mm] (1,1) [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (1,1) [mm] \in [/mm] R
In der Bedingung fuer die Transitivitaet steht nicht, dass x [mm] \not= [/mm] y [mm] \not= [/mm] z gelten muss
In a) kann man aber das gleiche Spiel wiederholen:
((2,3) [mm] \in [/mm] R [mm] \wedge [/mm] (3,3) [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (2,3) [mm] \in [/mm] R
((3,4) [mm] \in [/mm] R [mm] \wedge [/mm] (4,4) [mm] \in [/mm] R) [mm] \Rightarrow [/mm] (3,4) [mm] \in [/mm] R
Wieso ist R in a) dann aber nicht ebenfalls transitiv?
Gruss
mathlooser
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:24 Do 06.02.2014 | | Autor: | Sax |
Hi,
> Kreuzen Sie alle Eigenschaften an, die die Relation R auf N
> erfuellt.
>
> a) N = {1,2,3,4,5} und R =
> {(1,1),(2,2),(2,3),(3,3),(3,4),(4,4),(5,5)}
> b) N = {1,2,3,4,5} und R =
> {(1,1),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
> Hallo Leute,
>
> wieder einmal wende ich mich an euch mit einer Frage:
>
> Laut Loesung ist das R in a) nicht transitiv und das R in
> b) transitiv.
>
> Das ist mir raetselhaft, weil wenn das R in b) transitiv
> ist so muss gelten:
>
> ((3,4) [mm]\in[/mm] R [mm]\wedge[/mm] (4,4) [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (3,4) [mm]\in[/mm] R
> ((2,4) [mm]\in[/mm] R [mm]\wedge[/mm] (4,4) [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (2,4) [mm]\in[/mm] R
> ((2,3) [mm]\in[/mm] R [mm]\wedge[/mm] (3,3) [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (2,3) [mm]\in[/mm] R
>
Das muss in der Tat gelten und das tut es ja auch.
Unklar ist, worauf du da hinaus willst. Wenn [mm] (2,3)\in [/mm] R gilt, folgt daraus (auch ohne irgendwelche zusätzlichen Voraussetzungen) immer, dass [mm] (2,3)\in [/mm] R richtig ist.
> Ausserdem muesste gelten
>
> ((1,1) [mm]\in[/mm] R [mm]\wedge[/mm] (1,1) [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (1,1) [mm]\in[/mm] R
>
> In der Bedingung fuer die Transitivitaet steht nicht, dass
> x [mm]\not=[/mm] y [mm]\not=[/mm] z gelten muss
aber es steht drin, dass es für alle x,y,z gelten muss !
>
> In a) kann man aber das gleiche Spiel wiederholen:
>
> ((2,3) [mm]\in[/mm] R [mm]\wedge[/mm] (3,3) [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (2,3) [mm]\in[/mm] R
> ((3,4) [mm]\in[/mm] R [mm]\wedge[/mm] (4,4) [mm]\in[/mm] R) [mm]\Rightarrow[/mm] (3,4) [mm]\in[/mm] R
>
> Wieso ist R in a) dann aber nicht ebenfalls transitiv?
>
Tipp 1: Worin unterscheiden sich A und B ?
Tipp 2: In B kommt (2,4) vor, in A nicht.
Versuche, ein Beispiel zu finden, dass die Existenz von (2,4) in der Relation zwingend erforderlich macht, damit die Relation transitiv ist.
Damit kannst du zeigen, dass A nicht transitiv ist, für die Transitivität von B musst du das Fettgedruckte bemühen.
Gruß Sax.
|
|
|
| |
|
Hi Sax,
danke erstmal fuer deine Antwort.
> Das muss in der Tat gelten und das tut es ja auch.
> Unklar ist, worauf du da hinaus willst. Wenn [mm](2,3)\in[/mm] R
> gilt, folgt daraus (auch ohne irgendwelche zusätzlichen
> Voraussetzungen) immer, dass [mm](2,3)\in[/mm] R richtig ist.
Ich moechte darauf hinaus, dass jedes Element in der Menge R transitiv sein muss, damit die Relation transitiv ist. (Ist das korrekt?) und das habe ich versucht anschaulich darzustellen ganz im Sinne folgender Regel:
transitiv, falls (xRy [mm] \wedge [/mm] yRz) [mm] \Rightarrow [/mm] xRz fuer alle x, y, z [mm] \in [/mm] M
> aber es steht drin, dass es für alle x,y,z gelten muss !
hierzu gleich eine weitere Frage:
Was heisst hier fuer alle?
- Heisst es, dass alle Elemente der Menge N = {1,2,3,4,5} in R vorkommen muessen? Ich glaube nicht, denn sonst waere b) sicher nicht transitiv, da (x, 5), (5, x) [mm] \not\in [/mm] R
- oder heisst es, dass alle verwendetetn Ziffern/Zahlen in R aus N sein muessen. Vermutlich ist es so.
Aber dann stellt sich die Frage, warum bei der reflexivitaet alle paare mit
(x, x) [mm] \in [/mm] R fuer alle x [mm] \in [/mm] M
enthalten sein muessen, obwohl hier auch fuer alle steht. Z.B ist b) nicht reflexiv, weil eben die (5,5) fehlt.
> Tipp 1: Worin unterscheiden sich A und B ?
a) ist reflexiv, da die Diagonale (in Matrixdarstellung) vollstaendig ist (1,1), (2,2), ... ,(5,5), ausserdem fehlt a) das paar (2,4).
> Tipp 2: In B kommt (2,4) vor, in A nicht.
> Versuche, ein Beispiel zu finden, dass die Existenz von
> (2,4) in der Relation zwingend erforderlich macht, damit
> die Relation transitiv ist.
> Damit kannst du zeigen, dass A nicht transitiv ist, für
Genau da liegt mein Problem.
> die Transitivität von B musst du das Fettgedruckte
> bemühen.
Ich komme leider nicht weiter.
Gruss
mathlooser
|
|
|
| |
|
| Aufgabe | Kreuzen Sie alle Eigenschaften an, die die Relation R auf N erfuellt.
a) N = {1,2,3,4,5} und R = {(1,1),(2,2),(2,3),(3,3),(3,4),(4,4),(5,5)}
b) N = {1,2,3,4,5} und R = {(1,1),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} |
Hallo,
untersuchen wir beide Relationen zunächst auf Reflexivität:
R heißt reflexiv, wenn für alle [mm] x\in [/mm] N gilt xRx.
Wenn es für alle x aus N gelten muß, muß es für x=1,2,3,4,5 gelten.
Also müssen im Falle der Reflexivität (1,1), (2,2), (3,3), (4,4), (5,5) in der Relation R enthalten sein.
Bei a) ist dies der Fall, bei b) nicht.
Die Symmetrie:
für alle [mm] x,y\in [/mm] N gilt
xRy ==> yRx.
Das bedeutet: falls (!) ein Paar (x,y) in R ist, kann es nicht anders sein, als daß (y,x) auch drin ist.
Es ist aber nicht zwangsläufig jedes Paar (x,y) in der Relation.
Wenn man dies möchte, lautet die Bedingung: für alle x,y [mm] \in [/mm] N gilt: xRy.
Das ist etwas völlig anderes als die Symmetrie.
Weder a) noch b) ist symmetrisch. Ich denke, das siehst Du leicht.
Nun zu Deiner eigentlichen Frage, der Tansitivität:
R ist transitiv, wenn für alle [mm] x,y,z\in [/mm] N gilt: (xRy und yRz) ==> xRz.
Das sagt: wenn eine Relation transitiv ist, und wenn (x,y) und (y,z) in R sind, dann ist zwingend auch (x,z) in R.
Transitivität fordert aber nicht, daß für alle x,y,z [mm] \in [/mm] N die Paare (x,y) und (y,z) in der Relation enthalten sind.
a) ist nicht transitiv:
es sind (2,3) und (3,4) in R, aber (2,4) ist nicht drin.
b) ist transitiv, denn Du findest keine zwei Zahlenpaare, bei denen das nicht funktioniert.
Bei allen klappt's.
Ich versuche, auf Deine Fragen einzugehen, was nicht ganz leicht ist.
Im Idealfall haben sie sich inzwischen bereits geklärt.
> Ich moechte darauf hinaus, dass jedes Element in der Menge
> R transitiv sein muss, damit die Relation transitiv ist.
Es gibt keine transitiven Elmenente.
Oder wurde "transitives Element" in Eurer Vorlesung definiert?
Transitivität ist eine Eigenschaft, die eine Relation haben kann.
>
> transitiv, falls (xRy [mm]\wedge[/mm] yRz) [mm]\Rightarrow[/mm] xRz fuer alle
> x, y, z [mm]\in[/mm] M
>
> > aber es steht drin, dass es für alle x,y,z gelten muss !
Ich habe es oben erklärt.
Für alle x,y,z gilt:
wenn xRy und yRz, dann kann es nicht anders sein, als daß auch xRz gilt. Für kein x,y,z wird eine Ausnahme gemacht. Es gilt für alle.
Aber es ist nicht zwingend vorgeschrieben, daß für alle x,y,z die Relationen xRy und yRz gelten.
Nur wenn sie gelten, dann hat es bei Transitivität die Konsequenz, daß auch xRz gilt.
Ich hoffe, daß Du jetzt durchblickst.
LG Angela
|
|
|
| |
|
Hallo Angela,
wie jedesmal, bin ich von der Ausfuehrlichkeit der Antworten und dem Eifer der Antwortenden beeindruckt. Ich danke dafuer (und natuerlich fuer die hilfreiche Antwort).
> R heißt reflexiv, wenn für alle $ [mm] x\in [/mm] $ N gilt xRx.
> Wenn es für alle x aus N gelten muß, muß es für x=1,2,3,4,5 gelten.
> Also müssen im Falle der Reflexivität (1,1), (2,2), (3,3), (4,4), (5,5) in der
> Relation R enthalten sein.
Hier muessen alle x [mm] \in [/mm] N in R in der Form xRx vertreten sein, weil es keinen Anlass dazu gibt, dass nicht alle x [mm] \in [/mm] N gemeint sind. Ok.
> Bei a) ist dies der Fall, bei b) nicht.
klar.
> Die Symmetrie:
> für alle $ [mm] x,y\in [/mm] $ N gilt
> xRy ==> yRx.
> Das bedeutet: falls (!) ein Paar (x,y) in R ist, kann es nicht anders sein,
> als daß (y,x) auch drin ist.
Kann es sein dass hier der Folgerungspfeil eine entscheidende Rolle spielt?
Falls(aber nicht zwingend) [mm] \Rightarrow [/mm] dann(in jedem Fall)
xRy muss nicht zwingend ein El. aus R sein, aber wenn es eins ist, dann muss auch yRx ein El. aus R sein.
> Es ist aber nicht zwangsläufig jedes Paar (x,y) in der Relation.
> Wenn man dies möchte, lautet die Bedingung: für alle x,y $ [mm] \in [/mm] $ N gilt: > xRy. Das ist etwas völlig anderes als die Symmetrie.
somit auch klar.
> Weder a) noch b) ist symmetrisch. Ich denke, das siehst Du leicht
jupp
> Nun zu Deiner eigentlichen Frage, der Tansitivität:
> R ist transitiv, wenn für alle $ [mm] x,y,z\in [/mm] $ N gilt: (xRy und yRz) ==> xRz.
> Das sagt: wenn eine Relation transitiv ist, und wenn (x,y) und (y,z) in R
> sind, dann ist zwingend auch (x,z) in R.
> Transitivität fordert aber nicht, daß für alle x,y,z $ [mm] \in [/mm] $ N die Paare (x,y)
> und (y,z) in der Relation enthalten sind.
Hier wieder die Begruendung mit dem Folgerungspfeil richtig?
> a) ist nicht transitiv:
> es sind (2,3) und (3,4) in R, aber (2,4) ist nicht drin.
Ich glaube ich habs gerade verstanden.
Eine Frage bleibt jedoch noch offen (im Prinzip der Grund fuer die ganze Verwirrung):
Waere
N = {1,2,3,4,5} und R = {(1,1),(2,2),(2,3),(3,3),(4,4),(5,5)} auch transitiv? (also ohne (3,4))
Meine Behauptung: Ja, weil 2R3 [mm] \wedge [/mm] 3R3 [mm] \Rightarrow [/mm] 2R3 richtig?
Also darf man xRx als Bedingung auf der linken Seite des Pfeils verwenden?
> b) ist transitiv, denn Du findest keine zwei Zahlenpaare, bei denen das
> nicht funktioniert.
> Bei allen klappt's.
Auch klar.
> Ich versuche, auf Deine Fragen einzugehen, was nicht ganz leicht ist.
Das ist dir gut gelungen.
> Im Idealfall haben sie sich inzwischen bereits geklärt.
Ja, ich hoffe es.
> Es gibt keine transitiven Elmenente.
Hab ich verstanden.
> Oder wurde "transitives Element" in Eurer Vorlesung definiert?
Nein. Das hatte ich offenbar falsch verstanden.
> Transitivität ist eine Eigenschaft, die eine Relation haben kann.
Alles klar.
> Ich habe es oben erklärt.
> Für alle x,y,z gilt:
> wenn xRy und yRz, dann kann es nicht anders sein, als daß auch xRz gilt. > Für kein x,y,z wird eine Ausnahme gemacht. Es gilt für alle.
> Aber es ist nicht zwingend vorgeschrieben, daß für alle x,y,z die
> Relationen xRy und yRz gelten.
> Nur wenn sie gelten, dann hat es bei Transitivität die Konsequenz, daß
> auch xRz gilt.
> Ich hoffe, daß Du jetzt durchblickst.
Ja, super! Nur die Frage oben bleibt noch offen. Danke nochmal.
Gruss
mathlooser
|
|
|
| |
|
> wie jedesmal, bin ich von der Ausfuehrlichkeit der
> Antworten und dem Eifer der Antwortenden beeindruckt. Ich
> danke dafuer (und natuerlich fuer die hilfreiche Antwort).
Hallo,
nett, daß Du das sagst.
Ich freue mich - auch im Namen aller Mitstreiter hier im Forum.
Ja, Du hast es jetzt verstanden.
> Waere
>
> N = {1,2,3,4,5} und R =
> {(1,1),(2,2),(2,3),(3,3),(4,4),(5,5)} auch transitiv? (also
> ohne (3,4))
>
> Meine Behauptung: Ja,
Stimmt!
> weil 2R3 [mm]\wedge[/mm] 3R3 [mm]\Rightarrow[/mm] 2R3
> richtig?
Fast.
Mit (2,3) und (3,3) ist auch (2,3) in R, wie Du sagst.
Es gibt aber ein qeiteres zu prüfendes Paar von Paaren:
mit (2,2) und (2,3) ist auch (2,3) in R.
Weitere "Dominopaare" gibt es nicht.
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:47 Do 06.02.2014 | | Autor: | mathlooser |
Super! Danke!
|
|
|
|
