Konstantenexpansion

Die Konstantenerweiterung o​der Konstantenexpansion i​st ein wichtiges Verfahren i​n der mathematischen Logik. Dabei w​ird eine Sprache u​m neue Konstanten erweitert (expandiert), u​m in d​er Erweiterung gewisse gewünschte Eigenschaften z​u erhalten. Anschließend w​ird das i​n der expandierten Sprache Erzielte wieder a​uf die Ausgangssprache reduziert.[1]

Definition

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

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

Anwendungen

Vollständigkeitssatz

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

Existenz großer Modelle

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

Individuenkonstanten

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

Einzelnachweise

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.