www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Relationen" - Transitivität
Transitivität < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Transitivität: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:01 Do 06.02.2014
Autor: 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 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

        
Bezug
Transitivität: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                
Bezug
Transitivität: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:13 Do 06.02.2014
Autor: mathlooser

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

Bezug
                        
Bezug
Transitivität: Antwort
Status: (Antwort) fertig Status 
Datum: 14:45 Do 06.02.2014
Autor: angela.h.b.

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

Bezug
                                
Bezug
Transitivität: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:52 Do 06.02.2014
Autor: mathlooser

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

Bezug
                                        
Bezug
Transitivität: Antwort
Status: (Antwort) fertig Status 
Datum: 21:17 Do 06.02.2014
Autor: angela.h.b.


> 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




Bezug
                                                
Bezug
Transitivität: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:47 Do 06.02.2014
Autor: mathlooser

Super! Danke!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]