Relationen + transitive Hülle

Neue Frage »

29.10.2010, 08:55	Estorias	Auf diesen Beitrag antworten »
Relationen + transitive Hülle Meine Frage: Hallo, ich brauche eure Hilfe bei der folgenden Aufgabe. Ich habe teilweise auch Lösungen/Ansätze, aber ich bin mir halt auch nicht ganz so sicher. Bitte gebt auch an ob die betreffende Aufgabe richtig gelöst wurde, damit ich das abhaken kann Zur Aufgabe: Folgendes sei gegeben: die Menge M = {1,2,3,4,5} die Relation R = {(1,1),(2,2),(3,3),(1,2),(3,1),(3,2)} und eine weitere Relation S = {(1,1),(1,2),(1,4),(3,3),(5,3)} a) Überprüfe ob R reflexiv, transitiv oder symmetrisch ist b) Bestimmen Sie die reflexive Hülle S* von S c)Gib eine kleinstmögliche Relation über M an, die -reflexiv und symmetrisch, aber nicht transitv - symmetrisch und transitiv, aber nicht reflexiv Meine Ideen: zu a) R ist nicht reflexiv,da in der Menge M die Elemente 4,5 enthalten sind, jedoch in der Relation nicht (4,4) und (5,5) R ist nicht symmetrisch, da z.B. für das Paar (1,2) nicht dasPaar (2,1) enthalten ist R ist transitiv, da es die Defintion der Transitivität erfüllt (hatte hier jetzt keine Lust alle Paare einzutippen) zu b) Wenn ich das richtig verstanden habe muss ich einfach nur Paare hinzufügen: S* = { (1,1),(1,2),(1,4),((3,3),(5,3), (5,5), (2,3),(4,5), (3,5)} Sicher bin ich mir aber nicht. zu c) zum ersten Punkt: R = {(1,1),(2,2),(3,3),(4,4),(5,5)} zum zweiten Punkt: da habe ich noch keinen Lösungsansatz Danke für eure Hilfe
29.10.2010, 11:05	tmo	Auf diesen Beitrag antworten »
a) und b) sind richtig Zu c) Beim ersten Punkt hast du ein Fehler, diese Relation ist nämlich auch transitiv. D.h. du musst noch mind. 4 Elemente hinzufügen um die Transitivität zu verletzen, aber die Symmetrie beizubehalten. Der 2te Punkt ist übrigens trivial.
29.10.2010, 11:16	Estorias	Auf diesen Beitrag antworten »
Hallo und danke für deine Antwort, der 2te Punkt is tatsächlich trivial: Lösung: R={(1,1)} nicht wahr? beim ersten Punkt fällt mir echt nix ein, denn füge ich z.B. (2,1) und (1,2) hinzu dann ergibt sich auch 2R1 1R2 und 2R2 Was könnte ich denn einsetzen? Vielen Dank
29.10.2010, 13:01	tmo	Auf diesen Beitrag antworten »
Ich sagte doch auch du musst VIER Elemente hinzufügen, wie könntest du denn jetzt die Transitivität verletzen? Und zum 2ten Punkt. Das ist nicht die kleinstmögliche Relation mit den gewünschten Eigenschaften.
29.10.2010, 13:12	Estorias	Auf diesen Beitrag antworten »
Hallo, Warum stimmt denn (1,1) nicht? Es erfüllt doch a=b --> Symmetrie und a=b , b=c, a=c --> Transitivität und reflexiv ist es nicht, weil (2,2) etc. nicht Element von R ist. Und der erste Punkt mit der Transitivität ist mir immer noch schleierhaft. Auch wenn ich 4 Paare hinzufüge, ändert sich doch nix. Denn ich kann ja ein Paar z.B auch mehrmals nehmen um die Transitiviät zu zeigen oder nicht?
29.10.2010, 13:20	tmo	Auf diesen Beitrag antworten »
Ich habe nie behauptet, dass {(1,1)} die Eigenschaften nicht erfüllt, aber es ist eben nicht die kleinstemögliche solche Relation. Du kannst doch nicht Transitvität zeigen, indem du ein Beispiel gibst. Viel mehr musst du nur ein Gegenbeispiel geben, damit Transitivität nicht gilt. Und dazu reichen genau 2 Elemente (wegen der Symmetrie musst du halt die jeweiligen Gegenstücke auch noch mit reinnehmen, also 4).
Anzeige

29.10.2010, 13:37	Estorias	Auf diesen Beitrag antworten »
ok, also meinst du sicherlich die sogenannt "leere Relation". Da treffen ja Symmetrie und Transitivität sowie Nicht-Reflexivität zu. Und für das zweite fiele mir ein (2,5) (5,2) -> (5,5) (1,5) (5,1) -> (5,5) aber ( 2,5)(5,1) -> (2,1) nicht Element von R ginge das denn? Danke und MfG
29.10.2010, 13:41	tmo	Auf diesen Beitrag antworten »
Das letzte Beispiel ist nun richtig. (2,5) und (5,1) sind in R, wenn Transitivität gilt, also auch (2,1), was aber nicht der Fall ist. Und ja, ich meinste die leere Relation. Wenn man nicht draufkommt, kann man das auch "berechnen". Man betrachte einfach alle Relationen R, die die gewünschten Eigenschaften, haben und bringe sie zum Schnitt. Dann kann man zeigen, dass der Schnitt selbst wieder die gewünschten Eigenschaften hat. Also ist der Schnitt die kleinste solche Relation. Da aber {(1,1)} und {(2,2)} die gewünschten Eigenschaften erfüllen und schon leeren Schnitt haben, muss der Schnitt aller solchen Relationen auch die leere Menge sein.
29.10.2010, 13:49	Estorias	Auf diesen Beitrag antworten »
ok . Vielen Dank
29.10.2010, 21:42	Estorias	Auf diesen Beitrag antworten »
Hallo noch mal, Ich hab mir die Aufgabe 2 B noch mal angesehen, wo du meintest die sei richtig, ich aber glaube, dass sie nicht richtig gelöst ist. Grund: Wir hatten auf unseren Übungszettel einen "Hinweis" wie man die reflexive und transitive Hülle berechnet. Ich will das mal kurz wiedergeben und anschließend meine neue Lösung präsentieren. Also zunächst wird die Verkettung definiert: Für zwei Relationen R,S über M definieren wir die Verkettung durch: $\begin{eqnarray} RS = \left\{ \left(x,y\right)\|\exists z \in M mit \left(x,z \right)\in R, und \left( z,y\right)\in S \right\} \end{eqnarray}$ Dann wird $\begin{eqnarray} R^{°} = \left\{(x,x)\| x\in M\right\} \end{eqnarray}$ gesetzt und es wird für $\begin{eqnarray} n \geq 1 \end{eqnarray}$ definiert die n-malige Verkettung von R mit sich selbst : $\begin{eqnarray} R^{n} = RR^{n-1} \end{eqnarray}$ Die reflexive und transitive Hülle ist dann: $\begin{eqnarray} R^{} = \bigcup R^{n} mit. n\geq 0 \end{eqnarray}$ Das n>0 steht eigentlich unter dem Vereinigungssymbol, wußte aber nicht wie ich das mit dem Editor antstellen soll. So und nach dieser Definition habe ich dann die Aufgabe gelöst. $\begin{eqnarray} S^{°} = \left\{ (1,1),(2,2),(3,3),(4,4),(5,5)\right\} \end{eqnarray}$ Dann habe ich die Verkettung nach der Definition vorgenommen: $\begin{eqnarray} S^{1} = SS^{°} = \left\{ (1,1),(1,2)(1,4),(3,3)\right\} \end{eqnarray}$ $\begin{eqnarray} S^{2} = SS^{1} = \left\{ (1,1), (3,3)\right\} \end{eqnarray}$ $\begin{eqnarray} S^{3} = SS^{2} = \left\{ (1,1), (3,3)\right\} \end{eqnarray}$ Und schließlich die Vereinigung: $\begin{eqnarray} S^{} = \bigcup S^{n} [mit n=2] = \left\{ (1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(1,4)\right\} \end{eqnarray}$ Das n=2 steht wieder unter dem Vereinigungssymbol. Ja, das wäre nun die Lösung und die unterscheidet sich sehr von der anderen. Wie gesagt, es ist die reflexive und transitive Hülle von S gesucht. Habe ich die Definition falsch verstanden oder ein Fehler bei den Berechnungen gemacht??? Bitte um schnelle Hilfe. Danke
30.10.2010, 13:32	Estorias	Auf diesen Beitrag antworten »
keiner ne Idee?

Neue Frage »

Antworten »

Relationen + transitive Hülle

Verwandte Themen