Kompaktheitssatz (Logik)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Kompaktheit (Logik))
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt den Kompaktheitssatz der mathematischen Logik. Für den Satz aus der Funktionalanalysis siehe Kompaktheitssatz von Riesz.

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.

Beweis[Bearbeiten | Quelltext bearbeiten]

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:

: Gegeben ein Modell von , dann ist es auch ein Modell einer jeden Teilmenge von , also auch aller endlichen.

: Angenommen, jede endliche Menge besitzt ein Modell. Zur Erzeugung eines Widerspruchs wird angenommen, habe kein Modell. Dann ist aus 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 verwendet worden sein. Also ist aus einer endlichen Teilmenge von ein Widerspruch herleitbar, und sie besitzt somit kein Modell (Korrektheitssatz), ein 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. (Ist , so es gibt ein 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ś.

Namensherkunft[Bearbeiten | Quelltext bearbeiten]

Man kann den Raum aller Theorien einer bestimmten Sprache mit einem Modell mit einer Topologie versehen: Die Basismengen sind die . Nach dem Kompaktheitssatz ist ein kompakter Raum.

Stellung in der Mengenlehre[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]