Mengenlehre: Kleinste Äquivalenzrelation?

Neue Frage »

shooter99 Auf diesen Beitrag antworten »
Mengenlehre: Kleinste Äquivalenzrelation?
Hallo!

Ich verstehe folgende Relation nicht:

Sei R eine Relation über einer nichtleeren Menge A.

Die nachfolgend definierte Relation R' ist die kleinste R umfassende Äquivalenzrelation



Bei Xi und Xi+1 sind "i" und "i+1" Indizes.

Wieso ist das die kleinste Äquvalenzrelation die R umfasst??? Hilfe

Gruß
shooter
shooter99 Auf diesen Beitrag antworten »

Es würde mir schon sehr weiterhelfen, wenn mir jemand sagen könnte wie dieser Teil mit den hintereinander gereihten Existenzquantoren zu verstehen ist (in Bezug auf die Relation R')..

Wäre echt klasse wenn mir das jemand erklären könnte, da ich morgen leider schon eine Klausur darüber schreibe..

Gruß
shooter
Sanisani Auf diesen Beitrag antworten »

hm dieser beitrag existiert schon seit fast zwei jahren und keine einzige antwort gibts darauf? oO was für ein mathe forum
Kasiopaia Auf diesen Beitrag antworten »

naja, bei der sauchlecht lesbaren latexformel kein wunder...
SaniSani Auf diesen Beitrag antworten »

ich machs mal hübscher:
R'=\{(x,y)|\exists n\in N \exists x_{1}... \exists x_{n} \in A: x=x_{1} \wedge y=x_{n} \wedge (x_{i}=x_{i+1} \vee x_{i}Rx_{i+1} \vee x_{i+1}Rx_{i})\}
SaniSani Auf diesen Beitrag antworten »

ups ich meine:

 
 
Abakus Auf diesen Beitrag antworten »

Du zeigst schrittweise:

(1)

(2) ist eine Äquivalenzrelation

(3) ist die kleinste Äquivalenzrelation, die umfasst

Grüße Abakus smile
papahuhn Auf diesen Beitrag antworten »

Zitat:
Original von SaniSani
ups ich meine:



Dann mach ich mal einen Anfang. Sei . Dann belegen wir für die Existenzquantoren folgendermaßen: und es gilt die Disjunktion in der Bedingung, weil . D.h. wir haben schonmal .

Danach musst du noch nachweisen, dass R' eine Äquivalenzrelation ist, und dass sie sogar die kleinste ist. Die Bedingung innerhalb der Mengendefinition ist im Übrigen keine FO-Formel. Wenn ich das richtig in Erinnerung habe, ist das nichtmal Second-Order-Logic.
SaniSani Auf diesen Beitrag antworten »

Das Problem ist nicht der Beweis, denn den habe ich hier in meinem Buch schwarz auf weiß. Ich hätte es erwähnen sollen, aber ich habe eherlich nicht damit gerechnet, dass wer antwortet.

Das eigentliche Problem:

Hier steht zum Beispiel, als Nachweis der Reflexivität- "R' ist reflexiv, da alle und gilt: also xR'x "

Ich verstehe nicht, warum das die Reflexivität von R'nachweist. Wenn , warum gibt es die dann überhaupt, wenn sie eh das selbe sind.

Es ist sicher nur ein Knoten in meinen Gedanken verwirrt , aber ich verstehe den ganzen Sinn dieser Relation R' nicht. unglücklich

R' ist die Relation mit der Eigenschaft, dass ich mir ein beliebliges(?) n suche, oder dass ich ein exitierendes(?) n finde, dass die Anzahl der angibt, die dann irgendwie doch () das selbe sind. *Knoten-in-Gedanken-hab*

Vlt. würde es helfen, wenn mir jemand aufschreiben könnte, wie man diese Relation lesen und verstehen soll.

Was ich bis jetzt denke zu wissen ist:

x steht mir y in Relation R', wenn ein n existiert, das die Anzahl der angibt.. Das erste x ist unser x und das lezte x ist unser y. Was mit den x dazwischen ist, weiß ich nicht.... und wenn n=2 ist, dann verstehe ich den ganzen Sinn von nicht,dann kann man doch gleich (x,y) x und y sein lassen.

.... Irgenwie komme ich gerade ziemlich dumm vor. Ich muss doch was übersehen haben. traurig

Gebt mir ne Idee.
SaniSani Auf diesen Beitrag antworten »

Unabhängig davon, ist der Schnitt, aller ÄR über A die kleinste ÄR über A. Wenn ich mir jetzt alle ÄR aus A schnappe, die auch die Relation R enthalten, und dann erst den Schnitt bilde, ist das dann die kleine R umfassende ÄR in A.
Warum muss man es immer so kompliziert machen?
Aber dieser Gedanke hilft mir bei meinem Problem mit der R' Formel nicht weiter, oder? ^^

Oute ich mich jetzt, wenn ich frage, ob ihr es idiotensicher mit der Erklärung Lehrer machen könnt? FO-Formel? Second-Order-Logic?.... Bin doch eine Ersti Augenzwinkern
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von SaniSani
Das eigentliche Problem:

Hier steht zum Beispiel, als Nachweis der Reflexivität- "R' ist reflexiv, da alle und gilt: also xR'x "

Ich verstehe nicht, warum das die Reflexivität von R'nachweist. Wenn , warum gibt es die dann überhaupt, wenn sie eh das selbe sind.


Zu zeigen ist für alle . Nun existiert ein n (nämlich n:=2) und es existieren , die die Bedingungen in der Mengendefinition erfüllen (nämlich ). Daraus folgt die Reflexivität.

Es ist noch die Symmetrie und Transitivität nachzuweisen. Dafür brauchst du verschiedene 's.


Zitat:
Es ist sicher nur ein Knoten in meinen Gedanken verwirrt , aber ich verstehe den ganzen Sinn dieser Relation R' nicht. unglücklich

R' ist die Relation mit der Eigenschaft, dass ich mir ein beliebliges(?) n suche, oder dass ich ein exitierendes(?) n finde, dass die Anzahl der angibt, die dann irgendwie doch () das selbe sind. *Knoten-in-Gedanken-hab*

Vlt. würde es helfen, wenn mir jemand aufschreiben könnte, wie man diese Relation lesen und verstehen soll.

Was ich bis jetzt denke zu wissen ist:

x steht mir y in Relation R', wenn ein n existiert, das die Anzahl der angibt.. Das erste x ist unser x und das lezte x ist unser y. Was mit den x dazwischen ist, weiß ich nicht.... und wenn n=2 ist, dann verstehe ich den ganzen Sinn von nicht,dann kann man doch gleich (x,y) x und y sein lassen.


n ist nicht für alle (x, y) gleich 2, sondern kann größer sein. Am Besten kannst du dir das an einem Beispiel klarmachen:



Wie sieht nun aus und wieso ?


Zitat:
Unabhängig davon, ist der Schnitt, aller ÄR über A die kleinste ÄR über A. Wenn ich mir jetzt alle ÄR aus A schnappe, die auch die Relation R enthalten, und dann erst den Schnitt bilde, ist das dann die kleine R umfassende ÄR in A.
Warum muss man es immer so kompliziert machen?


Du kannst natürlich auch gerne alle Äquivalenzrelationen, die R umfassen, ermitteln, und dann den Durchschnitt bilden.

Bei einer 4-elementigen Basismenge A mag das gut gehen, bei größeren Mengen A stösst du aber schnell an Grenzen.

Grüße Abakus smile
SaniSani Auf diesen Beitrag antworten »

Danke Abakus ^^ ich habe folgende Antwort bekommen, von einem Lehrer aus Bayern smile die hat mir weitergeholfe, ^^ ich poste sie mal hier, damit sie auch anderen weiter helfen kann Augenzwinkern

Zitat:

diese Definition von R' versucht, ausgehend von R die nochfehlenden Eigenschaften einer Äquivalenzrelation zu bilden.
Ich beginne mal mit dem kompliziertesten, der Transitivität, denn da wird hoffentlich klar, wie diese Definition aufgebaut ist.
Sei also (x,z) $ \in $ R und (z,y) $ \in $ R. Ist jetzt (x,y) $ \not\in $ R, dann muss es trotzdem in R' hinzugefügt werden, um die benötigte Transitivität zu erhalten. Nun kann es aber auch sein, dass eine entsprechende Verkettung mehrere Zwischenstufen enthält: Sind z.B. $ (x,z_1), (z_1,z_2), (z_2,z_3),(z_3,y) $ in R, dann muss auch (x,y) in R' liegen. Die in der Beschreibung von R' genannten $ x_i $ sind gerade die Elemente einer solchen "Transitivitätskette".
In Worten formuliert besagt die Definition von R':
xR'y genau dann, wenn sich x und y durch eine Kette endlicher Länge verbinden lassen, wobei für zwei benachbarte Glieder a und b eine der folgenden Bedingungen gilt:
1.) a=b
2.) aRb
3.) bRa

Der Beweis der Reflexivität läuft dann also folgendermaßen: mit x $ \in $ A bilden wir die Kette x $ \to $ x. Diese ist zulässig, denn alle benachbarten Glieder erfüllen 1.). Anfangspunkt ist x, Endpunkt ist x also ist (x,x) $ \in $ R'.
Die Transitivität von R' ergibt sich, da man zwei bestehende Ketten über 1.) aneinanderhängen kann, die Symmetrie bekommt man mit Hilfe von 2.) und 3.) bewiesen.

Was eine härtere Nuss sein dürfte ist, die Minimalität von R' (...die kleinste ÄR...) zu beweisen, aber das dürfte bei Dir wohl auch noch eher im Hintergrund stehen...
*zitat-Ende*

Vielen Dank an Piet für diese Antwort
Abakus Auf diesen Beitrag antworten »

Die reflexiv-transitive Hülle findest du auch bei Wiki erklärt.

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »