Endlichkeitssatz
aus Wikipedia, der freien Enzyklopädie
Der Endlichkeitssatz, auch Kompaktheitssatz genannt, ist einer der wichtigsten Sätze der Logik und Modelltheorie erster Stufe. Er besagt: Eine (möglicherweise unendliche) Formelmenge X der Logik der ersten Stufe ist genau dann erfüllbar (d.h. hat ein Modell), wenn jede endliche Teilmenge von X ein Modell hat.
[Bearbeiten] Beweis
Der Kompaktheitssatz ergibt sich als Korollar aus dem Gödel'schen Vollständigkeitssatz. Dementsprechend kurz gestaltet sich auch der Beweis:
: Angenommen, X hat ein Modell. Dann ist dieses (trivialerweise) auch ein Modell einer jeden endlichen Teilmenge von X.
: Angenommen, jede endliche Menge 
besitzt ein Modell. Zur Erzeugung eines Widerspruchs wird angenommen, X habe kein Modell. Dann ist aus X in einem vollständigen und korrekten formalen System ein Widerspruch (z.B. 
) herleitbar (Vollständigkeitssatz). Da eine Herleitung in einem formalen System (nach Definition) endlich ist, können in dieser Herleitung auch nur endlich viele Formeln aus X verwendet worden sein. Also ist aus einer endlichen Teilmenge von X ein Widerspruch herleitbar, und diese besitzt somit kein Modell (Korrektheitssatz). Widerspruch. Also besitzt X doch ein Modell.
Im Kern des Beweises steht das folgende Ergebnis, das direkt aus dem Gödel'schen Vollständigkeitssatz folgt:
Folgt eine Formel φ aus einer Formelmenge X, so gibt es eine endliche Menge , sodass φ aus Xfin folgt.
(
es gibt endliches mit 
)
