Konstantenexpansion

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.

Definition

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

Ist $L$ die Ausgangssprache, oft auch mit $L_{\sigma }$ bezeichnet, wenn die Signatur $\sigma$ angegeben werden soll, so wird die Konstantenexpansion um $C$ mit $L(C)$ bzw. $L_{\sigma }(C)$ bezeichnet.

Anwendungen

Vollständigkeitssatz

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

Existenz großer Modelle

Es sei $T$ eine Aussagenmenge einer Sprache der Prädikatenlogik erster Stufe. Wenn es zu jeder natürlichen Zahl ein Modell von $T$ 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 $\kappa$ wähle Konstanten $c_{\alpha },\alpha <\kappa$ . Die gegebene Aussagemenge bleibt konsistent, wenn man die Aussagen $\neg c_{\alpha }\equiv c_{\beta }$ für je zwei $\alpha <\beta <\kappa$ hinzunimmt, denn jede endliche Teilmenge der so erweiterten Aussagenmenge enthält nur endlich viele der Ungleichungen $\neg c_{\alpha }\equiv c_{\beta }$ ; dazu gibt es nach Voraussetzung Modelle und der Kompaktheitssatz liefert dann ein Modell für $T\cup \{\neg c_{\alpha }\equiv c_{\beta }|\alpha <\beta <\kappa \}$ in der Sprache $L(\{c_{\alpha }|\alpha <\kappa \})$ . Jedes solche Modell ist auch ein Modell in der Sprache $L$ und hat wegen der Mächtigkeit der hinzugenommenen Konstantenmenge mindestens die Mächtigkeit $\kappa$ , womit die Aussage bewiesen ist.

Individuenkonstanten

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

Einzelnachweise

↑ 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.
↑ 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.
↑ 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.