Dies wird über den induktiven Aufbau der Terme bzw. der Ausdrücke bewiesen. (1). Für eine Konstante ${\displaystyle {}c}$ ist die Aussage richtig, da ihre Interpretation unverändert ist. Für eine Variable ${\displaystyle {}x}$ macht man eine Fallunterscheidung. Wenn

${\displaystyle {}x=x_{i}\,}$

mit einer der an der Substitution beteiligten Variablen ist, so ist

${\displaystyle {}I{\left(x_{i}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}=I(t_{i})={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(x_{i})\,.}$

Bei einer an der Substitution nicht beteiligten Variablen ${\displaystyle {}x}$ ist

${\displaystyle {}I{\left(x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}=I(x)={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(x)\,.}$

Wenn ${\displaystyle {}f}$ ein ${\displaystyle {}n}$-stelliges Funktionssymbol ist und ${\displaystyle {}s_{1},\ldots ,s_{n}}$ Terme sind, für die die Gleichheit schon bekannt ist, so ist

${\displaystyle {}{\begin{aligned}I{\left({\left(fs_{1}\ldots s_{n}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}&=I{\left(fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}\\&=I(f){\left(I{\left(s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)},\ldots ,I{\left(s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}\right)}\\&=I(f){\left({\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s_{1}),\ldots ,{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s_{n})\right)}\\&={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(f){\left({\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}{\left(s_{1}\right)},\ldots ,{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}{\left(s_{n}\right)}\right)}\\&={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}{\left(fs_{1}\ldots s_{n}\right)}.\end{aligned}}}$

(2). Für einen Ausdruck der Form ${\displaystyle {}s=t}$ bedeutet

${\displaystyle I\vDash {\left(s=t\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$

einfach

${\displaystyle I\vDash s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=t{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.}$

Dies ist äquivalent zu

${\displaystyle {}I{\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}=I{\left(t{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}\,,}$

was nach dem ersten Teil einfach

${\displaystyle {}I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}(s)=I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}(t)\,}$

bedeutet. Dies wiederum ist äquivalent zu

${\displaystyle I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\vDash s=t.}$

Sei nun ${\displaystyle {}R}$ ein ${\displaystyle {}n}$-stelliges Relationssymbol und seien ${\displaystyle {}s_{1},\ldots ,s_{n}}$ Terme. Die Gültigkeit

${\displaystyle I\vDash {\left(Rs_{1}\ldots s_{n}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$

bedeutet

${\displaystyle I\vDash Rs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$

und dies bedeutet, dass

${\displaystyle {\left(I{\left(s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)},\ldots ,I{\left(s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}\right)}}$

zur Relation ${\displaystyle {}I(R)}$ gehört. Nach dem ersten Teil ist dieses Tupel gleich

${\displaystyle {\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}(s_{1}),\ldots ,I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}(s_{n})\right)}.}$

Wegen ${\displaystyle {}R(I)=R{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}}$ ist dies äquivalent zu

${\displaystyle I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\vDash Rs_{1}\ldots s_{n}.}$

Für die weiteren Aussagen beweist man die Äquivalenz durch Induktion über den Aufbau der Ausdrücke, und zwar über alle Interpretationen simultan; dies ist für die aussagenlogischen Junktoren unmittelbar klar. Betrachten wir also einen Ausdruck der Form ${\displaystyle {}\forall x\alpha }$. Die Gültigkeit

${\displaystyle I\vDash {\left(\forall x\alpha \right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$

bedeutet gemäß der Festlegung in Definition, dass

${\displaystyle I\vDash \forall v\alpha {\frac {t_{i_{1}},\ldots ,t_{i_{r}},v}{x_{i_{1}},\ldots ,x_{i_{r}},x}}}$

gilt, wobei ${\displaystyle {}v}$ in ${\displaystyle {}t_{i_{1}},\ldots ,t_{i_{r}}}$ nicht vorkommt. Dies bedeutet, dass für jedes ${\displaystyle {}m\in M}$ der Grundmenge der Interpretation die Beziehung

${\displaystyle I{\frac {m}{v}}\vDash \alpha {\frac {t_{i_{1}},\ldots ,t_{i_{r}},v}{x_{i_{1}},\ldots ,x_{i_{r}},x}}}$

gilt. Nach Induktionsvoraussetzung (angewendet auf die Interpretation ${\displaystyle I{\frac {m}{v}}}$) bedeutet dies

${\displaystyle {\left(I{\frac {m}{v}}\right)}{\frac {{\left(I{\frac {m}{v}}\right)}{\left(t_{i_{1}}\right)},\ldots ,{\left(I{\frac {m}{v}}\right)}{\left(t_{i_{r}}\right)},{\left(I{\frac {m}{v}}\right)}{\left(v\right)}}{x_{i_{1}},\ldots ,x_{i_{r}},x}}\vDash \alpha }$

für alle ${\displaystyle {}m\in M}$. Aufgrund des Koinzidenzlemmas ist dies äquivalent zu

${\displaystyle {\left(I{\frac {m}{v}}\right)}{\frac {I{\left(t_{i_{1}}\right)},\ldots ,I{\left(t_{i_{r}}\right)},m}{x_{i_{1}},\ldots ,x_{i_{r}},x}}\vDash \alpha .}$

Dies ist äquivalent (für alle ${\displaystyle m\in M}$) zu

${\displaystyle I{\frac {I{\left(t_{i_{1}}\right)},\ldots ,I{\left(t_{i_{r}}\right)},m}{x_{i_{1}},\ldots ,x_{i_{r}},x}}\vDash \alpha ,}$

was bei ${\displaystyle {}v=x}$ klar ist und bei ${\displaystyle {}v\neq x}$ aus dem Koinzidenzlemma folgt, da dann ${\displaystyle {}v}$ nicht in ${\displaystyle {}\alpha }$ vorkommt. Dies bedeutet wiederum

${\displaystyle I{\frac {I{\left(t_{i_{1}}\right)},\ldots ,I{\left(t_{i_{r}}\right)}}{x_{i_{1}},\ldots ,x_{i_{r}}}}\vDash \forall x\alpha }$

und damit

${\displaystyle I{\frac {I{\left(t_{1}\right)},\ldots ,I{\left(t_{k}\right)}}{x_{1},\ldots ,x_{k}}}\vDash \forall x\alpha .}$