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

Es sei $I$ eine Interpretation mit

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

Nach dem Substitutionslemma bedeutet dies

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

Von der anderen Seite her ist

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

mit dem Substitutionslemma äquivalent zu

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

Dies ist äquivalent zu

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

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

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

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

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

Nach dem Substitutionslemma für Terme ist

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

Dabei ist

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

und somit ist

$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

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

Die Interpretation links nennen wir wieder $J$. Nach dem Substitutionslemma ist

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

Dabei ist

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

und wir haben

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

Daher ist

$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

$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

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

Nach dem Koinzidenzlemma ist dies äquivalent zu

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

da $u$ und $v$

in $\alpha$ nicht vorkommen. Dies stimmt mit der eingangs erzielten Formulierung überein.

Zur gelösten Aufgabe