Unendlichkeit

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Unendlichkeit

Beitrag von Ankou » 31. Aug 2011 11:00

Ich denke es hat sich beim erneuten lesen der Aufgabenstellung eine halbwegs(oder viertelwegs) zufriedenstellende Erklärung für mich ergeben bezüglich der Definition eines Pfades als Sequenz von Knoten <x1,x2,...,xn>. Von mir aus kann das hier auch wieder entfernt werden oder auch nicht, mir egal.
Hi,
mal sehen ob jemand Licht in dieses dunkle und von mir verhasste Thema bringen kann und mir den Begriff der Unendlichkeit mal so erklären kann, dass ich nicht immer das Gefühl habe, dass er gerade so interpretiert wird wie es uns passt.
Ich habe mir gerade die Lösung zur Übung 13 G2 angeschaut und muss sagen, dass ich diesen Gedanken durchaus hatte, ihn aber schlichtweg verworfen habe und hier die Begründung:
In anderen Kompaktheitsbeweisen war die Lösung zu sagen, \(\varphi\) stellt sicher dass x(Anzahl der Elemente oder sonstwas, z.B. auch die Länge des Pfades) > n. Die Vereinigung aller phi stellt damit sicher, dass x > alle n und somit unendlich.
Nun haben wir hier: \(\varphi\) stellt sicher, dass kein Pfad der Länge n existiert. Eigentlich sollte die Aussage \(\varphi\) stellt sicher, dass ein existierender Pfad kleiner n oder größer n identisch sein. Sprich in der Vereinigung aller n sollte wieder ein Pfad zugelassen sein, der größer ist als alle n, also ein unendlicher Pfad.
Das lässt sich für einen Graphen auch durchaus konstruieren: V sei eine X-beliebige unendliche Knotenmenge und E = V x V verbindet schlichtweg alle Knoten.
Klar nehme ich noch 2 spezifische Knoten raus, ich wüsste aber nicht wieso bei einer unendlichen Knotenmenge zwischen 2 Knoten nicht auch unendlich viele Knoten liegen können?

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Unendlichkeit

Beitrag von fscheepy » 31. Aug 2011 12:31

Ich verstehe das ganze Thema auch nicht so recht. Die Lösungen und Erklärungen der Tutoren konnte ich teilweise (nach mehrmaligem durchlesen bzw. erklären) mehr oder weniger nachvollziehen, auch wenn ich hinter den Lösungen nie ein festes Schema erkennen konnte (es erschien mir immer alles ein bisschen willkürlich und schwammig: "Wir nehmen an, dass es dasunddas gibt, dann nehmen wir hier etwas unerfüllbares dazu, dadurch ist die ganze Formel unerfüllbar, also haben wir einen Widerspruch qed."). Warum muss denn z.B. bei der 13. Übung, G2 das Gamma_unendlich erfüllbar sein? Man nimmt eine erfüllbare Formel und nimmt etwas unerfüllbares dazu, was die ganze Formelmenge unerfüllbar macht. Wo liegt da der Widerspruch?

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Unendlichkeit

Beitrag von Ankou » 31. Aug 2011 13:12

Warum muss denn z.B. bei der 13. Übung, G2 das Gamma_unendlich erfüllbar sein? Man nimmt eine erfüllbare Formel und nimmt etwas unerfüllbares dazu, was die ganze Formelmenge unerfüllbar macht
Es muss gleichzeitig erfüllbar und unerfüllbar sein(du zeigst beides), da liegt der Widerspruch und die Formel, die du hinzufügst muss auf jeden Fall erfüllbar sein.

Du willst die Existenz einer Formelmenge\(\psi\)(Im Beispiel: es existiert ein Pfad von x nach y) zum Widerspruch führen:
Die Kunst liegt jetzt darin eine unendliche Formelmenge \(\phi\) zu konstruieren, die das Gegenteil von \(\psi\) ausdrückt von der aber alle endlichen Teilmengen mit \(\psi\) vereinbar sind, meist geschieht das wie folgt:
du hast irgendeine Formel \(\varphi_n\) die du selbst definierst (..., große Konjuktion/Disjuktion und so weiter sind da halt erlaubt und auch notwendig, ich finde nur es ist immer ein bisschen ein Ratespiel für mich(hatte allerdings auch noch kein Mathe I) was genau man jetzt darf, dass das ganze eine FO Formel bleiben muss ist aber klar - du müsstest jedes \(\varphi_n\) auch einzeln syntaktisch exakt aufstellen können.) und sagst dann \(\phi = \bigcup_n \varphi_n\)
Im Beispiel ist \(\phi\) die Vereinigung aus \(\varphi_n\) wobei dieses ausdrückt, dass zwischen x und y kein Pfad der Länge n existiert. Die endlichen Teilmengen wären also Aussagen wie es existiert kein Pfad der Länge {2,5,42,9000}. Das ist immer vereinbar mit der Aussage, dass überhaupt irgendein Pfad zwischen x und y existiert, er darf dann halt nur nicht die entsprechenden Längen haben.
\(\phi\) selbst drückt aber aus, dass für alle n kein Pfad der Länge n existiert, also existiert überhaupt kein (endlicher, hier lag mein Problem) Pfad.

Und nun ist Schema F: Du vereinigst \(\phi' = \phi \cup \psi\) und kommst zum Widerspruch:
-Jede endliche Teilmenge besteht aus einer endlichen Teilmenge von \(\phi\) und einer endlichen Teilmenge von \(\psi\), da die endlichen Teilmengen von \(\phi\) ja mit \(\psi\) vereinbar sind muss diese Teilmenge erfüllbar sein. Und wenn jede endliche Teilmenge erfüllbar ist, sagt der Kompaktheitssatz, dass auch die ganze Menge \(\phi'\) erfüllbar ist.
-\(\phi'\) kann aber gar nicht erfüllbar sein, da \(\phi\) ja genau so von uns gewählt wurde, dass es das Gegenteil von \(\psi\) bedeuted: um \(\phi\) zu erfüllen darf kein Pfad existieren, um \(\psi\) zu erfüllen muss aber ein Pfad existieren, beides zu erfüllen geht nicht.
Zuletzt geändert von Ankou am 31. Aug 2011 14:38, insgesamt 1-mal geändert.

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Unendlichkeit

Beitrag von fscheepy » 31. Aug 2011 13:37

Ankou hat geschrieben:
Warum muss denn z.B. bei der 13. Übung, G2 das Gamma_unendlich erfüllbar sein? Man nimmt eine erfüllbare Formel und nimmt etwas unerfüllbares dazu, was die ganze Formelmenge unerfüllbar macht
Es muss gleichzeitig erfüllbar und unerfüllbar sein(du zeigst beides), da liegt der Widerspruch und die Formel, die du hinzufügst muss auf jeden Fall erfüllbar sein.

Du willst die Existenz einer Formelmenge\(\psi\)(Im Beispiel: es existiert kein Pfad von x nach y) zum Widerspruch führen:
Die Kunst liegt jetzt darin eine unendliche Formelmenge \(\phi\) zu konstruieren, die das Gegenteil von \(\psi\) ausdrückt von der aber alle endlichen Teilmengen mit \(\psi\) vereinbar sind, meist geschieht das wie folgt:
du hast irgendeine Formel \(\varphi_n\) die du selbst definierst (..., große Konjuktion/Disjuktion und so weiter sind da halt erlaubt und auch notwendig, ich finde nur es ist immer ein bisschen ein Ratespiel für mich(hatte allerdings auch noch kein Mathe I) was genau man jetzt darf, dass das ganze eine FO Formel bleiben muss ist aber klar - du müsstest jedes \(\varphi_n\) auch einzeln syntaktisch exakt aufstellen können.) und sagst dann \(\phi = \bigcup_n \varphi_n\)
Im Beispiel ist \(\phi\) die Vereinigung aus \(\varphi_n\) wobei dieses ausdrückt, dass zwischen x und y kein Pfad der Länge n existiert. Die endlichen Teilmengen wären also Aussagen wie es existiert kein Pfad der Länge {2,5,42,9000}. Das ist immer vereinbar mit der Aussage, dass überhaupt irgendein Pfad zwischen x und y existiert, er darf dann halt nur nicht die entsprechenden Längen haben.
\(\phi\) selbst drückt aber aus, dass für alle n kein Pfad der Länge n existiert, also existiert überhaupt kein (endlicher, hier lag mein Problem) Pfad.

Und nun ist Schema F: Du vereinigst \(\phi' = \phi \cup \psi\) und kommst zum Widerspruch:
-Jede endliche Teilmenge besteht aus einer endlichen Teilmenge von \(\phi\) und einer endlichen Teilmenge von \(\psi\), da die endlichen Teilmengen von \(\phi\) ja mit \(\psi\) vereinbar sind muss diese Teilmenge erfüllbar sein. Und wenn jede endliche Teilmenge erfüllbar ist, sagt der Kompaktheitssatz, dass auch die ganze Menge \(\phi'\) erfüllbar ist.
-\(\phi'\) kann aber gar nicht erfüllbar sein, da \(\phi\) ja genau so von uns gewählt wurde, dass es das Gegenteil von \(\psi\) bedeuted: um \(\phi\) zu erfüllen darf kein Pfad existieren, um \(\psi\) zu erfüllen muss aber ein Pfad existieren, beides zu erfüllen geht nicht.
Hmm...kannst du nochmal genauer erläutern, welche Formel(-menge) was genau ausdrückt? Steht \(\psi\) nicht für die Aussage "es existiert EIN Pfad von x nach y"? Dann wählt man sich ein \(\varphi_n\) sodass gilt: \(\varphi_n\):="es existiert kein Pfad der Länge n". Dies steht nicht im Widerspruch mit \(\psi\), da man das n einfach so wählen kann, dass es \(\psi\) nicht widerspricht. Nun definieren wir uns \(\phi\) als Vereinigung aller \(\varphi_n\). Vereinigt man jetzt \(\phi\) mit \(\psi\), so haben wir eine Formelmenge, die laut Kompaktheitssatz erfüllbar sein müsste (\(\psi\) ist erfüllbar und jede endliche Teilmenge von \(\phi\) ist erfüllbar), was aber nicht sein kann, da sich \(\psi\) und \(\phi\) widersprechen. Somit haben wir einen Widerspruch, also kann es keine Formeln geben, die ausdrückt, dass ein Pfad von x nach y existiert.

Stimmt das jetzt so oder was habe ich falsch verstanden?

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Unendlichkeit

Beitrag von Ankou » 31. Aug 2011 14:45

Steht nicht für die Aussage "es existiert EIN Pfad von x nach y"?
ja richtig, hab mich wohl verschrieben - ist geändert.
Hmm...kannst du nochmal genauer erläutern, welche Formel(-menge) was genau ausdrückt?
\(\psi\) = die Formel, deren Existenz wir wiederlegen wollen - Es existiert ein Pfad
\(\phi\) = eine zu \(\psi\) gegensätzliche, unendliche Formelmenge - Es existiert kein Pfad
\(\varphi_n\) = Teilformel aus der \(\phi\) aufgebaut ist - Es existiert kein Pfad der Länge n
\(\phi'\) = Vereinigung, die wahr ist wenn \(\psi\) und \(\phi\) wahr sind und somit nicht erfüllbar sein kann, es aber nach Kompaktheitssatz dennoch ist.
Stimmt das jetzt so oder was habe ich falsch verstanden?
stimmt so fast =>
(\(\psi\) ist erfüllbar und jede endliche Teilmenge von \(\phi\) ist erfüllbar)
das allein reicht nicht, jede endliche Teilmenge von \(\phi\) vereinigt mit \(\psi\) ist ebenfalls erfüllbar.

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Unendlichkeit

Beitrag von fscheepy » 31. Aug 2011 15:01

Okay, vielen Dank. Soweit habe ich das jetzt verstanden. Ich bin mir aber nicht sicher, ob ich das in einer Klausuraufgabe hinbekommen würde.
Eine Frage habe ich aber noch:
Ankou hat geschrieben:
(\(\psi\) ist erfüllbar und jede endliche Teilmenge von \(\phi\) ist erfüllbar)
das allein reicht nicht, jede endliche Teilmenge von \(\phi\) vereinigt mit \(\psi\) ist ebenfalls erfüllbar.
Laut Kompaktheitssatz muss doch nur jede endliche Teilmenge erfüllbar sein. Hierbei besteht \(\phi'\) ja aus der Vereinigung von \(\phi\) und \(\psi\), also sind die endlichen Teilmengen von \(\phi'\) alle endlichen Teilmengen von \(\phi\) und außerdem noch \(\psi\). Wieso reicht dann die Aussage, dass \(\psi\) erfüllbar ist und jede endliche Teilmenge von \(\phi\) erfüllbar ist nicht aus? Schließlich sind das ja alle endlichen Teilmengen von \(\phi'\).


/edit: ich habe mich jetzt mal an der Aufgabe 6c) aus der Klausur WS05/06 probiert:
"Angenommen, es gäbe eine Satzmenge \(\psi\), die aussagt, dass E endlich viele Äquivalenzklassen hat. Dann können wir ein \(\varphi_n\) definieren, das aussagt: "es gibt höchstens n Äquivalenzklassen". Definieren wir außerdem \(\phi = \bigcup_n \varphi_n\). Dann sagt \(\phi\) aus, dass es beliebig viele Äquivalenzklassen gibt. Somit gibt es laut Kompaktheitssatz also unendlich viele Äquivalenzklassen (der Satz ist ein bisschen schwammig, hier sollte ich vielleicht lieber ausdrücken, dass laut Kompaktheitssatz \(\phi\) ausdrückt, dass es unendlich viele Äquivalenzklassen gibt). Desweiteren sei angemerkt, dass keines der \(\varphi_n\) der Satzmenge \(\psi\) widerspricht, da jedes n endlich ist. Nun ist also \(\psi\) erfüllbar und laut Kompaktheitssatz \(\phi\) ebenfalls erfüllbar. Betrachten wir \(\phi'\) := \(\phi \cup \psi\). Dann ist jede endliche Teilmenge von \(\phi'\) erfüllbar (also sowohl \(\psi\) ist erfüllbar als auch jede endliche Teilmenge von \(\phi\)). Somit müsste laut Kompaktheitssatz \(\phi'\) ebenfalls erfüllbar sein, was nicht möglich ist, da sich \(\psi\) und \(\phi\) gegenseitig ausschließen. Somit kann ein solches \(\psi\) nicht existieren.

Was hältst du davon? :mrgreen:

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Unendlichkeit

Beitrag von Ankou » 31. Aug 2011 15:37

also sind die endlichen Teilmengen von \(\phi'\) alle endlichen Teilmengen von \(\phi\) und außerdem noch \(\psi\)
Nö, Beispiel: sei \(\phi = \mathbb{N} \cup \{fisch\}\) dann sind die endlichen Teilmengen von \(\phi\) halt nicht nur {fisch}, {1},{1,2},{1,2,3},{2,3},... sondern eben auch {fisch,2,3,4}.
Genau genommen musst du eben noch alle Teilmengen von \(\phi\) mit allen Teilmengen von \(\psi\) kombinieren. Wenn du es aber direkt mit \(\psi\) kombinierst und zeigst dass das erfüllbar sind, dann sind auch alle Kombinationen mit Teilmengen von \(\psi\) nach Kompaktheitssatz erfüllbar(gilt ja nicht nur für unendliche Mengen) - ich glaube nicht dass man das begründen muss, warum es reicht wenn alle Teilmengen von \(\phi\) vereinigt mit \(\psi\) erfüllbar sind, aber es muss halt schon so sein, sonst hast du nicht alle endlichen Teilmengen.
Dann können wir ein \(\varphi_n\) definieren, das aussagt: "es gibt höchstens n Äquivalenzklassen".
1. das ist eine Behauptung, die du vermutlich eher (durch Angabe von \(\varphi_n\)) beweisen solltest, ansonsten kann es ja auch sein, dass es nicht das \(\psi\) ist, was es nicht geben kann, sondern eben das \(\varphi_n\)
2. wenn etwas höchstens 1, höchstens 2, höchstens 3, .... Äquivalenzklassen hat, dann sind das nicht unendlich viele sondern immer noch höchstens 1. Du willst mindestens.

Die Aufgabe kam übrigens schon 2 mal in Klausuren vor und meine Lösung dazu hab ich hier auch schon gepostet
http://d120.de/forum/viewtopic.php?f=17 ... 88#p131868

Antworten

Zurück zu „Archiv“