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

Es sei ${}I$ eine Interpretation mit

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

Nach dem Substitutionslemma bedeutet dies

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

Von der anderen Seite her ist

$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

$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

$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 ${}I{\frac {I(y)}{v}}(x)=I(x)$ kann man dies als

$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 ${}J$. Mit dem Substitutionslemma ist dies äquivalent zu

$J{\frac {J(t{\frac {u}{x}})}{y}}\vDash \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}}\vDash \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}}\vDash \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}}\vDash \alpha .$

Nach dem Koinzidenzlemma ist dies äquivalent zu

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

da ${}u$ und ${}v$

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

Zur gelösten Aufgabe