Signatur

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 für Relationen,
• ${\displaystyle F}$ ist die Menge der Symbole für Funktionen,
• ${\displaystyle K}$ ist die Menge der Symbole für Konstanten,
• ${\displaystyle Ar}$ ist eine Funktion, die jedem Symbol eine Stelligkeit (engl. arity) zuordnet.

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

Struktur

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}}$ für jedes ${\displaystyle k}$-stellige Relationssymbol aus ${\displaystyle R}$,
• einer ${\displaystyle k}$-stelligen Funktion ${\displaystyle f\subseteq {\mathcal {U}}^{k}\times U}$ für jedes ${\displaystyle k}$-stellige Funktionssymbol aus ${\displaystyle F}$,
• einem Element ${\displaystyle c\in {\mathcal {U}}^{1}}$ für jedes Konstantensymbol aus ${\displaystyle K}$.

Interpretation

Sei ${\displaystyle L}$ eine Sprache mit Variablen, Eigennamen, Termen und Prädikaten. 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 Prädikate auf die übrigen Relationen von ${\displaystyle {\mathcal {A}}}$.

Eine Belegung ist eine Zuordnung

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

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

Modell und die Erfüllbarkeitsrelation

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 erfüllt ist. Symbolisch: ${\displaystyle {\mathcal {A}}\models T}$, gesprochen: ${\displaystyle {\mathcal {A}}}$ erfüllt ${\displaystyle T}$, oder auch, ${\displaystyle T}$ ist wahr in ${\displaystyle {\mathcal {A}}}$.

Modelltheoretische Folgerung

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 für ${\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 für ${\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 vollständig, das heißt, zu jeder Aussage ${\displaystyle \varphi }$ ist entweder ${\displaystyle \varphi \in T}$ oder ${\displaystyle \neg \varphi \in T}$.

Dichte Ordnungen

Die geordnete Menge der rationalen Zahlen ist ein Modell für 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)}$ (Transitivität)
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 vollständig und modellvollständig.
• Alle abzählbaren Modelle sind isomorph (zum Beweis), in überabzählbaren Kardinalzahlen gibt es nicht isomorphe Modelle. In der Sprache der Modelltheorie heißt das: Sie ist ${\displaystyle \omega }$-kategorisch, aber nicht kategorisch in überabzählbaren Kardinalzahlen: Ist ${\displaystyle \kappa }$ eine überabzählbare Kardinalzahl, so hat diese Theorie ${\displaystyle 2^{\kappa }}$ nicht-isomorphe Modelle der Mächtigkeit ${\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.

Einelementige Universen

Das einelementige Universum, das nur die Konstante c enthält, ist ein Modell für das Axiom ${\displaystyle \forall x:x=c}$ über der Signatur ${\displaystyle \sigma =\{c\}}$.

Ein Beispiel für zweielementige Modelle

Wie kann ein Modell für die folgende Menge von Aussagen über ${\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 enthält, die zweite und dritte Aussage zusammen gelten nur, wenn es zwei Elemente enthält. 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}$.)

Nichterfüllbare Axiome

Die Aussagenmenge

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

ist nicht erfüllbar, das heißt, sie hat kein Modell.