Arithmetische Ausdrucksmenge/Relation in N/Ableitbare Äquivalenz und Repräsentierung/Aufgabe/Lösung
Es sei und es sei vorausgesetzt, dass die Relation repräsentiert. Wir müssen zeigen, dass auch die Relation repräsentiert. Es sei zunächst . Dann ist
wegen der Repräsentierbarkeit von durch . Nach Voraussetzung ist
Aus der Alleinführung im Sukzedens (die anwendbar ist, da in nur gebundene Variablen vorkommen) folgt
Das Einsetzungsaxiom sichert
was
bedeutet. Also gilt
und somit
Bei gilt
und
Mit dem gleichen Schluss wie oben ergibt sich
und somit