Logik/Vollständigkeitssatz/Modellkonstruktion/Konstruktion

Es sei ${\displaystyle {}\Gamma }$ eine Menge an ${\displaystyle {}S}$-Ausdrücken (über einem Symbolalphabet ${\displaystyle {}S}$), die abgeschlossen unter Ableitungen ist. Dann definiert man auf der Menge aller ${\displaystyle {}S}$-Terme eine Äquivalenzrelation durch

${\displaystyle t\sim s{\text{ genau dann, wenn der Ausdruck }}t=s{\text{ zu }}\Gamma {\text{ gehört}}.}$

Es sei ${\displaystyle {}M}$ die Menge der Termklassen (also die Menge der Äquivalenzklassen zu dieser Äquivalenzrelation). Auf ${\displaystyle {}M}$ definiert man für jedes ${\displaystyle {}n}$-stellige Relationssymbol ${\displaystyle {}R}$ eine ${\displaystyle {}n}$-stellige Relation ${\displaystyle {}R^{M}}$ durch

${\displaystyle R^{M}([t_{1}],[t_{2}],\ldots ,[t_{n}]){\text{ genau dann, wenn der Ausdruck }}Rt_{1}t_{2}\cdots t_{n}{\text{ zu }}\Gamma {\text{ gehört}}}$

und für jedes ${\displaystyle {}n}$-stellige Funktionssymbol ${\displaystyle {}f}$ eine ${\displaystyle {}n}$-stellige Funktion ${\displaystyle {}f^{M}}$ durch

${\displaystyle {}f^{M}([t_{1}],[t_{2}],\ldots ,[t_{n}]):=[ft_{1}t_{2}\cdots t_{n}]\,.}$

Konstanten werden als

${\displaystyle {}c^{M}:=[c]\,}$

interpretiert.