Direkt zum Inhalt

Lexikon der Mathematik: Endlichkeitssatz

eine grundlegende Aussage in der Logik über die Widerspruchsfreiheit von Mengen von Ausdrücken.

Um die wichtigsten syntaktischen und semantischen Versionen des Endlichkeitssatzes formulieren zu können, benötigt man einige grundlegende Begriffsbildungen.

Es sei L eine elementare Sprache und Σ eine Menge von Ausdrücken in L. Ein Modell von Σ ist eine algebraische Struktur, in der alle Ausdrücke aus Σ gültig sind (symbolisch \({\mathcal{A}}\models \Sigma \) bzw. \({\mathcal{A}}\models \varphi \), gelesen \({\mathcal{A}}\) ist ein Modell von Σ bzw. von ϕ).

Eine Menge Σ, die ein Modell besitzt, heißt widerspruchsfrei. Ein Ausdruck folgt aus Σ, wenn jedes Modell von Σ auch ein Modell von ϕ ist (symbolisch Σ ⊨ ϕ, gelesen aus Σ folgt ϕ; das Zeichen ⊨ ist also in der mathematischen Logik doppeldeutig!).

Entsprechend den oben gegebenen semantischen Begriffsbildungen betrachten wir jetzt Begriffe, die der Syntax zuzurechnen sind.

Ein Ausdruck ϕ ist aus Σ ableitbar oder formal beweisbar, wenn ein (formaler) Beweis (ϕ1, …, ϕn) für ϕ aus Σ existiert, dies kennzeichnet man durch Σ ⊨ ϕ. Eine Menge Σ heißt konsistent, wenn es keinen Ausdruck ϕ gibt, so daß Σ ⊨ ϕ ∧ ¬ϕ.

Wir können jetzt die verschiedenen Versionen des Endlichkeitssatzes formulieren.

Endlichkeitssatz, semantische Version a)

Σ ⊨ ϕ genau dann, wenn eine endliche Teilmenge Σ0von Σ existiert, so daß Σ0ϕ.

Endlichkeitssatz, semantische Version b)

Σ besitzt genau dann ein Modell, wenn jede endliche Teilmenge Σ0von Σ ein Modell besitzt.

Endlichkeitssatz, syntaktische Version a)

Σ ⊨ ϕ genau dann, wenn eine endliche Teilmenge Σ0von Σ existiert, so daß Σ0ϕ.

Endlichkeitssatz, syntaktische Version b)

Σ ist genau dann konsistent, wenn jede endliche Teilmenge Σ0von Σ konsistent ist.

Der Endlichkeitssatz wird auch häufig Kompaktheitssatz genannt. K. Gödel hat gezeigt, daß für die Prädikatenlogik das inhaltliche Folgern ⊨ mit dem formalen Beweisen ⊢ übereinstimmt, d. h., \begin{eqnarray}{\rm{\Sigma }}\models \varphi \iff {\rm{\Sigma }} \vdash \varphi.\end{eqnarray}

Damit sind die verschiedenen Versionen des Endlichkeitssatzes zueinander äquivalent.

Der Endlichkeitssatz ist ein wichtiges Hilfsmittel der mathematischen Logik insbesondere beim Nachweis der Existenz gewisser Modelle mit z.T. verblüffenden Eigenschaften.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos