Kompaktheitssatz (Logik)

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$ ist erfüllbar (d.h., hat ein Modell) $\Leftrightarrow$ jede endliche Teilmenge von $X$ hat ein Modell.

Beweis

Der Kompaktheitssatz ergibt sich als Korollar aus dem Gödel'schen Vollständigkeitssatz. Dementsprechend kurz gestaltet sich auch der Beweis:

$\Rightarrow$: Angenommen, X hat ein Modell. Dann ist dieses (trivialerweise) auch ein Modell einer jeden endlichen Teilmenge von X.

$\Leftarrow$: Angenommen, jede endliche Menge $X_{fin}\subseteq X$ 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. $\exists x:x\neq x$) 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 $\phi$ aus einer Formelmenge $X$, so gibt es eine endliche Menge $X_{fin}\subseteq X$, sodaß $\phi$ aus $X_{fin}$ folgt.

($X\models \phi \Rightarrow X_{fin}\models \phi$)