Kompaktheitssatz und Formalisierbarkeit in FO

Daki
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 4. Nov 2010 14:34

Kompaktheitssatz und Formalisierbarkeit in FO

Beitrag von Daki » 1. Sep 2011 20:22

Hallo,

nachdem ich meinen Tutor gelöchert, aber keine zufriedenstellende Antwort erhalten habe, nun die Frage ins Forum: Im 6. Übungsblatt (uebung13.pdf) soll man bei der H1 für drei Eigenschaften blabla entscheiden, ob sie in FO formalisierbar sind. Bei Teilaufgabe (c) ist die Eigenschaft nicht formalisierbar.

Nun will ich wissen, ob meine Argumentation dazu korrekt ist. Bei (c) heißt es: „Jedes Element hat nur endlich viele Vorgänger.“ Wenn es laut Kompaktheitssatz (salopp gesagt) nicht möglich ist, etwas über endliche Mengen auszusagen, ohne dabei auch etwas über unendliche Mengen auszusagen, sollte Folgendes funktionieren: Ich nehme einmal die Aussage „Jedes Element hat nur endlich viele Vorgänger“ und konstruiere daraus eine weitere Aussage, wobei ich „endlich“ durch „unendlich“ ersetze: „Jedes Element hat (nur) unendlich viele Vorgänger.“ Nun überprüfe ich beide Aussagen und komme zum Schluss, dass die eine wahr und die andere falsch ist. Also sollte sich eine FO-Formel, wenn es denn für die in (c) genannte Aussage eine gäbe, widersprüchlich verhalten, ergo: es ist nicht in FO formalisierbar.

Ist diese Argumentation korrekt bzw. immer/bedingt anwendbar? Falls nicht, wäre ein Gegenbeispiel sehr hilfreich. ^^

Viele Grüße
Nein, mein Nick hat nichts mit Kissen zu tun!

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Kompaktheitssatz und Formalisierbarkeit in FO

Beitrag von AlexanderF » 1. Sep 2011 21:46

hallo Daki,

also, ich denke, deine Argumentation ist,
soweit ich sie verstehe, nicht ganz korrekt,
ich bin mir zumindest nicht ganz sicher, ob Du den Kompaktheitssatz richtig verstanden hast,


also, eigentlich wäre die Aufgabe in etwa so zu beantworten:


Man nimmt an die Aussage "Jedes Element hat nur endlich viele Vorgänger." ließe sich durch eine FO Formel phi formulieren.

Nun betrachte man die FO-Formel psi_n (siehe Aufgabenstellung),
die besagt, dass das Element c (also irgendein Element) mindestens n verschiedene Vorgänger hat.

Die Formelmenge {psi_n | n e(Element) N} drückt nun aus, dass c, unendlich viele Vorgänger hat.

Nimmt man zu dieser Formelmenge noch die angenommene Aussage phi dazu, (in der Aufgabenstellung die Menge groß Phi) hat man eine nicht erfüllbare Aussage.
Denn gleichzeitig soll jedes Element nur endlich viele Vorgänger haben, aber c hat unendlich viele Vorgänger.

Nun sind nach Kompaktheitssatz folgende Aussagen äquivalent:
(i) eine Fomelmenge Phi ist erfüllbar.
(ii) jede endliche Teilmenge Phi_0 von Phi ist erfüllbar.

unsere Formelmenge Phi ist, wie gesagt nicht erfüllbar,
also bleibt, um einen Widerspruch herzuleiten, noch zu zeigen, dass jede endliche Teilmenge aber schon erfüllbar ist.

denn dann wäre (ii) erfüllt, (i) aber nicht!


und es ist auch wirklich jede endliche Teilmenge von Phi erfüllt:
Da wir von einer endlichen Teilmenge ausgehen,
ist auch nur eine endliche Anzahl an den ursprünglichen psi_n´s in der Teilmenge enthalten,

Diese sagt jetzt also nicht mehr aus, dass c unendliche viele Vorgänger hat (was ja die unendliche Menge ausgesagt hatte) sondern nur noch, dass c mindestens n Vorgänger hat (wobei n dann das maximale n aus den Psi_n´s ist),
und es steht nicht mehr in Widerspruch zur Aussage, dass jedes Element nur endlich viele Vorgänger hat.

also ist der Kompakheitssatz verletzt
(i) nicht erfüllt aber (ii) erfüllt (beides ist ja nach Kompaktheitssatz äquivalent),
also kann unsere anfangs gemachte Annahme, "Jedes Element hat nur endlich viele Vorgänger" ließe sich formulieren als eine FO Formel, nicht stimmen.


Ich hoffe, Dir ist es jetzt ein wenig klarer geworden,


und allen morgen noch viel Glück bei der Klausur!
Alexander

Daki
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 4. Nov 2010 14:34

Re: Kompaktheitssatz und Formalisierbarkeit in FO

Beitrag von Daki » 1. Sep 2011 22:14

Vielen Dank für die Antwort, AlexanderF; auch für die Glückwünsche (werde ich wohl brauchen). Ich werde sie (die Antwort) mir mal irgendwann genauer zu Gemüte führen.

Beim Groben Überblicken sehe ich allerdings noch keine direkte Antwort auf meine Frage. Vielleicht sehe ich sie aber nur noch nicht, oder sie kommt noch … irgendwann. ^^

Grüße
Nein, mein Nick hat nichts mit Kissen zu tun!

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Kompaktheitssatz und Formalisierbarkeit in FO

Beitrag von AlexanderF » 1. Sep 2011 22:47

hallo Daki,

also Deine Frage war ja, ob Deine Argumentation korrekt ist.

also zuerst sagst Du ja:
Daki hat geschrieben: Wenn es laut Kompaktheitssatz (salopp gesagt) nicht möglich ist, etwas über endliche Mengen auszusagen, ohne dabei auch etwas über unendliche Mengen auszusagen,
Das ist nicht das, was der Kompaktheitssatz eigentlich aussagt, oder ich erkenne es zumindest gerade nicht.

Deine Argumentation beginnt so:
Daki hat geschrieben: Ich nehme einmal die Aussage „Jedes Element hat nur endlich viele Vorgänger“ und konstruiere daraus eine weitere Aussage, wobei ich „endlich“ durch „unendlich“ ersetze: „Jedes Element hat (nur) unendlich viele Vorgänger.“
Die Aussage „Jedes Element hat unendlich viele Vorgänger.“ lässt sich wohl konstruieren durch eine unendliche Menge, ähnlich der Aussage im Lösungsvorschlag.

Weiter sagst Du:
Daki hat geschrieben: Nun überprüfe ich beide Aussagen und komme zum Schluss, dass die eine wahr und die andere falsch ist. Also sollte sich eine FO-Formel, wenn es denn für die in (c) genannte Aussage eine gäbe, widersprüchlich verhalten, ergo: es ist nicht in FO formalisierbar.
Das kannst Du so nicht sagen, dass die eine wahr ist und die andere falsch,
"Jedes Element hat nur endlich viele Vorgänger." ist erfüllbar, z.B. erfüllt die Menge der natürlichen Zahlen diese Formel.
aber auch dir Formel
„Jedes Element hat unendlich viele Vorgänger.“ ist, denke, ich erfüllbar,
z.B. durch die Menge der ganzen Zahlen.

aber auf jeden Fall ist das ("eine Formel erfüllbar, irgendeine Formelmenge nicht erfüllbar") keine Begründung, warum die Aussage "Jedes Element hat nur endlich viele Vorgänger." sich nicht mit einer FO Formel ausdrücken lässt,

hier müsstest Du dann mit dem Kompaktheitssatz argumentieren.

Daki
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 4. Nov 2010 14:34

Re: Kompaktheitssatz und Formalisierbarkeit in FO

Beitrag von Daki » 2. Sep 2011 06:23

Vielen Dank auch für diese Antwort. Ich denke zumindest, gerade meinen Denkfehler gefunden zu haben (kann es gerade nicht nachprüfen).

Viele Grüße
Nein, mein Nick hat nichts mit Kissen zu tun!

Antworten

Zurück zu „Archiv“