Registermaschine/Programm/Arithmetische Repräsentierung/Fakt/Beweis

Beweis

Die Variablen ${}z,z',r_{j},r_{j}'$ seien durch die natürlichen Zahlen ${}\ell ,\ell ',n_{j},n_{j}'$ belegt. Wir müssen zeigen, dass die Gleichheit

${}\varphi _{P}(\ell ,n_{1},\ldots ,n_{m})=(\ell ',n'_{1},\ldots ,n'_{m})\,$

genau dann gilt, wenn

$\mathbb {N} \vDash A_{P}(\ell ,\ell ',n_{1},\ldots ,n_{m},n'_{1},\ldots ,n'_{m})$

gilt. Der Ausdruck ${}A_{P}$ gilt genau dann, wenn sämtliche Ausdrücke ${}A_{1},A_{2},\ldots ,A_{h},A_{h+1}$ gelten. Es sei ${}\ell$ fixiert. Dann gelten sämtliche ${}A_{k}$, ${}k\neq \ell$, automatisch, da für diese Ausdrücke der Vordersatz nicht gilt. Die Gültigkeit von ${}A_{P}$ bei dieser Belegung bedeutet also, dass der Nachsatz in ${}A_{\ell }$ gelten muss. Sowohl ${}\varphi (\ell ,-)$ als auch der Nachsatz von ${}A_{\ell }$ drücken die Wirkungsweise des Befehls ${}B_{\ell }$ aus, daher gilt die Abbildungsgleichheit genau dann, wenn ${}A_{\ell }$ wahr ist.

Zur bewiesenen Aussage