Kompaktheitssatz

Neue Frage »

Pippen Auf diesen Beitrag antworten »
Kompaktheitssatz
Eine Formelmenge F ist erfüllbar gdw. jede endliche Teilmenge von F erfüllbar ist.

Wenn ich den Satz richtig verstehe, dann könnte F einige endliche Formeln enthalten und einige unendliche Formeln und dennoch würde es ausreichen, nur die endlichen Formeln auf ihre Erfüllbarkeit zu prüfen und damit auf die Erfüllbarkeit von F zu schließen, obwohl F ja noch andere - unendliche - Formeln enthält? Das leuchtet mir nämlich nicht so recht ein.

Wenn F dagegen nur endliche Formeln enthält, dann scheint der Kompaktheitssatz trivial: Sei F erfüllbar, d.h. jede Formel von F in einer Interpretation wahr, dann recht recht auch ein Teil der Formeln von F. Sei jede endliche Teilmenge von F erfüllbar, dann ist damit ("jede") ja F vollständig beschrieben und somit auch erfüllbar.

Offenbar mache ich da mind. einen Denkfehler, denn der Beweis des (aussagenlogischen) Kompaktheitssatzes ist ziemlich aufwändig.
zweiundvierzig Auf diesen Beitrag antworten »

Eine endliche Teilmenge ist eine Teilmenge mit endlich vielen Elementen. Jede Formel in der Aussagenlogik/FO-Prädikatenlogik ist endlich!
Pippen Auf diesen Beitrag antworten »

D.h. also unsere Formelmenge F kann zwar unendlich viele, aber nur endlich-lange Formeln beherbergen. Wieso kann man dann den Kompaktheitssatz nicht einfach so beweisen:

Kompaktheitssatz: Eine Formelmenge F ist erfüllbar <=> jede endliche Teilmenge von F erfüllbar ist.

=>: Sei F erfüllbar, d.h. es gibt eine Interpretation, wo jede Formel in F wahr ist. Dann gilt das erst recht für jede endliche Teilmenge von F.

<=: Sei jede endliche Teilmenge von F erfüllbar. Wir nehmen einfach an, wir können jedes F - auch eine unendliche Menge, selbst eine überabzählbare - vollständig in endliche Teilmengen zerlegen. Dann folgt trivial, dass auch F erfüllbar sein muss. (Achtung: Könnten wir F nicht vollständig in endliche Teilmengen zerlegen, dann scheitert mE auch der Kompaktheitssatz, weil dann der Rückschluss von "jede endliche Teilmenge von F" auf "F" nicht mehr funktioniert.)

Ist das im Grunde der Beweis des Kompaktheitssatzes oder drehe ich mal wieder am Rad (wobei dann ein Hinweis hilfreich wäre, wo und wieso es nicht klappt, was ich mir so denke)?
zweiundvierzig Auf diesen Beitrag antworten »

Das Argument für ist richtig, aber das ist auch die leichte Richtung.

Der Punkt bei der umgekehrten Richtung ist, dass nicht klar ist, wie man aus erfüllenden Interpretationen für alle endlichen Teilmengen eine Interpretation für *alle* Formeln simultan bekommt.

Es gibt verschiedene Methoden das zu beweisen, z.B.: Gödelscher Vollständigkeitssatz, Lemma von König, Satz von Los, Stonescher Darstellungssatz.
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Der Punkt bei der umgekehrten Richtung ist, dass nicht klar ist, wie man aus erfüllenden Interpretationen für alle endlichen Teilmengen eine Interpretation für *alle* Formeln simultan bekommt.



Wenn sich F vollständig in endliche Teilmengen zerlegen läßt - das nehme ich ja an - dann sollte aus der Erfüllbarkeit jeder endlichen Teilmenge von F auch die Erfüllbarkeit von F trivial folgen und die "schwierige" Richtung des K-Satzes wäre gleichfalls bewiesen. Wenn F sich nicht vollständig in endliche Teilmengen zerlegen läßt, dann kann man auch nicht von der Erfüllbarkeit der Teilmengen von F auf das ganze F schließen, also kein Kompaktheitssatz, oder? Ich sehe da irgendwie kein Problem.
zweiundvierzig Auf diesen Beitrag antworten »

Jede Menge, gleich welcher Kardinalität, lässt sich in endliche Teilmengen zerlegen.

Laut Kompaktheitssatz folgt aus endlicher Erfüllbarkeit auch insgesamt Erfüllbarkeit, aber das ist keineswegs trivial.

Seien für eine FO-Formelmenge alle endlichen Teilmengen gegeben durch ( geeignete Indexmenge). Angenommen, wir haben Interpretationen gegeben mit für alle . Es ist wahr, aber nicht ohne weiteres klar, dass man Interpretationen "passend zusammensetzen" kann, um eine Interpretationen zu gewinnen, sodass gilt.

Edit: Eine äquivalente Aussage ist, dass Unerfüllbarkeit einer beliebig großen Formelmenge impliziert, dass es bereits eine endliche Formelmenge geben muss, die unerfüllbar ist. Das ist ohne weiteres genau so wenig klar.
 
 
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Jede Menge, gleich welcher Kardinalität, lässt sich in endliche Teilmengen zerlegen.



Ergibt sich damit aber nicht auch die sog. nichttriviale Richtung des Kompaktheitssatzes?

Zur Erinnerung, der K-Satz lautet: F erfüllbar <=> jede endliche Teilmenge von F erfüllbar.

=> ist trivial.
<= doch aber dann auch, denn: wenn jede Menge sich in endliche Teilmengen zerlegen läßt, dann auch F und wenn dann jede dieser endlichen Teilmengen erfüllbar sind, was wir ja annehmen können, dann trivial doch auch F, zu deren Menge sie sich zusammensetzen, nicht wahr? Ich verstehe nicht, warum das ein Problem sein soll. Wenn ich eine Menge, sagen wir IR, in endliche Teilmengen zerlege, sagen wir je eine reelle Zahl und ich annehme, dass alle diese endlichen Teilmengen X seien, dann folgt doch daraus sofort, dass auch IR die Eigenschaft X hat. Verstehst du mein Problem?
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Pippen
wenn dann jede dieser endlichen Teilmengen erfüllbar sind, was wir ja annehmen können, dann trivial doch auch F, zu deren Menge sie sich zusammensetzen, nicht wahr?

Was ist denn eine erfüllende Interpretation von ?
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Zitat:
Original von Pippen
wenn dann jede dieser endlichen Teilmengen erfüllbar sind, was wir ja annehmen können, dann trivial doch auch F, zu deren Menge sie sich zusammensetzen, nicht wahr?

Was ist denn eine erfüllende Interpretation von ?


Eine, wo alle Formeln in F wahr wären. Wenn nun F sich in endliche Teilmengen zerlegt und wenn jede solche endliche Teilmenge von F erfüllbar ist, also eine Interpretation hat, wo alle deren Formeln wahr wären, dann kann man schlicht jede Teilmenge mit der sie erfüllenden Interpretation hernehmen und damit hätte man ja F erfüllt. So zumindest meine Idee. Oder mache ich da einen Denkfehler?
zweiundvierzig Auf diesen Beitrag antworten »

Betrachte . Was ist eine erfüllende Interpretation von ?
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Betrachte . Was ist eine erfüllende Interpretation von ?


Jede der Disjunktionen muss wahr sein, richtig? Soweit ich das sehe, könnte das der Fall sein.

Hier können wir am Beispiel auch durchspielen, was ich meine. Phi ist eine unendliche Formelmenge, die aus unendlichen vielen endlichen Teilmengen - zB die jeweils einzelne Disjunktion - besteht. Wenn jede dieser endlichen Teilmengen (Disjunktionen) erfüllbar ist, dann muss auch Phi erfüllbar sein, denn Phi ist ja nichts weiter als alle endlichen Teilmengen zusammengenommen. Das läßt sich mE verallgemeinern, meinste nicht?

p.s. Weiß jmd. einen guten Link zum Beweis des Komapktheitssatzes ohne Gödels Vollständigkeitssatz (weil dann wird's einfach, das kapier selbst ich)?
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Pippen
Jede der Disjunktionen muss wahr sein, richtig?

Ja. Damit erfüllt ist, ist eine Belegung gesucht, für die gilt. Eine Belegung ist eine Abbildung , wobei die Variablenmenge bezeichnet. Für jede Variable muss also festgelegt werden, ob sie mit oder belegt wird. Wie sieht hier eine geeignete Belegung aus?

Edit: Man ist nicht gezwungen Vollständigkeit zu bemühen. Für abzählbare Formelmengen gibt es einen Beweis via vollständiger Induktion. Aber der ist immer noch nichttrivial.
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Zitat:
Original von Pippen
Jede der Disjunktionen muss wahr sein, richtig?

Ja. Damit erfüllt ist, ist eine Belegung gesucht, für die gilt. Eine Belegung ist eine Abbildung , wobei die Variablenmenge bezeichnet. Für jede Variable muss also festgelegt werden, ob sie mit oder belegt wird. Wie sieht hier eine geeignete Belegung aus?



In allen Disjunktionen ist jeweils die erste Aussage wahr und die zweite falsch.
zweiundvierzig Auf diesen Beitrag antworten »

Ja, d.h. und für .

Es erfordert aber eine Konstruktion dieser Belegung für die gesamte Formelmenge. Beim Beweis des Kompaktheitssatzes muss man das für eine allgemeine Formelmenge tun.
Pippen Auf diesen Beitrag antworten »

Aber woran scheitert dann mein Beweis des Kompaktheitssatzes? Kannst du die kritische Stelle aufzeigen?

Zur Erinnerung, der K-Satz lautet: F erfüllbar <=> jede endliche Teilmenge von F erfüllbar.

=> ist trivial.
<= wie folgt:

1. Jede Menge F läßt sich in endliche Teilmengen Fn mit n IN oder IR zerlegen, also F = Fn.
2. Nach Annahme sei jede endliche Teilmenge Fn erfüllbar.
3. Da nun F = Fn (siehe 1.), folgt somit die Erfüllbarkeit auch für F.
zweiundvierzig Auf diesen Beitrag antworten »

Du musst eine erfüllende Belegung für ganz konstruieren.
Elvis Auf diesen Beitrag antworten »

Zitat:
Original von Pippen
1. Jede Menge F läßt sich in endliche Teilmengen Fn mit n IN oder IR zerlegen, also F = Fn.


Die Menge der reellen Zahlen lässt sich in einelementige also endliche Teilmengen der reellen Zahlen zerlegen: ,
also (?) ist die Menge der reellen Zahlen eine Menge, die genau eine reelle Zahl enthält. Wie das ?
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Du musst eine erfüllende Belegung für ganz konstruieren.


Woher kommt dieses ? Bleib mal an meinem Beweis, sonst bin ich sofort überfordert, irgendwo muss sich da ja ein Fehlschritt angeben lassen, also nochmal:

Zur Erinnerung, der K-Satz lautet: F erfüllbar <=> jede endliche Teilmenge von F erfüllbar.

=> ist trivial.
<= wie folgt:

1. Jede Menge F läßt sich in endliche Teilmengen Fn mit n € IN oder IR zerlegen, also F = Fn, d.h. F und alle endlichen Teilmengen von F (für die wir Fn schreiben) vereinigt sind gleich.
2. Nach Annahme sei jede endliche Teilmenge Fn erfüllbar.
3. Da nun F = Fn (siehe 1.), folgt somit die Erfüllbarkeit auch für F.

Vielleicht an einem konkreten Beispiel, damit wir uns nicht missverstehen:

Sei zB F = {p, p & q}. Dann gibt es drei endliche Teilemengen von F: {p} und {p & q} und {p, p & q}. Zusammengefasst (vereinigt) ergeben die Teilmengen wieder F. Wenn nun alle drei Teilmengen nach Annahme erfüllbar sind, also eine wahr Interpretation haben, dann muss das auch für F gelten, denn F ist ja nichts weiter als die Vereinigung der drei Teilmengen, von denen wir aber schon wissen, dass sie alle drei erfüllbar sind.

@Elvis: Ich meine damit: Jede Menge F läßt sich in endliche Teilmengen Fn zerlegen, so dass F gleich alle Teilmengen Fn vereinigt ist. Im Beispiel für IR läßt sich also IR in einelementige Teilmengen (je eine reelle Zahl) zerlegen, so dass alle diese Teilmengen zusammen IR ergeben. Ich weiß nicht so recht, wie man das eindeutiger notiert, aber ich hoffe die Idee wird klar und die Idee ist richtig.
zweiundvierzig Auf diesen Beitrag antworten »

Du musst aus der Voraussetzung der endlichen Erfüllbarkeit von eine erfüllende Belegung für ganz konstruieren.
Elvis Auf diesen Beitrag antworten »

@Pippen
Deine Idee ist nicht klar, und sie ist falsch. Wenn deine Idee richtig wäre, könntest du daraus keine falschen Schlüsse ziehen. Das ergibt sich aus einfachster Logik, denn aus wahren Voraussetzungen folgt nie eine falsche Aussage.
Für endliche Mengen F ist F=Fn, also die Menge F gleich einer ihrer endlichen Teilmengen, das ist trivial. Diese Trivialitaet benutzt du in deinem Scheinbeweis für den Kompaktheitssatz. Für unendliche Mengen ist F=Fn falsch.
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Du musst aus der Voraussetzung der endlichen Erfüllbarkeit von eine erfüllende Belegung für ganz konstruieren.


Wenn jede endliche Teilmenge von F erfüllbar ist, dann gibt es also keine endliche Teilmenge von F die unerfüllbar ist. Wie soll dann F unerfüllbar sein? Wäre F unerfüllbar, dann müsste es ja in F irgendwo den Widerspruch "X & ~X" geben und das wäre bereits eine mögliche endliche Teilmenge von F, von der wir ja aber per Annahme wüßten, dass es sie nicht gibt (s.o.)

@Elvis: Ich sage, dass eine Menge M gleich der Vereinigung ihrer möglichen endlichen Teilmengen ist. Nimm IR. Und dann zerlege IR in alle möglichen Teilmengen, Teilmengen mit genau einem Element, mit zwei Elementen usw. Wenn du diese ganzen Teilmengen vereinigst, dann hast du IR.
Pippen Auf diesen Beitrag antworten »

Hier mal eine verfeinerte englische Version, die ich bei stackexchange reingestellt habe, um mal zu sehen, was da so kommt:

The Compactness Theorem states: F is satisfiable <-> every subset of F is satisfiable.

-> is trivial.
<- We assume every subset of F is satisfiable, i.e. no subset of F is unsatisfiable. Now we assume by the way of contradiction that F is unsatisfiable, i.e. at least one formula in F has to be a falsum. But this formula would be a subset of F which contradicts the fact that by assumption no subset of F is unsatisfiable. Therefore F must be satisfiable. Done.

Why is this simple version wrong for I only find pretty sophisticated proofs of the compactness theorem.
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Pippen
The Compactness Theorem states: F is satisfiable <-> every subset of F is satisfiable.

Das ist nicht der Kompaktheitssatz.
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Pippen
Wäre F unerfüllbar, dann müsste es ja in F irgendwo den Widerspruch "X & ~X" geben

Nein.
Elvis Auf diesen Beitrag antworten »

@Pippen
Dass eine Menge die Vereinigung ihrer endlichen Teilmengen ist, ist trivial. In deinem albernen Scheinbeweis für den Kompaktheitssatz benutzt du aber, dass eine unendliche Menge F gleich einer endlichen Teilmenge von F ist, und das ist offenbar falsch.
Pippen Auf diesen Beitrag antworten »

Ok, ich hab jetzt zumindest begriffen, warum mein Beweis nicht funktioniert. Ist ja auch schonmal was.
Pippen Auf diesen Beitrag antworten »

Eine neue Idee.

Wir erinnern uns an den Kompaktheitssatz: F ist erfüllbar <-> jede endliche Teilmenge von F erfüllbar, wobei nur die Richtung von rechts nach links ein Problem darstellt, die wir nun beweisen wollen:

Wir nehmen dazu die Negation an, d.h. jede endliche Teilmenge von F sei erfüllbar, aber F selbst sei unerfüllbar. Wenn F unerfüllbar ist, dann ist F inkonsistent, womit aus F die Formel p & ~p folgerbar sein müsste. Doch so eine Folgerung (Beweis) ist finit, d.h. bereits aus einer endlichen Menge an Formeln aus F müsste p & ~p folgerbar sein und genau diese endliche Menge wäre damit selbst inkonsistent und unerfüllbar, im Widerspruch zur Annahme, jede endliche Teilmenge von F sei erfüllbar, also muss die Annahme negiert werden, d.h. jede endliche Teilmenge von F erfüllbar -> F ist erfüllbar. qed?
zweiundvierzig Auf diesen Beitrag antworten »

Das ist richtig. In diesem Beweis wird der Vollständigkeitssatz benutzt.
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Das ist richtig. In diesem Beweis wird der Vollständigkeitssatz benutzt.


Achso? Wo genau verbirgt er sich?
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Pippen
Wenn F unerfüllbar ist, dann ist F inkonsistent, womit aus F die Formel p & ~p folgerbar sein müsste.
Pippen Auf diesen Beitrag antworten »

Sind das nicht einfach Definitionen und ihre Konsequenzen? So wie Unerfüllbarkeit definiert ist, führt sie geradewegs zu Inkonsistenz und aus Inkonsistenz folgt nunmal Beliebiges, also auch p & ~p. Daran würde doch auch Vollständigkeit nichts ändern, oder?
zweiundvierzig Auf diesen Beitrag antworten »

Du sagst: ist unerfüllbar (Semantik), also ist aus ableitbar (Syntax).

Der Schluss von Semantik (Erfüllbarkeit) auf Syntax (Ableitbarkeit) ist gerade die Vollständigkeit des Kalküls.
Pippen Auf diesen Beitrag antworten »

Ja, stimmt.

Kannst du vllt. die Beweisidee schildern, mit der man ohne den Vollständigkeitssatz das Kompaktheitstheorem für die AL zeigt?
zweiundvierzig Auf diesen Beitrag antworten »

Es gibt einen induktiven Beweis, siehe Schöning: Logik für Informatiker.
Neue Frage »
Antworten »



Verwandte Themen

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