Prädikatenlogik/Zweifache Substitution/Einfache Substitution/Semantik/Aufgabe/Lösung

Es sei ${\displaystyle {}I}$ eine Interpretation mit

${\displaystyle I\vDash \alpha {\frac {s,t}{x,y}}.}$

Nach dem Substitutionslemma bedeutet dies

${\displaystyle I{\frac {I(s),I(t)}{x,y}}\vDash \alpha .}$

Von der anderen Seite her ist

${\displaystyle I\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}{\frac {y}{v}}}$

mit dem Substitutionslemma äquivalent zu

${\displaystyle I{\frac {I(y)}{v}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}.}$

Dies ist äquivalent zu

${\displaystyle I{\frac {I(y)}{v}}{\frac {I{\frac {I(y)}{v}}(x)}{u}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}},}$

und wegen ${\displaystyle {}I{\frac {I(y)}{v}}(x)=I(x)}$ kann man dies als

${\displaystyle I{\frac {I(y),I(x)}{v,u}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}}$

schreiben. Wir nennen die Interpretation links ${\displaystyle {}J}$. Mit dem Substitutionslemma ist dies äquivalent zu

${\displaystyle J{\frac {J(t{\frac {u}{x}})}{y}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}.}$

Nach dem Substitutionslemma für Terme ist

${\displaystyle {}J{\left(t{\frac {u}{x}}\right)}=J{\frac {J(u)}{x}}(t)\,.}$

Dabei ist

${\displaystyle {}J(u)={\left(I{\frac {I(y),I(x)}{v,u}}\right)}(u)=I(x)\,}$

und somit ist

${\displaystyle {}J{\frac {J(u)}{x}}(t)={\left(I{\frac {I(y),I(x)}{v,u}}\right)}{\frac {I(x)}{x}}(t)={\left(I{\frac {I(y),I(x)}{v,u}}\right)}(t)=I(t)\,.}$

Zusammengefasst ist also

${\displaystyle I{\frac {I(y),I(x),I(t)}{v,u,y}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}.}$

Die Interpretation links nennen wir wieder ${\displaystyle {}J}$. Nach dem Substitutionslemma ist

${\displaystyle J{\frac {J{\left(s{\frac {v}{y}}\right)}}{x}}\vDash \alpha .}$

Dabei ist

${\displaystyle {}J{\left(s{\frac {v}{y}}\right)}={\left(J{\frac {J(v)}{y}}\right)}(s)\,}$

und wir haben

${\displaystyle {}J(v)={\left(I{\frac {I(y),I(x),I(t)}{v,u,y}}\right)}(v)=I(y)\,.}$

Daher ist

${\displaystyle {}J{\left(s{\frac {v}{y}}\right)}=J{\frac {I(y)}{y}}(s)=I{\frac {I(y),I(x),I(t)}{v,u,y}}{\frac {I(y)}{y}}(s)=I{\frac {I(y),I(x),I(t)}{v,u,y}}(s)=I(s)\,.}$

Also ist insgesamt

${\displaystyle {}J{\frac {J{\left(s{\frac {v}{y}}\right)}}{x}}=J{\frac {I(s)}{x}}=I{\frac {I(y),I(x),I(t)}{v,u,y}}{\frac {I(s)}{x}}=I{\frac {I(y),I(x),I(s),I(t)}{v,u,x,y}}\,}$

und

${\displaystyle I{\frac {I(y),I(x),I(s),I(t)}{v,u,x,y}}\vDash \alpha .}$

Nach dem Koinzidenzlemma ist dies äquivalent zu

${\displaystyle I{\frac {I(s),I(t)}{x,y}}\vDash \alpha ,}$

da ${\displaystyle {}u}$ und ${\displaystyle {}v}$

${\displaystyle {}\alpha }$