Transitivität

24.11.2020, 22:18

Yasminx3

Transitivität

$\begin{eqnarray*} R=\{(a,a),(a,b),(a,c),(b,b),(b,c)\} \end{eqnarray*}$

$\begin{eqnarray*} A= \{a,b,c,d\} \end{eqnarray*}$

Hier wäre die Relation doch transitiv. oder? verwirrt

Für Transitivität gilt doch: $\begin{eqnarray*} \forall x,y,z \in A:xRy \wedge yRz \Rightarrow xRz \end{eqnarray*}$

Betrachte ich ein anderes Beispiel:

$\begin{eqnarray*} R=\{(a,c),(a,b)\} \end{eqnarray*}$

$\begin{eqnarray*} aRc \wedge cRb \end{eqnarray*}$ , was ja eine falsche Aussage ist, da $\begin{eqnarray*} (c,b) \notin R \end{eqnarray*}$ , also wäre diese Relation auch transitiv, weil ich aus etwas falschem was wahres folgern kann. verwirrt

24.11.2020, 22:27

Elvis

Auf diesen Beitrag antworten »

Beide Relationen sind transitiv, denn es fehlt nichts.

24.11.2020, 23:38

Yasminx3

Auf diesen Beitrag antworten »

Hey Elvis

,

danke für die schnelle Antwort. Ok gut, war mir da echt unsicher. Hätte da noch eine kleine Frage, wenn es keine Umstände macht. smile

Sei mal $\begin{eqnarray*} G = \{1, . . . , 5\} \end{eqnarray*}$ und G folgende Relation auf R

$\begin{eqnarray*} R = \{(1, 1), (1, 5), (2, 4), (3, 3), (4, 1), (4, 2), (5, 4)\} \end{eqnarray*}$

Und es gibt noch zwei:

$\begin{eqnarray*} R_1 =\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,1),(1,5)\} \end{eqnarray*}$

R1 wäre reflexiv und symmetrisch, aber nicht transtiv.

$\begin{eqnarray*} R_2 = \{(2,1),(1,2),(1,1)\} \end{eqnarray*}$

R2 wäre symmetrisch, transitiv, aber nicht reflexiv.

Sind R1 und R2 die kleinstmöglichen, die ich bilden kann, die diese Relationseigenschaften erfüllen, wenn ja, wie kann ich das beweisen?

Rein intuitiv würde ich sagen:

z.z: $\begin{eqnarray*} R_1 =\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,1),(1,5)\} \end{eqnarray*}$ ist kleinstmöglich gewählt.

(1) Eine Relation ist reflexiv, falls $\begin{eqnarray*} \forall x \in G:xR_1x \Rightarrow (1,1),(2,2),(3,3),(4,4),(5,5) \in R_1 \end{eqnarray*}$
Das heißt, damit unsere Relation reflexiv ist, brauchen wir schon mal $\begin{eqnarray*} |G| \end{eqnarray*}$ Elemente und zwar genau die, die auf sich selber abbilden.

(2) Für Transitivität gilt: $\begin{eqnarray*} \forall x,y,z \in G:xR_1y \wedge yR_1z \Rightarrow xR_1z<br /> \end{eqnarray*}$
Wenn unsere Relation nur die Elemente enthält, die auf sich selber abbilden, ist sie auch transitiv, bedeutet, wir müssen weitere Elemente hinzufügen, die die Transitivität verhindern. Und zwar genau zwei.

Ich bin allgemein sonderlich schlecht in Beweisen. Hast du da Tipps für mich?

25.11.2020, 09:34

Elvis

Auf diesen Beitrag antworten »

Mathematik lebt von Begriffen, die in Definitionen festgelegt werden, von Aussagen, die in Sätzen formuliert werden und von Beweisen. Nur wenige große Mathematiker haben große Beweise hinterlassen, davon können wir viel lernen, wir können aber nicht beanspruchen, selbst so großartige Sachen zu produzieren, schon gar nicht als Anfänger. Bemühe dich um saubere Begriffe, lerne und arbeite so gut du kannst, mehr kann man nicht verlangen.

Definitionen:
Eine Menge ist die Zusammenfassung wohldefinierter und wohlunterschiedener Objekte unseres Denkens oder unserer Anschauung zu einem Ganzen. (Georg Cantor)
Das cartesische Produkt MxN zweier Mengen M und N ist die Menge aller Paare (m,n) mit m in M und n in N.
Eine Relation R zwischen zwei Mengen M und N ist eine Teilmenge von MxN.
Eine Relation R auf einer Menge M ist eine Teilmenge von MxM.
(Funktionen bzw. Abbildungen sind etwas ganz anderes, auch wenn manche Leute Funktionen als spezielle Relationen definieren.)

Eigenschaften von Relationen R auf einer Menge M:
r) R ist reflexiv genau dann wenn die Diagonale {(x,x):x in M} Teilmenge von R ist.
s) R ist symmetrisch, wenn für alle (x,y) in R auch (y,x) in R ist.
t) R ist transitiv, wenn für alle (x,y) und (y,z) in R auch (x,z) in R ist.

R1 ist nicht symmetrisch, weil (2,1) in R1, (1,2) nicht. Nicht transitiv, weil (2,1) und (1,5) drin, aber (2,5) nicht.
R2 hast du richtig erkannt.

Nach dem gesagten ist die Diagonale die kleinstmögliche Äquivalenzrelation (r,s,t) auf M.

Nachtrag: Wenn du nicht mehr zur Schule gehst sondern studierst, wäre es mir lieber, deine Fragen im Hochschulbereich zu beantworten, dort wage ich formalere und umfassendere Antworten.
Man könnte noch darauf eingehen, dass die kleinste reflexive / symmetrische / transitive Relation, die eine gegebene Relation R auf einer Menge umfasst, auch die reflexive / symmetrische / transitive Hülle von R genannt wird und durch Hinzunahme geeigneter Elemente aus MxM konstruiert wird. Wenn man alle drei Eigenschaften berücksichtigt, erhält man so die kleinste R umfassende Äquivalenzrelation.

25.11.2020, 17:00

Yasminx3

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Mathematik lebt von Begriffen, die in Definitionen festgelegt werden, von Aussagen, die in Sätzen formuliert werden und von Beweisen. Nur wenige große Mathematiker haben große Beweise hinterlassen, davon können wir viel lernen, wir können aber nicht beanspruchen, selbst so großartige Sachen zu produzieren, schon gar nicht als Anfänger. Bemühe dich um saubere Begriffe, lerne und arbeite so gut du kannst, mehr kann man nicht verlangen.

Das beruhigt mich. In den Vorlesungen werden so viele Definitionen eingeleitet, viele Beweise gemacht, alles sieht so abstrakt aus. Ich versuche mir die Dinge immer an Beispielen zu erklären. Es ist aber sehr schwer.

Zitat:

Original von Elvis
Nachtrag: Wenn du nicht mehr zur Schule gehst sondern studierst, wäre es mir lieber, deine Fragen im Hochschulbereich zu beantworten, dort wage ich formalere und umfassendere Antworten.
Man könnte noch darauf eingehen, dass die kleinste reflexive / symmetrische / transitive Relation, die eine gegebene Relation R auf einer Menge umfasst, auch die reflexive / symmetrische / transitive Hülle von R genannt wird und durch Hinzunahme geeigneter Elemente aus MxM konstruiert wird. Wenn man alle drei Eigenschaften berücksichtigt, erhält man so die kleinste R umfassende Äquivalenzrelation.

Ja, werde ich in Zukunft machen. Hüllen haben wir leider noch nicht, werden wir wahrscheinlich morgen machen. Zumindest steht das so im Skript.

$\begin{eqnarray*} R_1 =\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,1),(1,5)\} \end{eqnarray*}$

Dann würde ich einfach, also um die Symmetrie wiederherzustellen.

$\begin{eqnarray*} R_1 =\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,1),(1,5)\} \cup \{(5,1),(1,2)\} \end{eqnarray*}$

R1 wäre dann reflexiv und symmetrisch, aber nicht transitiv. Nur ist dann die Frage, ob das die kleinstmögliche ist, die man so bilden, die genau diese Eigenschaften erfüllt. verwirrt

25.11.2020, 17:52

Elvis

Auf diesen Beitrag antworten »

So ist es richtig, die neue Relation solltest du dann aber R2 nennen, denn die gegebene R1 unterscheidet sich davon. Zwei Objekte dürfen nur dann den gleichen Namen haben, wenn sie gleich sind. Ja, das ist die kleinstmögliche Erweiterung von R1, die symmetrisch ist. Beweis: Diese beiden neuen Elemente sind notwendig, also geht es nicht kleiner, und sie erfüllen den Zweck, R1 zu einer symmetrischen Relation R2 zu machen, mithin ist R2 die symmetrische Hülle von R1. Eine Hülle ist übrigens auch immer der Durchschnitt aller umfassenden Mengen mit der gewünschten Eigenschaft. Zur transitiven Hülle R3 kommt dann zu R2 noch (2,5) und (5,2) dazu, wodurch R3 eine Äquivalenzrelation wird. Fleißig weiter so, dann wird alles gut. Freude

25.11.2020, 18:45

Yasminx3

Auf diesen Beitrag antworten »

Vielen Dank. Wink

25.11.2020, 19:55

Elvis

Auf diesen Beitrag antworten »

Noch eine wichtige Anmerkung im Zusammenhang mit Äquivalenzrelationen. Eine solche zerlegt die Menge immer in Klassen, das sind disjunkte Teilmengen der Menge, deren Vereinigung wieder die Menge ergibt. Jede Klasse besteht genau aus den Elementen, die zueinander äquivalent sind. Im Beispiel $\begin{eqnarray*} R3 \end{eqnarray*}$ sind die Klassen offenbar $\begin{eqnarray*} \{1,2,5\},\{3\},\{4\} \end{eqnarray*}$ und man nennt $\begin{eqnarray*} G/R3=\{\{1,2,5\},\{3\},\{4\}\} \end{eqnarray*}$ die Faktormenge oder Quotientenmenge.

Gerade an so einfachen Beispielen kann man sich klar machen, worum es in der Mengenlehre geht.

25.11.2020, 22:06

Yasminx3

Auf diesen Beitrag antworten »

Danke dir für ganzen Erklärungen. Das hilft echt fürs Verständnis smile

Ich bin gerade dabei eine Aufgabe zu lösen. Wenn ich eine Relation $\begin{eqnarray*} R=\{(a,b)\} \end{eqnarray*}$ von einer Grundmenge $\begin{eqnarray*} A= \{a,b\} \end{eqnarray*}$ habe.

Was ist dann $\begin{eqnarray*} R^0 \end{eqnarray*}$ ?

Im Skript steht, dass es die Identität ist. Weißt aber nicht ganz genau, was damit gemeint ist. verwirrt

25.11.2020, 22:29

Elvis

Auf diesen Beitrag antworten »

Jetzt hast du mich erwischt. Ich weiß fast alles, d.h. alles bis auf endlich viele Sachen - oder doch eher fast nichts. Augenzwinkern

Davon habe ich noch nie gehört. Könnte anfangen zu raten, aber das ist nicht seriös. Hat vermutlich mit Verknüpfung von Relationen zu tun. Dein Skript weiß da bestimmt mehr als ich, und du kommst bestimmt noch dahinter, wenn du weiter liest.

25.11.2020, 23:30

Yasminx3

Auf diesen Beitrag antworten »

Ahh oki. Kein Problem. smile

Ich melde mich mal morgen nach der Vorlesung nochmal. Mal sehen, was der Prof dazu sagt. ^^

26.11.2020, 17:37

Yasminx3

Auf diesen Beitrag antworten »

Also, der Professor hat heute dazu gesagt.

Wenn man eine Grundmenge A hat, dann ist $\begin{eqnarray*} R^0 \end{eqnarray*}$ die Identität auf A, also all die Elemente die auf sich selber abbilden. Er hatte das so definiert. smile

26.11.2020, 18:15

Elvis

Auf diesen Beitrag antworten »

Der Professor hat immer recht. Er darf das so definieren, weil er Professor ist. Er darf das so definieren, wenn er eine Relation R auf einer Menge A als Abbildung von A nach A versteht, so dass jedes (x,y) in R bedeutet, dass dem Element x vermöge der Abbildung R das Element y zugeordnet wird.
Achtung: Dadurch wird R nicht notwendig zu einer Funktion, denn eine Funktion ist bei dieser Herangehensweise eine Relation, bei der jedem Urbild genau ein Bild zugeordnet wird. Ich mache das nicht so, weil ich möchte, dass der Begriff der Funktion mit dem Begriff der Abbildung zusammenfällt. Deshalb definiere ich eine Relation R auf A als Teilmenge von AxA. Eine Funktion f von A nach B ist für mich ein Tripel (A,B,Graph(f)).
Bei mir ist der Graph einer Funktion eine Relation, bei deinem Professor ist eine Funktion eine Relation. Bei mir ist eine Funktion eine Abbildung, bei deinem Professor ist eine Relation eine Abbildung. So kann er R^0 als identische Abbildung betrachten. Für mich ist R^0 die Diagonale von AxA, also die Teilmenge, die eine reflexive Relation mindestens enthalten muss.
Lass dich nicht von mir verwirren, lerne das, was dein Professor sagt, er sagt nichts falsches. Alles was er weiterhin lehrt wird auf dem aufbauen was er sagt. Wenn du ein Buch studierst, musst du immer darauf achten, wie die Begriffe definiert sind, nichts ist einheitlich und alles fließt.

Neue Frage »

Antworten »

Transitivität

Verwandte Themen