Kompaktheitssatz (Logik)

mathematischer Satz
(Weitergeleitet von Kompaktheit (Logik))

Der Kompaktheitssatz, auch Endlichkeitssatz genannt, ist einer der wichtigsten Sätze der Aussagenlogik und der Prädikatenlogik erster Stufe. Er besagt: Eine (möglicherweise unendliche) Formelmenge ist genau dann erfüllbar (d. h., hat ein Modell), wenn jede endliche Teilmenge von erfüllbar ist. Für die Logik der 2. Stufe gilt dieser Satz nicht.

Eine wichtige Folgerung aus dem Kompaktheitssatz ist, dass jede (möglicherweise unendliche) Formelmenge , die beliebig große endliche Modelle hat, auch ein unendliches Modell hat. Mit dieser Folgerung ist häufig die Axiomatisierbarkeit von Klassen endlicher Strukturen widerlegbar.

Für die Prädikatenlogik erster Stufe ergibt sich der Kompaktheitssatz als Korollar aus dem Gödelschen Vollständigkeitssatz. Dementsprechend kurz gestaltet sich auch der Beweis:

 “: Angenommen,   hat ein Modell. Dann ist dieses (trivialerweise) auch ein Modell einer jeden endlichen Teilmenge von  .

 “: Angenommen, jede endliche Menge   besitzt ein Modell. Zur Erzeugung eines Widerspruchs wird angenommen,   habe kein Modell. Dann folgt aus   semantisch ein Widerspruch, z. B.  . Formal:

 

(Jedes Modell, das   erfüllt, erfüllt auch den Widerspruch. Das gilt, weil es eben kein Modell für   gibt.)

Der Gödelsche Vollständigkeitssatz sagt nun, dass   schon syntaktisch aus   folgt. Formal:

 

Es gibt also einen formalen Beweis, eine syntaktische Herleitung von   aus  . Da eine Herleitung in einem formalen System (nach Definition) endlich ist, können in dieser Herleitung auch nur endlich viele Formeln aus   verwendet worden sein. Also ist aus einer endlichen Teilmenge von   ein Widerspruch herleitbar, und diese besitzt somit kein Modell (Korrektheitssatz). Widerspruch. Also besitzt   doch ein Modell.

Im Kern des Beweises steht das folgende Ergebnis, das direkt aus dem Gödelschen Vollständigkeitssatz folgt:

Folgt eine Formel   aus einer Formelmenge  , so gibt es eine endliche Menge  , sodass   aus   folgt. (  es gibt endliches   mit  ).

Ein gänzlich anderer Beweis, der auf den Begriff der syntaktischen Herleitbarkeit und auch auf den Vollständigkeitssatz verzichtet, ergibt sich in der Modelltheorie aus dem Satz von Łoś durch Ultraprodukte[1].

Prädikatenlogik zweiter Stufe

Bearbeiten

Aus dem Kompaktheitssatz folgt, dass eine Formelmenge, die ein unendliches Modell hat, auch beliebig große Modelle hat. Denn hat   ein unendliches Modell, dann auch für eine beliebige (unendliche) Indexmenge   auch

 ,

denn jede endliche Menge hat ein Modell. (Die   sind neue Konstantensymbole)

Insbesondere lassen sich mit der Prädikatenlogik erster Stufe nur die endlichen, nicht aber die unendlichen Modelle bis auf Isomorphie charakterisieren.

Die Peano-Axiome beschreiben in der Prädikatenlogik zweiter Stufe aber die natürlichen Zahlen bis auf Isomorphie. Ist   die Menge der Peano-Axiome, so hat   kein Modell, obwohl jede endliche Teilmenge ein Modell hat.

Namensherkunft

Bearbeiten

Betrachtet man den Raum   aller Theorien einer bestimmten Sprache  , die ein Modell besitzen, so kann man diesen Raum mit einer Topologie versehen: Die Basismengen sind die Mengen   von Theorien, die   enthalten. Der Kompaktheitssatz besagt nun gerade, dass dieser Raum topologisch kompakt ist.

Stellung in der Mengenlehre

Bearbeiten

Beim Beweis des Kompaktheitsatzes werden transfinite Methoden wie z. B. das Zornsche Lemma benutzt: Die entscheidende Stelle ist der Satz von Lindenbaum, der es erlaubt, von einer konsistenten Theorie zu einer maximal konsistenten Theorie überzugehen. Anders als z. B. der Satz, dass jeder Vektorraum eine Basis hat, ist der Kompaktheitssatz aber nicht äquivalent zum Zornschen Lemma bzw. dem Auswahlaxiom. Er ist jedoch äquivalent zu einer Reihe von anderen Sätzen wie dem booleschen Primidealsatz.

Literatur

Bearbeiten
  • Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 978-3-8274-1691-9.
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Ultraproducts. Abgerufen am 6. Dezember 2022 (deutsch).