Prädikatenlogik/Koinzidenzlemma/Fakt/Beweis

Beweis

(1). Wir führen Induktion über den Aufbau der ${}U$-Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus ${}U$ betrachten. Für eine Variable ${}x$ (oder eine Konstante) aus ${}U$ ist nach Voraussetzung ${}I_{1}(x)=I_{2}(x)$. Im Induktionsschritt können wir annehmen, dass ein ${}n$-stelliges Funktionssymbol ${}f$ aus ${}U$ gegeben ist sowie ${}U$-Terme ${}t_{1},\ldots ,t_{n}$, für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird ${}f$ in beiden Interpretationen durch die gleiche Funktion ${}f^{M}$ interpretiert. Daher ist

${}{\begin{aligned}I_{1}(ft_{1}\ldots t_{n})&=f^{M}(I_{1}(t_{1}),\ldots ,I_{1}(t_{n}))\\&=f^{M}(I_{2}(t_{1}),\ldots ,I_{2}(t_{n}))\\&=I_{2}(ft_{1}\ldots t_{n}).\end{aligned}}$

(2). Wir führen Induktion über den Aufbau der ${}U$-Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol ${}R$ aus ${}U$ folgt die Aussage unmittelbar aus (1), da ja ${}R$ in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form ${}\neg \alpha ,\,\alpha \wedge \beta ,\,\alpha \rightarrow \beta$ aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein ${}U$-Ausdruck der Form ${}\exists x\alpha$ gegeben, und es gelte ${}I_{1}\vDash \exists x\alpha$. Dies bedeutet aufgrund der Modellbeziehung, dass es ein ${}m\in M$ derart gibt, dass ${}I_{1}{\frac {m}{x}}\vDash \alpha$ gilt. Die beiden umbelegten Interpretationen ${}I_{1}{\frac {m}{x}}$ und ${}I_{2}{\frac {m}{x}}$ stimmen auf den Symbolen aus ${}U$ und den in ${}\alpha$ frei vorkommenden Variablen überein: Die Variable ${}x$ wird so oder so als ${}m$ interpretiert und die anderen freien Variablen aus ${}\alpha$ sind auch in ${}\exists x\alpha$ frei. Nach Induktionsvoraussetzung gilt ${}I_{2}{\frac {m}{x}}\vDash \alpha$ und daher wiederum ${}I_{2}\vDash \exists x\alpha$.

Zur bewiesenen Aussage