Konstantenexpansion

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Konstantenerweiterung oder Konstantenexpansion ist ein wichtiges Verfahren in der mathematischen Logik. Dabei wird eine Sprache um neue Konstanten erweitert (expandiert), um in der Erweiterung gewisse gewünschte Eigenschaften zu erhalten. Anschließend wird das in der expandierten Sprache Erzielte wieder auf die Ausgangssprache reduziert.[1]

Die Signatur einer Sprache, zum Beispiel der Prädikatenlogik erster oder zweiter Stufe, enthält unter anderem eine möglicherweise leere Menge von Konstantensymbolen. Die Expansion zu einer größeren Menge , wobei und disjunkt seien, erweitert die Ausgangssprache um neue Konstantensymbole aus .

Ist die Ausgangssprache, oft auch mit bezeichnet, wenn die Signatur angegeben werden soll, so wird die Konstantenexpansion um mit bzw. bezeichnet.

Vollständigkeitssatz

[Bearbeiten | Quelltext bearbeiten]

Henkins Beweis des gödelschen Vollständigkeitssatzes konstruiert zu jeder konsistenten Aussagenmenge in einer Sprache der Prädikatenlogik erster Stufe eine Modell. Ein wesentlicher Schritt ist die Hinzunahme einer neuen Konstanten für jede Aussage der Form . Jede dieser neuen Konstanten , deren Gesamtheit mit bezeichnet sei, fungiert als Beispiel für ein Element, das die Existenzaussage erfüllt, genauer erhält man durch Hinzunahme der Aussagen zur gegebenen konsistenten Aussagenmenge wieder eine konsistente Aussagenmenge, von der man die Existenz eines Modells in der Sprache zeigen kann. Dieses Modell ist dann auch in der Sprache ein Modell für die anfangs gegebene konsistente Aussagenmenge, denn diese enthält die neuen Konstanten aus ja nicht. Das ist Henkins Beweis des Vollständigkeitssatzes.[2]

Existenz großer Modelle

[Bearbeiten | Quelltext bearbeiten]

Es sei eine Aussagenmenge einer Sprache der Prädikatenlogik erster Stufe. Wenn es zu jeder natürlichen Zahl ein Modell von gibt, dessen Mächtigkeit größer als diese natürliche Zahl ist, so gibt es Modelle beliebig großer Mächtigkeit. Diese auch als Aufwärtsversion des Satzes von Löwenheim-Skolem bezeichnete Aussage lässt sich wie folgt sehr leicht mittels Konstantenexpansion beweisen. Zu vorgegebener Kardinalzahl wähle Konstanten . Die gegebene Aussagemenge bleibt konsistent, wenn man die Aussagen für je zwei hinzunimmt, denn jede endliche Teilmenge der so erweiterten Aussagenmenge enthält nur endlich viele der Ungleichungen ; dazu gibt es nach Voraussetzung Modelle und der Kompaktheitssatz liefert dann ein Modell für in der Sprache . Jedes solche Modell ist auch ein Modell in der Sprache und hat wegen der Mächtigkeit der hinzugenommenen Konstantenmenge mindestens die Mächtigkeit , womit die Aussage bewiesen ist.[3]

Individuenkonstanten

[Bearbeiten | Quelltext bearbeiten]

Ist ein Modell zu einer Sprache mit Trägermenge , so kann es nützlich sein, für jedes Individuum eine Konstante zu haben. Die durch Hinzunahme sämtlicher Konstanten resultierende Konstantenexpansion wird mit bezeichnet. Die im Modell geltenden Formeln der Sprache sind dann genau die -Aussagen im Modell , wenn jede Individuenkonstante durch interpretiert wird. Diese Sichtweise kommt bei der Diagrammmethode zum Tragen.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Wolfgang Rautenberg: Einführung in die Mathematische Logik. Ein Lehrbuch. 3. Aufl. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, Abschnitt 3.2.
  2. Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 4. Aufl. Spektrum Akademischer Verlag, Heidelberg 1998, ISBN 3-8274-0130-5, Kapitel V: Der Vollständigkeitssatz.
  3. Chen Chung Chang, Howard Jerome Keisler: Model Theory (Studies in Logic and the Foundations of Mathematics, Band 73). Elsevier Science Amsterdam 1990, ISBN 0-444-88054-2, Korollar 2.1.6.