Mengenlehre: Kleinste Äquivalenzrelation? |
06.12.2004, 01:55 | shooter99 | Auf diesen Beitrag antworten » | ||||||
Mengenlehre: Kleinste Äquivalenzrelation? 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??? Gruß shooter |
||||||||
06.12.2004, 13:08 | 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 |
||||||||
10.10.2006, 10:05 | 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 |
||||||||
10.10.2006, 10:34 | Kasiopaia | Auf diesen Beitrag antworten » | ||||||
naja, bei der sauchlecht lesbaren latexformel kein wunder... |
||||||||
10.10.2006, 12:16 | 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})\} |
||||||||
10.10.2006, 12:18 | SaniSani | Auf diesen Beitrag antworten » | ||||||
ups ich meine: |
||||||||
Anzeige | ||||||||
|
||||||||
10.10.2006, 19:53 | Abakus | Auf diesen Beitrag antworten » | ||||||
Du zeigst schrittweise: (1) (2) ist eine Äquivalenzrelation (3) ist die kleinste Äquivalenzrelation, die umfasst Grüße Abakus |
||||||||
10.10.2006, 20:04 | papahuhn | Auf diesen Beitrag antworten » | ||||||
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. |
||||||||
11.10.2006, 10:07 | 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 , aber ich verstehe den ganzen Sinn dieser Relation R' nicht. 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. Gebt mir ne Idee. |
||||||||
11.10.2006, 10:17 | 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 machen könnt? FO-Formel? Second-Order-Logic?.... Bin doch eine Ersti |
||||||||
11.10.2006, 21:24 | Abakus | Auf diesen Beitrag antworten » | ||||||
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.
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 ?
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 |
||||||||
12.10.2006, 12:48 | SaniSani | Auf diesen Beitrag antworten » | ||||||
Danke Abakus ^^ ich habe folgende Antwort bekommen, von einem Lehrer aus Bayern die hat mir weitergeholfe, ^^ ich poste sie mal hier, damit sie auch anderen weiter helfen kann 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 |
||||||||
12.10.2006, 20:21 | Abakus | Auf diesen Beitrag antworten » | ||||||
Die reflexiv-transitive Hülle findest du auch bei Wiki erklärt. Grüße Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|