Die Modelltheorie ist ein Teilgebiet der mathematischen Logik . Inhalt der Modelltheorie sind die Beziehungen zwischen den rein formalen Ausdrucken einer Sprache ( syntaktische Ebene ) und deren Bedeutung ( semantische Ebene ). Diese Beziehung wird uber sogenannte Interpretationen und eine als Erfullungsrelation bezeichnete mathematische Relation hergestellt.

Ganz allgemein gesprochen beschaftigt sich die Modelltheorie mit der Konstruktion und der Klassifikation von allen (moglichen) Strukturen und Klassen von Strukturen, im Besonderen mit solchen Strukturen, die axiomatisierbaren Sprachen oder Theorien entsprechen. Dabei geht es u. a. um die Aufgabe, Modelle fur ein vorgegebenes Axiomensystem zu konstruieren ? oft geht es um Modelle mit zusatzlichen Eigenschaften, die im Axiomensystem aber nicht spezifiziert werden konnen, z. B. die Kardinalitat des Modells. Weiterhin beschaftigt sich die Modelltheorie mit der Aquivalenz von Modellen , etwa der Frage, ob in ihnen die gleichen Aussagen gelten, und der Frage, wie viele (nichtisomorphe) Modelle eines Axiomensystems es gibt.

Ein Modell im Sinn der Modelltheorie ist eine mit einer gewissen Struktur versehene Menge (Universum, Individuenbereich, Tragermenge oder Domane genannt), auf die eine Menge von Aussagen zutrifft.

Dass die Tragermenge ${\displaystyle ~{\mathcal {U}}~}$ eine Struktur habe, bedeutet, dass gewisse Relationen auf ${\displaystyle ~{\mathcal {U}}~}$ definiert sind, also Teilmengen kartesischer Produkte ${\displaystyle ~{\mathcal {U}}^{k},~k\in \mathbb {N} }$. Das Tupel aus Universum ${\displaystyle ~{\mathcal {U}}~}$ und den Relationen heißt Struktur. Eine Struktur heißt Modell einer Aussage, falls die Aussage als eine Aussage uber die Struktur interpretierbar ist und dort erfullt wird.

Beispiel. Zu den einfachsten Strukturen zahlen Graphen . Ein Graph ${\displaystyle G}$ ist ein Tupel ${\displaystyle G=(V,E)}$ mit ${\displaystyle E\subseteq V^{2}}$. Das Universum ware hier ${\displaystyle V}$ und die (in diesem Fall einzige) Relation ware ${\displaystyle E}$. Um eine Aussage wie ?Julian und Chelsea sind Freunde“ in ${\displaystyle G}$ zu interpretieren, konnte man (in diesem Fall musste man, da es keine andere Relation gibt) ${\displaystyle E}$ als Freundschaftsrelation interpretieren; Julian und Chelsea mussten mit Individuen ${\displaystyle v_{1},v_{2}}$ aus dem Universum ${\displaystyle V}$ identifiziert werden. Falls dann ${\displaystyle (v_{1},v_{2})\in E}$, ware die Aussage in der Struktur ${\displaystyle (V,E)}$ erfullt und ${\displaystyle G}$ ware ein Modell fur die Aussage. Falls aber ${\displaystyle E}$ leer ware, gabe es keine Moglichkeit, ${\displaystyle v_{1},v_{2}}$ so zu wahlen, dass sie Freunde sind, und die Aussage ware in dieser Struktur ${\displaystyle G=(V,E)}$ nicht erfullt.

Allgemeiner wird nicht nur eine Aussage, sondern eine Menge von Aussagen in einer Sprache betrachtet. Die Modelltheorie beschaftigt sich mit den Fragen, welche Modelle jede Aussage der Menge erfullen und ob die Menge uberhaupt ein Modell hat.

Die erste Schwierigkeit ist die Entscheidung, welche Strukturen fur die Aussagen einer Sprache als Modelle in Frage kommen. Dafur wurde der Begriff der Signatur eingefuhrt, der jeden Aussagensatz der Sprache in Subjekt und Pradikat aufzuteilen sucht. Subjekte konnten Eigennamen (jede Sprache spricht uber gewisse Objekte und benutzt manchmal dafur Eigennamen), Variablen (sozusagen Pronomen, sie sind keine Eigennamen, beziehen sich aber auf die Objekte, uber die die Sprache spricht) oder Terme (andere mogliche Subjekte) sein. Die Grundidee in der Modelltheorie ist,

• Variablen mit nullstelligen Relationen,
• Eigennamen mit einstelligen Relationen, die nur ein Element enthalten,
• Terme mit Funktionen (das sind linkstotale, rechtseindeutige Relationen) und
• Pradikate mit den ubrigen Relationen

zu assoziieren. Wie allgemein die Definitionen gemacht werden, hangt vom Kontext ab: In der Kategorientheorie versucht man sehr allgemein vorzugehen, in der Informatik deutlich weniger allgemein, in der Mathematik beschrankt man sich oft auf eine einzige Sprache (die Pradikatenlogik erster Stufe). Daher gibt es keine einheitlichen Definitionen, fur Details sei auf die Haupteintrage verwiesen.

Eine Signatur ${\displaystyle \sigma }$ ist ein Tupel ${\displaystyle \sigma =(R,F,K,Ar)}$ bestehend aus drei Mengen und einer Funktion.

• ${\displaystyle R}$ ist die Menge der Symbole fur Relationen,
• ${\displaystyle F}$ ist die Menge der Symbole fur Funktionen,
• ${\displaystyle K}$ ist die Menge der Symbole fur Konstanten,
• ${\displaystyle Ar}$ ist eine Funktion, die jedem Symbol eine Stelligkeit (engl. arity ) zuordnet.

Die Mengen ${\displaystyle R,F}$ und ${\displaystyle K}$ mussen paarweise disjunkt sein, durfen aber auch leer sein. Im Prinzip durfen sie auch unendlich sein, aber in aller Regel sind sie endlich. Die Elemente aus ${\displaystyle R\cup F\cup K}$ nennt man nichtlogische Symbole .

Sei ${\displaystyle \sigma =(R,F,K,Ar)}$ eine Signatur. Eine ${\displaystyle \sigma }$- Struktur ${\displaystyle {\mathcal {A}}}$ ist ein Tupel bestehend aus:

• einer nichtleeren Menge ${\displaystyle {\mathcal {U}}}$, dem Universum ,
• einer ${\displaystyle k}$-stelligen Relation ${\displaystyle r\subseteq {\mathcal {U}}^{k}}$ fur jedes ${\displaystyle k}$-stellige Relationssymbol aus ${\displaystyle R}$,
• einer ${\displaystyle k}$-stelligen Funktion ${\displaystyle f\subseteq {\mathcal {U}}^{k}\times U}$ fur jedes ${\displaystyle k}$-stellige Funktionssymbol aus ${\displaystyle F}$,
• einem Element ${\displaystyle c\in {\mathcal {U}}^{1}}$ fur jedes Konstantensymbol aus ${\displaystyle K}$.

Sei ${\displaystyle L}$ eine Sprache mit Variablen, Eigennamen, Termen und Pradikaten. Eine Interpretation von ${\displaystyle w\in L}$ in einer Struktur ${\displaystyle {\mathcal {A}}}$ ist eine Zuordnung

• der Individuennamen auf die Konstanten von ${\displaystyle {\mathcal {A}}}$,
• der Terme auf die Funktionen von ${\displaystyle {\mathcal {A}}}$,
• der Pradikate auf die ubrigen Relationen von ${\displaystyle {\mathcal {A}}}$.

Eine Belegung ist eine Zuordnung

• der Variablen auf das Universum von ${\displaystyle {\mathcal {A}}}$.

Eine Interpretation ist also moglich, falls die Sprache zur Signatur passt. Durch die Interpretation und die Belegung wird ${\displaystyle w}$ zu einer Aussage uber die Struktur ${\displaystyle {\mathcal {A}}}$. Meistens wird die Belegung als Teil der Interpretation definiert.

Sei ${\displaystyle L}$ eine beliebige Sprache und ${\displaystyle T\subseteq L}$ eine Teilmenge der Sprache. Eine Struktur ${\displaystyle {\mathcal {A}}}$ heißt Modell von ${\displaystyle T}$, falls es eine Interpretation (mit einer Belegung) gibt, sodass jedes Element aus ${\displaystyle T}$ einer Aussage entspricht, die in der Struktur erfullt ist. Symbolisch: ${\displaystyle {\mathcal {A}}\models T}$, gesprochen: ${\displaystyle {\mathcal {A}}}$ erfullt ${\displaystyle T}$, oder auch, ${\displaystyle T}$ ist wahr in ${\displaystyle {\mathcal {A}}}$.

Man sagt, eine Aussage ${\displaystyle \phi _{2}}$ folge modelltheoretisch aus einer Aussage ${\displaystyle \phi _{1}}$, falls jedes Modell von ${\displaystyle \phi _{1}}$ auch ein Modell fur ${\displaystyle \phi _{2}}$ ist; symbolisch: ${\displaystyle \phi _{1}\models \phi _{2}}$.

Die Folgerungsrelation ${\displaystyle \models }$ wird dann auf beliebige Aussagemengen erweitert: Eine Aussagenmenge ${\displaystyle \Phi _{2}}$ folgt modelltheoretisch aus einer Aussagenmenge ${\displaystyle \Phi _{1}}$, falls jedes Modell von ${\displaystyle \Phi _{1}}$ ein Modell fur ${\displaystyle \Phi _{2}}$ ist; symbolisch: ${\displaystyle \Phi _{1}\models \Phi _{2}}$.

Unter der Theorie eines Modells versteht man die Menge aller Aussagen, die in ihm gelten. Jede Theorie ${\displaystyle T}$ eines Modells ist vollstandig , das heißt, zu jeder Aussage ${\displaystyle \varphi }$ ist entweder ${\displaystyle \varphi \in T}$ oder ${\displaystyle \neg \varphi \in T}$.

• Eine Axiomenmenge lasst sich oft einfacher als Theorie eines Modells angeben als in einer aufzahlenden Form.
• Die Existenz eines Modells beweist, dass sich die Axiome nicht widersprechen, sie sind also konsistent. Eine Logik hat die Eigenschaft der Vollstandigkeit, falls umgekehrt jede konsistente Aussagenmenge ein Modell hat (dies gilt fur die Pradikatenlogik erster Stufe , siehe weiter unten ).
• Existieren sowohl Modelle mit einer gewissen Eigenschaft als auch solche, die diese Eigenschaft nicht haben, so ist damit die logische Unabhangigkeit der Eigenschaft von den Axiomen bewiesen, d. h., diese Eigenschaft folgt nicht aus den Axiomen und lasst sich auch nicht auf Grundlage der Axiome widerlegen.
• Jeder Satz einer formalen Sprache induziert eine Menge endlicher Modelle, die ihn erfullen. So kann man jede Sprache als die Vereinigung aller Modelle, die von den Satzen der Sprache erfullt werden, betrachten. Eine Sprache heißt dann in einer Logik definierbar, wenn es einen Satz der Logik gibt, der von derselben Menge von Modellen erfullt wird. In der deskriptiven Komplexitatstheorie wird der Zusammenhang zwischen der Komplexitatsklasse einer Sprache und ihrer Definierbarkeit in gewissen Logiken untersucht.

Die geordnete Menge der rationalen Zahlen ist ein Modell fur die Axiome der dichten offenen strengen Totalordnungen :

1. ${\displaystyle \forall x,y(x<y\vee x=y\vee y<x)}$ (Trichotomie)
2. ${\displaystyle \forall x,y[x<y\rightarrow \neg (y<x)]}$ (Antisymmetrie)
3. ${\displaystyle \forall x,y,z(x<y\wedge y<z\rightarrow x<z)}$ (Transitivitat)
4. ${\displaystyle \forall x\exists y,z(y<x\wedge x<z)}$ (Offenheit)
5. ${\displaystyle \forall x,y[x<y\rightarrow \exists z(x<z\wedge z<y)]}$ (Dichtheit)

Die geordnete Menge der reellen Zahlen und alle Teilmengen der reellen Zahlen, die die rationalen Zahlen enthalten, sind Modelle. Die Theorie der dichten offenen strengen Totalordnungen ist ein Standardbeispiel in der Modelltheorie. Sie hat u. a. folgende Eigenschaften:

• Sie ist endlich axiomatisierbar, hat aber keine endlichen Modelle.
• Sie ist vollstandig und modellvollstandig .
• Alle abzahlbaren Modelle sind isomorph (zum Beweis ), in uberabzahlbaren Kardinalzahlen gibt es nicht isomorphe Modelle. In der Sprache der Modelltheorie heißt das: Sie ist ${\displaystyle \omega }$- kategorisch , aber nicht kategorisch in uberabzahlbaren Kardinalzahlen: Ist ${\displaystyle \kappa }$ eine uberabzahlbare Kardinalzahl, so hat diese Theorie ${\displaystyle 2^{\kappa }}$ nicht-isomorphe Modelle der Machtigkeit ${\displaystyle \kappa }$.
• Sie ist der (eindeutig bestimmte) Modellbegleiter der Theorie der linearen Ordnung.
• Sie besitzt mit den rationalen Zahlen ein Primmodell . (Das ist ein Modell, das in jedes andere Modell elementar eingebettet werden kann.)
• Jedes Modell ist atomar .
• Sie hat Quantorenelimination .
• Sie ist nicht stabil .

Das einelementige Universum, das nur die Konstante c enthalt, ist ein Modell fur das Axiom ${\displaystyle \forall x:x=c}$ uber der Signatur ${\displaystyle \sigma =\{c\}}$.

Wie kann ein Modell fur die folgende Menge von Aussagen uber ${\displaystyle \sigma =\{c,R\}}$ aussehen ( ${\displaystyle c}$ sei eine Konstante, ${\displaystyle R}$ sei eine zweistellige Relation)?

1. ${\displaystyle \forall x,y,z\,[(x=y)\vee (y=z)\vee (x=z)]}$
2. ${\displaystyle \exists x,y\,xRy}$
3. ${\displaystyle \neg \exists x\,xRx}$
4. ${\displaystyle \forall x,y\,[xRy\rightarrow \neg (yRx)]}$

Die erste Aussage bestimmt, dass das Universum maximal zwei Elemente enthalt, die zweite und dritte Aussage zusammen gelten nur, wenn es zwei Elemente enthalt. Es gibt bis auf Isomorphie nur zwei Modelle (wobei wir das Universum ${\displaystyle U=\{a,b\}}$ zugrunde legen):

${\displaystyle M_{1}:}$ ${\displaystyle U=\{a,b\},}$ ${\displaystyle c=a,}$ ${\displaystyle R=\{(a,b)\}}$ und

${\displaystyle M_{2}:}$ ${\displaystyle U=\{a,b\},}$ ${\displaystyle c=a,}$ ${\displaystyle R=\{(b,a)\}}$

Das Modell

${\displaystyle M_{3}:}$ ${\displaystyle U=\{a,b\},}$ ${\displaystyle c=b,}$ ${\displaystyle R=\{(a,b)\}}$

ist isomorph zu ${\displaystyle M_{2}}$. (Es gibt eine Isomorphie, die ${\displaystyle a}$ auf ${\displaystyle b}$ abbildet und ${\displaystyle b}$ auf ${\displaystyle a}$.)

Die Aussagenmenge

1. ${\displaystyle \forall x\,xRx}$
2. ${\displaystyle \exists x\,\neg (xRx)}$

ist nicht erfullbar, das heißt, sie hat kein Modell.

Es konnten Kriterien fur Aussagenmengen der Pradikatenlogik erster Stufe gefunden werden, die die Existenz von Modellen garantieren.

• So besagt etwa der Godelsche Vollstandigkeitssatz , dass jede syntaktisch konsistente Theorie (also jede Menge von geschlossenen Formeln, aus der kein logischer Widerspruch herleitbar ist) ein Modell hat.
• Der Kompaktheitssatz besagt, dass ein (unendliches) Axiomensystem genau dann ein Modell hat, falls jedes endliche Teilsystem ein Modell hat.
• Der Satz von Lowenheim-Skolem sagt daruber hinaus aus, dass jede Theorie (in einer abzahlbaren Sprache der Pradikatenlogik), die uberhaupt ein unendliches Modell hat, auch ein Modell jeder unendlichen Kardinalitat hat.

Die Endliche Modelltheorie ist ein Teilbereich der Modelltheorie, der auf die Eigenschaften logischer Sprachen (wie etwa der Pradikatenlogik ) sowie auf endliche Strukturen wie etwa endliche Gruppen, Graphen und die meisten Maschinenmodelle fokussiert ist. Ein Schwerpunkt liegt dabei insbesondere in den Beziehungen zwischen logischen Sprachen und der Berechenbarkeitstheorie . Weiterhin bestehen enge Bezuge zur diskreten Mathematik , zur Komplexitatstheorie und zur Theorie der Datenbanken .

Typische Fragen in der endlichen Modelltheorie sind, zu welchen Kardinalitaten sich fur ein gegebenes Axiomensystem Modelle schaffen lassen. So ist diese Frage fur die Korperaxiome vollstandig geklart: Primzahlen und Primzahlpotenzen sind die alleinigen Kardinalitaten endlicher Modelle. Diese Menge naturlicher Zahlen heißt dann Spektrum der Korperaxiome .

Es ist bisher ungeklart, ob das Komplement eines Spektrums stets wieder ein Spektrum ist: Gesucht ist also eine Axiomenmenge dergestalt, dass alle endlichen Modelle eine Kardinalitat im Komplement des Spektrums besitzen. Diese Frage hangt auch mit dem P-NP-Problem aus der Komplexitatstheorie zusammen.

Die Ursprunge der Modelltheorie finden sich in der Algebra des 19. Jahrhunderts, so wie sie im umfangreichen Werk von Ernst Schroder : Vorlesungen uber die Algebra der Logik (1890?1905) dargestellt wird. Zentral war der Individuenbereich (damals auch Denkbereich genannt), auf den man einen algebraisch Ausdruck anwandte. Schroder fuhrte auch den Begriff der Struktur ein. Aber die Begriffe blieben undefiniert. Diese Tradition setzte sich selbst bei logisch-axiomatisch veranlagten Mathematikern wie Ernst Zermelo fort, der bei der Axiomatisierung der Mengenlehre den Begriff Individuenbereich ebenfalls ohne Definition lasst, obwohl seine Axiomatisierung auf dem Begriff grundete. Selbst Albert Thoralf Skolem , der einige Begriffe Zermelos zu prazisieren suchte, verwendete den Begriff ohne weitere Erklarung.

Der wohl erste Versuch einer Formalisierung findet sich bei Rudolf Carnap. Aber die moderne Modelltheorie weicht in wichtigen Punkten von seiner Auffassung ab. Er bezog Modelle (wie damals ublich) auf Axiomensysteme und nicht auf Aussagenmengen, sodass ein Axiomensystem schon dann ein Modell hatte, wenn die Axiome des Systems erfullt sind. Das ist aus wichtigen Grunden in der modernen Auffassung nicht mehr notwendig. Carnap verstand unter einem Modell fur die axiomatischen Grundzeichen eines gegebenen Axiomensystems bezuglich eines gegebenen Individuenbereichs ${\displaystyle ~{\mathcal {U}}~}$ Folgendes: eine Bewertung fur diese Zeichen derart, dass sowohl der Bereich ${\displaystyle ~{\mathcal {U}}~}$ als auch die Bewertung ohne Gebrauch deskriptiver Konstanten angegeben wird. Ein Modell fur die Grundzeichen heißt ein Modell fur ein Axiomensystem, wenn es alle Axiome erfullt, d. h., wahr macht. ^[1]

Der Durchbruch zum modernen Verstandnis kam durch Alfred Tarski, der die Semantik eines Axiomensystems von seiner Syntax trennte und der Semantik den Vorrang vor der Syntax einraumte: Eine syntaktische Folgerung ist korrekt, wenn sie semantisch erfullt ist. Als weitere wichtige Meilensteine gelten die Herbrand-Struktur von Jacques Herbrand (1930) und die Wahrheitsdefinition von Tarski und Robert Vaught in Arithmetical extensions of relational systems (1956), die einige Unzuganglichkeiten von Tarskis ursprungliche Wahrheitsdefinition der 1930er Jahre aufhob. Besonders wichtig fur die Anwendungen in der Algebra waren die Arbeiten von Anatoli Malzew , der bereits ab 1936 Sprachen mit uberabzahlbar vielen logischen Symbolen einbezog.

• Godelscher Vollstandigkeitssatz
• Relativierung (Mengenlehre)
• Deskriptive Komplexitatstheorie

• C. C. Chang, H. J. Keisler: Model Theory. Studies in Logic and the Foundations of Mathematics, Band 73, Elsevier Science, 1990, ISBN 0-444-88054-2 .
• Wilfrid Hodges : Model Theory. Cambridge University Press, 1993, ISBN 0-521-30442-3 .
• Dirk W. Hoffmann : Grenzen der Mathematik. Springer Spektrum, 3. Auflage, Berlin 2018, ISBN 978-3-662-56616-9 , Kapitel 7: Modelltheorie.
• David Marker: Model Theory: an introduction. Springer Verlag, New York 2002, ISBN 9780387987606 .
• Wolfgang Rautenberg : Einfuhrung in die mathematische Logik. Vieweg Teubner, 3. Auflage, Wiesbaden 2008, ISBN 978-3-8348-0578-2 , Kapitel 5: Elemente der Modelltheorie.
• Philipp Rothmaler: Einfuhrung in die Modelltheorie. Spektrum Akademischer Verlag, 1995, ISBN 978-3-86025-461-5 .
• Wolfram Schwabhauser : Modelltheorie I. BI Hochschultaschenbucher Band 813, Bibliographisches Institut Mannheim 1971.
• Wolfram Schwabhauser: Modelltheorie II. BI Hochschultaschenbucher Band 815, Bibliographisches Institut Mannheim 1972.
• Herbert Stachowiak: Allgemeine Modelltheorie. Springer Verlag, Wien / New York 1973, ISBN 3-211-81106-0 .

• Wilfrid Hodges:  Model Theory. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy .
• Wilfrid Hodges:  First Order Model Theory. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy .
• Jouko Vaananen. A Short Course on Finite Model Theory (PDF; 221 kB). Department of Mathematics, University of Helsinki. Auf der Basis von Vorlesungen in den Jahren 1993?1994.
• William Weiss, Cherie D‘Mello: Fundamentals of Model Theory
• Finite Model Theory Homepage der RWTH Aachen, inklusive einer Liste offener Probleme.
• Finite Model Theory References ( Memento vom 4. Februar 2006 im Internet Archive ), eine Datenbank mit Bezugen zur Endlichen Modelltheorie.
• Modelltheorie im Lexikon der Mathematik auf Spektrum.de

1. ↑ Rudolf Carnap: Einfuhrung in die symbolische Logik. 3. Auflage. Springer, Wien / New York 1968, S. 174.