Relationseigenschaften nachweisen

03.11.2009, 10:10

RS

Auf diesen Beitrag antworten »

Relationseigenschaften nachweisen

Hi, habe mich an folgenden aufgaben versucht und würde gerne wissen obs irchitg ist (kam mir so einfach vor...).

Sei X Menge und ~ Relation auf X

Eine Relation ~r wie folgt: $\begin{eqnarray*} x\sim_r y : \Leftrightarrow x \sim y \vee x = y \end{eqnarray*}$ . Zeigen Sie: ~r
ist reflexiv.

Eine Relation ~s wie folgt: $\begin{eqnarray*} x \sim_s y :\Leftrightarrow x\sim y \vee y\sim x \end{eqnarray*}$ Zeigen sie ~s
ist symmetrisch.

Eine Relation ~t wie folgt: $\begin{eqnarray*} x \sim_t y :\exists n\in\mathbb N, x_1,...x_n \in X: x=x_1,x_1\sim x_2,x_2\sim x_3,...,x_{n-1}\sim x_n,x_n=y \end{eqnarray*}$ Zeigen Sie: ~t ist transitiv.

zu 1.

Sei x aus X, dann folgt $\begin{eqnarray*} x=x \end{eqnarray*}$ und daraus $\begin{eqnarray*} x\sim_r x \end{eqnarray*}$ .

zu 2.

Seien x,y aus X. Die Aussagen für $\begin{eqnarray*} x\sim_s y \end{eqnarray*}$ lassen sich auch vertauschen, sodass folgt:

$\begin{eqnarray*} y\sim x\vee x\sim y \end{eqnarray*}$ . Daraus folgt $\begin{eqnarray*} x\sim_s y\Leftrightarrow y\sim_s x \end{eqnarray*}$

zu 3.

Seien x,y,z aus X

Aus x~y folgt:

$\begin{eqnarray*} x=x_1,x_1\sim x_2,x_2\sim x_3,...,x_{n-1}\sim x_n,x_n=y \end{eqnarray*}$

Aus y~z folgt:

$\begin{eqnarray*} y=y_1,y_1\sim y_2,y_2\sim y_3,...,y_{n-1}\sim y_n,y_n=z \end{eqnarray*}$

$\begin{eqnarray*} x=x_1,x_1\sim x_2,x_2\sim x_3,...,x_{n-1}\sim x_n,x_n=y=y_1,y_1\sim y_2,y_2\sim y_3,...,y_{n-1}\sim y_n,y_n=z \end{eqnarray*}$

$\begin{eqnarray*} x=z \end{eqnarray*}$ .

Alles soweit richtig?

03.11.2009, 10:28

Jacques

Auf diesen Beitrag antworten »

Hallo,

Inhaltlich ist es richtig, aber die Lösung zu 3. ist (zumindest formal) nicht korrekt:

Du darfst im zweiten Fall nicht wieder die Variable n nehmen, denn die hast Du schon bei x als Variable für „eine beliebige natürliche Zahl“ genommen. Und Du müsstest bei x1, x2, ... und y1, y2 noch ein „existiert“ davorschreiben, denn das sind ja keine konkret bestimmten Folgenglieder, sondern eine Anzahl von gewissen Elementen.

03.11.2009, 11:35

RS

Auf diesen Beitrag antworten »

Zitat:

Original von Jacques
Hallo,

Inhaltlich ist es richtig, aber die Lösung zu 3. ist (zumindest formal) nicht korrekt:

Du darfst im zweiten Fall nicht wieder die Variable n nehmen, denn die hast Du schon bei x als Variable für „eine beliebige natürliche Zahl“ genommen. Und Du müsstest bei x1, x2, ... und y1, y2 noch ein „existiert“ davorschreiben, denn das sind ja keine konkret bestimmten Folgenglieder, sondern eine Anzahl von gewissen Elementen.

Also zu 3.

Seien x,y,z aus X

Aus x~y und folgt:

$\begin{eqnarray*} \exists n\in \mathbb N,\exists x_1,...,x_n\in X : x=x_1,x_1\sim x_2,x_2\sim x_3,...,x_{n-1}\sim x_n,x_n=y \end{eqnarray*}$

Aus y~z folgt:

$\begin{eqnarray*} \exists n'\in \mathbb N, \exists y_1,...,y_{n'}\in X: y=y_1,y_1\sim y_2,y_2\sim y_3,...,y_{n'-1}\sim y_{n'},y_{n'}=z \end{eqnarray*}$

$\begin{eqnarray*} x=x_1,x_1\sim x_2,x_2\sim x_3,...,x_{n-1}\sim x_n,x_n=y=y_1,y_1\sim y_2,y_2\sim y_3,...,y_{n'-1}\sim y_{n'},y_{n'}=z \end{eqnarray*}$

$\begin{eqnarray*} x=z \end{eqnarray*}$ .

03.11.2009, 12:46

Jacques

Auf diesen Beitrag antworten »

OK.

Freude

03.11.2009, 13:05

RS

Auf diesen Beitrag antworten »

danke... Sry dass ich hier so banale dinge einstelle, aber nach den letzten übungsserien, konnte ich iwie nicht glauben, dass auch mal so "einfache" dinge dabei sind^^. Sicher ist sicher...

04.11.2009, 18:43

RS

Auf diesen Beitrag antworten »

hab dazu noch ne zweite teilaufgabe wo ich ne idee habe aber nicht weiß wie ichs mathematisch darstelle.

Seien $\begin{eqnarray*} R_r,R_s,R_t \end{eqnarray*}$ die den eben definierten rel. zugrundeliegenden teilmengen von
X x X.

z.Z. ist: Die Menge Rr ist die kleinste Teilmenge von X x X, die R enthält
und eine refl. Relation ist. Die Menge Rs ist die kleinste Teilmenge von X x X, die R
enth¨alt und eine symmetrische Relation ist. Die Menge Rt ist die kleinste Teilmenge von X x X, die R enthält und eine transitive Relation ist.

"kleinste" ist auf die Inklusion bezogen.

muss ich jeweils zeigen ,dass die anderen beiden Teilmengen (relationen) nicht reflexiv bzw. symmetrisch bzw. transitiv sind? wo liegt hier der ansatz?

Anzeige

04.11.2009, 21:16

ankasztaj

Auf diesen Beitrag antworten »

RE: Relationseigenschaften nachweisen
ich habe so angefangen:
man denkt sich eine menge M aus, die in X*X enthalten ist, die R enthält und die Rr, Rs und Rt enthält. natürlich alles nacheinander. wenn du gezeigt hast dass es so ne menge gibt wo z.b. Rr die teilmenge ist, dann muss Rr die kleinste teilmenge von X*X sein.

04.11.2009, 22:39

RS

Auf diesen Beitrag antworten »

aber ist R nicht eigentlich schon so eine gesuchte menge? ist teilmenge X x X und enthält alle Ri (und sich selbst natürlich auch)...

Selbst wenn ich jetzt mal deinen ansatz weiterführe, so hab ich doch letztlich nur weil Rr ne teilmenge ist, nicht bewiesen dass es die kleinste ist. ?!

05.11.2009, 07:17

ankasztaj

Auf diesen Beitrag antworten »

R ist nicht die gesuchte Menge. Die gesuchte Menge muss doch R enthalten, in X*X sein und reflexiv sein.
DIe Idee lautet grundsätzlich so: Wir suchen eine Menge M mit den eigenschaften, Teilmenge von X*X, R ist drin enthalten und M ist reflektiv. Dann schauen wir ob Rr drin enthalten ist. Wenn Rr noch Teilmenge von M sein sollte dann muss Rr dann die kleinste Menge mit den Eigenschaften sein.

Ich kann es schwer erklären unglücklich

unglücklich

05.11.2009, 08:33

Mazze

Auf diesen Beitrag antworten »

Das was ankasztaj hingeschrieben hat ist die richtige Idee. Wenn man bei Mengen "das Kleinste" meint dann ist das folgender Sachverhalt, am Beispiel Rr. Rr ist die kleinste reflexive Relation wenn gilt :

$\begin{eqnarray*} \forall R \subset X \times X ~ \text{mit R ist reflexiv} \Rightarrow Rr \subset R \end{eqnarray*}$

Zum Verständnis: Man kann eine partielle Ordnungsrelation auf Mengen wie folgt definieren. Seien dazu A und B zwei Mengen, dann ist A kleiner als B wenn $\begin{eqnarray*} A \subset B \end{eqnarray*}$ gilt. Hast Du nun das kartesische Produkt $\begin{eqnarray*} X \times X \end{eqnarray*}$ dann ist die kleinste reflexive Relation gerade die reflexive Relation, die eine Teilmenge aller reflexiven Relationen ist. Zum Beweis nimmst Du dir also eine bel. Reflexive Relation R her, und zeigst das $\begin{eqnarray*} Rr \subset R \end{eqnarray*}$ gilt.

05.11.2009, 08:54

RS

Auf diesen Beitrag antworten »

Jetzt mal ohne zu überprüfen welche von Rs Rt reflexiv ist. ich muss also zeigen dass Rr ne echte teilmenge von Rs bzw Rt ist?

05.11.2009, 09:09

Mazze

Auf diesen Beitrag antworten »

Naja, Du musst das natürlich auf deine Aufgabe anpassen. Du hast zwei Sachen zu zeigen :

$\begin{eqnarray*} R \subset R_r \end{eqnarray*}$ (trivial)

Und Du musst zeigen dass wenn $\begin{eqnarray*} R' \end{eqnarray*}$ eine reflexive Relation ist und $\begin{eqnarray*} R \subset R' \end{eqnarray*}$ gilt, dass dann auch $\begin{eqnarray*} R_r \subset R' \end{eqnarray*}$ ist. Analog für die anderen beiden Fälle.

05.11.2009, 09:19

RS

Auf diesen Beitrag antworten »

Aber nur weil ich zeige Rr ist eine echte Teilmenge von R' (was bitte ist R', eine neu definierte Relation?),Rs eine echte Teilmenge von R', usw. habe ich doch nicht gezeigt, dass beispielsweise Rs nicht die kleinere reflexive teilmenge als Rr ist...

Verstehe nicht was R' in der Aufgabe soll. Warum reicht es nicht zu zeigen, dass Rr eine echte Teilmenge von Rs und Rt ist. Weil R ja letztlich durch diese 3 Teilmengen definiert ist...?

05.11.2009, 09:28

Mazze

Auf diesen Beitrag antworten »

Zitat:

Weil R ja letztlich durch diese 3 Teilmengen definiert ist...?

Ist sie doch garnicht. R ist irgend eine Relation. Mit Hilfe dieser Relation R definieren wir eine Relation $\begin{eqnarray*} R_r \end{eqnarray*}$ , nämlich :

$\begin{eqnarray*} x\sim_r y : \Leftrightarrow x \sim y \vee x = y \end{eqnarray*}$ .

In Worten heisst die Relation : (x,y) ist Element der Relation $\begin{eqnarray*} R_r \end{eqnarray*}$ wenn (x,y) in der Relation R enthalten ist, oder wenn x = y ist. Das heisst, nicht $\begin{eqnarray*} R_r \subset R \end{eqnarray*}$ , sondern $\begin{eqnarray*} R \subset R_r \end{eqnarray*}$ . Dieses R' ist eine allgemeine reflexive Relation die R enthält. Du stolperst hier vielleicht über die Formulierung. Wenn man den Satz hat :

"Die Menge A ist diejenige Menge die B enthält", dann heisst das $\begin{eqnarray*} B \subset A \end{eqnarray*}$ . Du sagts ja auch bei

"Das ist das Glas welches Wasser enthält", das dass Wasser im Glas ist und nicht das Glas im Wasser.

05.11.2009, 10:05

RS

Auf diesen Beitrag antworten »

ok aufgaben missverständnis^^

R ist echte Teilmenge von Rr, da es (x,y)€ Rr gibt sodass (x,y) nicht in R, nämlich für x=y oder. Alle anderen tupel sind aufgrund x~y element beider R.

oder?

Sei R' eine reflexive Relation und R echte Teilmenge von R'. Wie zeige ich jetzt genau dass Rr auch Teilmenge von R' ist?

05.11.2009, 13:32

RS

Auf diesen Beitrag antworten »

Ich fass das jetzt nochmal zusammen was zu tun ist (bzw. wie ich es verstanden habe^^).

Insgesamt zu Zeigen:

Für $\begin{eqnarray*} R_r\subset X\times X \end{eqnarray*}$ gibt es kein R' mit: R' ist reflexiv, R' ist Obermenge von R, $\begin{eqnarray*} R' \subset X\times X \end{eqnarray*}$ und R' ist Teilmenge von Rr.

Zuerst zu zeigen:

$\begin{eqnarray*} R\subset R_r \end{eqnarray*}$

D.h., zu zeigen: $\begin{eqnarray*} \exists (a,b)\in X\times X : (a,b)\in R_r, (a,b)\notin R \end{eqnarray*}$

Aus $\begin{eqnarray*} a\sim_r b \end{eqnarray*}$ folgt:

$\begin{eqnarray*} a\sim b \vee a=b \end{eqnarray*}$ . Daraus folgt (a,a) und (b,b) in Rr, aber nicht in R.

Sei $\begin{eqnarray*} R'\subset X\times X, R' \text{~ist reflexiv}, R\subset R' \end{eqnarray*}$

Zu zeigen: $\begin{eqnarray*} \neg (\exists (a,b)\in X\times X : (a,b)\in R_r, (a,b) \notin R') \end{eqnarray*}$ . Sprich zu zeigen, dass $\begin{eqnarray*} \neg (R'\subset R_r) \end{eqnarray*}$ .

So ist das bis hierhin richtig?

Aus der Refl. von R' folgt, dass $\begin{eqnarray*} (a,a), (b,b)\in R' \end{eqnarray*}$ , aus $\begin{eqnarray*} R\subset R' \end{eqnarray*}$ folgt, $\begin{eqnarray*} x\sim y\rightarrow (x,y)\in R' \end{eqnarray*}$ und damit $\begin{eqnarray*} (a,b)\in R' \end{eqnarray*}$

So, dass ist ja nun genau die Menge aller Tupel die auch in Rr enthalten sind. Sprich es gibt nur die Möglichkeit R'=Rr oder halt $\begin{eqnarray*} R_r\subset R' \end{eqnarray*}$ . (wenn noch weitere Tupel zu R' hinzukämen.)

Das widerlegt

Zitat:

$\begin{eqnarray*} \exists (a,b)\in X\times X : (a,b)\in R_r, (a,b) \notin R' \end{eqnarray*}$ | $\begin{eqnarray*} R'\subset R_r \end{eqnarray*}$ .

wie schauts aus^^?

05.11.2009, 14:18

Mazze

Auf diesen Beitrag antworten »

Zitat:

Für $\begin{eqnarray*} R_r\subset X\times X \end{eqnarray*}$ gibt es kein R' mit: R' ist reflexiv, R' ist Obermenge von R, $\begin{eqnarray*} R' \subset X\times X \end{eqnarray*}$ und R' ist Teilmenge von Rr.

Wow

Tanzen

. Anstatt den einfachen Weg zu gehen und zu zeigen das $\begin{eqnarray*} R_r \subset R' \end{eqnarray*}$ für alle reflexiven $\begin{eqnarray*} R' \end{eqnarray*}$ mit $\begin{eqnarray*} R \subset R' \end{eqnarray*}$ gilt ...

Zitat:

Zuerst zu zeigen: $\begin{eqnarray*} R\subset R_r \end{eqnarray*}$ D.h., zu zeigen: $\begin{eqnarray*} \exists (a,b)\in X\times X : (a,b)\in R_r, (a,b)\notin R \end{eqnarray*}$

Naja, das ist falsch. Wenn Du zeigen willst das $\begin{eqnarray*} R \subset R_r \end{eqnarray*}$ gilt, dann zeigst Du einfach

$\begin{eqnarray*} x \in R \Rightarrow x \in R_r \end{eqnarray*}$

Das ist ein Einzeiler :

Sei $\begin{eqnarray*} (x,y) \in R \end{eqnarray*}$ dann ist nach Definition $\begin{eqnarray*} (x,y) \in R_r \end{eqnarray*}$ . Damit ist $\begin{eqnarray*} R \subset R_r \end{eqnarray*}$ . Fertig. Das könnte man glatt unter "offensichtlich" laufen lassen.

Zweitens :

Zitat:

$\begin{eqnarray*} \neg (R'\subset R_r) \end{eqnarray*}$ .

Daraus folgt nicht das $\begin{eqnarray*} R_r \end{eqnarray*}$ das kleinste ist. Daraus folgt nur das die Teilmengenbeziehung nicht gilt. Das heisst aber noch lange nicht das dann auch $\begin{eqnarray*} R_r \subset R' \end{eqnarray*}$ ist. Nein, du zeigst genau das was ich dir gesagt habe :

Zitat:

wenn $\begin{eqnarray*} R' \end{eqnarray*}$ eine reflexive Relation ist und $\begin{eqnarray*} R \subset R' \end{eqnarray*}$ gilt, dass dann auch $\begin{eqnarray*} R_r \subset R' \end{eqnarray*}$

Sei also R' reflexiv und $\begin{eqnarray*} R \subset R' \end{eqnarray*}$ . Dann ist zu zeigen das auch $\begin{eqnarray*} R_r \subset R' \end{eqnarray*}$ ist. Sei also $\begin{eqnarray*} (x,y) \in R_r \end{eqnarray*}$ ...

05.11.2009, 14:41

RS

Auf diesen Beitrag antworten »

Ich muss also zeigen $\begin{eqnarray*} x\in R_r\Rightarrow x\in R' \end{eqnarray*}$ .

Sei $\begin{eqnarray*} (x,y) \in R_r \end{eqnarray*}$ , dann gilt: $\begin{eqnarray*} (x,y)\in R \vee x=y \end{eqnarray*}$ .
Aus $\begin{eqnarray*} R\subset R' \end{eqnarray*}$ folgt $\begin{eqnarray*} (x,y)\in R \Rightarrow (x,y)\in R' \end{eqnarray*}$
Und aus der Reflx. von R' und der Eigenschaft von Rr folgt wenn x=y $\begin{eqnarray*} (x,x)\in R_r \Rightarrow (x,x)\in R' \end{eqnarray*}$

so richtig?

05.11.2009, 14:54

Mazze

Auf diesen Beitrag antworten »

Zitat:

Ich muss also zeigen $\begin{eqnarray*} x\in R_r\Rightarrow x\in R' \end{eqnarray*}$ .

Ganz genau!

Zitat:

Sei $\begin{eqnarray*} (x,y) \in R_r \end{eqnarray*}$ , dann gilt: $\begin{eqnarray*} (x,y)\in R \vee x=y \end{eqnarray*}$ .

Das seh ich ein. Ansonsten wirds wieder etwas undurchsichtig. Es gibt zwei Fälle zu betrachten

x = y :

Wir haben also x = y, dann ist $\begin{eqnarray*} (x,x) \in R_r \end{eqnarray*}$ da $\begin{eqnarray*} R_r \end{eqnarray*}$ reflexiv ist. Wir wissen aber auch das $\begin{eqnarray*} R' \end{eqnarray*}$ reflexiv ist, also ist auch $\begin{eqnarray*} (x,x) \in R' \end{eqnarray*}$ . Das ist der erste Teil, der zweite ist :

x != y :

Sei also $\begin{eqnarray*} (x,y) \in R_r \end{eqnarray*}$ und x ungleich y. Dann ist nach Definition von $\begin{eqnarray*} R_r \end{eqnarray*}$ also $\begin{eqnarray*} (x,y) \in R \end{eqnarray*}$ . Nun ist aber R' gerade so gewählt das $\begin{eqnarray*} R \subset R' \end{eqnarray*}$ gilt. Damit ist natürlich sofort $\begin{eqnarray*} (x,y) \in R' \end{eqnarray*}$
Und damit ist die Teilmengenbeziehung $\begin{eqnarray*} R_r \subset R' \end{eqnarray*}$ gezeigt. Die andern 2 Relationen sollten ganz ähnlich funktionieren.

05.11.2009, 14:58

RS

Auf diesen Beitrag antworten »

Zitat:

Aus $\begin{eqnarray*} R\subset R' \end{eqnarray*}$ folgt $\begin{eqnarray*} (x,y)\in R \Rightarrow (x,y)\in R' \end{eqnarray*}$

bis auf die (für mich offensichtliche) bedingung x!=y, sagt doch, adss im prinzip den zweiten fall aus?

Sprich aus $\begin{eqnarray*} (x,y)\in R_r \end{eqnarray*}$ folgt (den anderen Fall jetzt mal weggelassen). $\begin{eqnarray*} (x,y)\in R \end{eqnarray*}$ . Ist vielleicht ungünstig aufgeschrieben aber ich meine, dass aus der Inklusion RcR' folgt, dass eben (x,y)€R --> ...R'

und noch ne frage:

Zitat:

wenn x=y $\begin{eqnarray*} (x,x)\in R_r \Rightarrow (x,x)\in R' \end{eqnarray*}$

Ich muss doch nicht mal mit der reflexivität von Rr argumentieren oder? aus x=y folgt doch x~r x oder?

05.11.2009, 15:14

Mazze

Auf diesen Beitrag antworten »

Zitat:

Aus $\begin{eqnarray*} R\subset R' \end{eqnarray*}$ folgt $\begin{eqnarray*} (x,y)\in R \Rightarrow (x,y)\in R' \end{eqnarray*}$

Das ist in der Tat ungünstig aufgeschrieben. Dies ist zwar richtig, aber Du hättest ruhig sagen können das Du die Definition von $\begin{eqnarray*} R_r \end{eqnarray*}$ benutzt hast. Vollständig hätte es heissen müssen :

Aus $\begin{eqnarray*} R \subset R' \end{eqnarray*}$ und der Definition von $\begin{eqnarray*} R_r \end{eqnarray*}$ folgt $\begin{eqnarray*} (x,y) \in R \end{eqnarray*}$ .

Zitat:

Ich muss doch nicht mal mit der reflexivität von Rr argumentieren oder? aus x=y folgt doch x~r x oder?

Die Sache ist doch die. Wir nehmen an $\begin{eqnarray*} (x,y) \in R_r \end{eqnarray*}$ und wollen zeigen das dann auch $\begin{eqnarray*} (x,y) \in R' \end{eqnarray*}$ ist. Jetzt schauen wir uns die Definition von $\begin{eqnarray*} R_r \end{eqnarray*}$ an. Wenn (x,y) da drin liegt ist entweder $\begin{eqnarray*} (x,y) \in R \end{eqnarray*}$ oder $\begin{eqnarray*} x = y \end{eqnarray*}$ . Das gibt uns zwei Fälle die zu untersuchen sind Augenzwinkern

Augenzwinkern

.

05.11.2009, 15:16

RS

Auf diesen Beitrag antworten »

Ja das ist mir schon klar... Geht nur um ne kleinigkeit, aber ist im prinzip egal...

Danke dir erstmal!

05.11.2009, 17:41

Grüner

Auf diesen Beitrag antworten »

Würde es nicht reichen zu sagen, dass man annimmt, dass $\begin{eqnarray*} R_r \end{eqnarray*}$ nicht die KLEINSTE Teilmenge ist die reflexiv ist und R enthält. Man könnte also ein Zahlentupel herausnehmen und hätte eine kleinere. Dies wäre aber ein Widerspruch, da das Tupel entweder aus R ist (womit R nicht mehr vollständig enthalten wäre) oder ein Tupel der Form (x,x) womit $\begin{eqnarray*} R_r \end{eqnarray*}$ allerdings nicht mehr reflexiv wäre. also ist $\begin{eqnarray*} R_r \end{eqnarray*}$ kleinste reflexive Teilmenge von X x X die R enthält?! Dass $\begin{eqnarray*} R_r \end{eqnarray*}$ reflexiv ist und R enthält wurde ja schon in der ersten Aufgabe gezeigt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »