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

Beweis

Die Variablen seien durch die natürlichen Zahlen belegt. Wir müssen zeigen, dass die Gleichheit

genau dann gilt, wenn

gilt. Der Ausdruck gilt genau dann, wenn sämtliche Ausdrücke gelten. Es sei fixiert. Dann gelten sämtliche , , automatisch, da für diese Ausdrücke der Vordersatz nicht gilt. Die Gültigkeit von bei dieser Belegung bedeutet also, dass der Nachsatz in gelten muss. Sowohl als auch der Nachsatz von drücken die Wirkungsweise des Befehls aus, daher gilt die Abbildungsgleichheit genau dann, wenn wahr ist.