Arithmetische Ausdrucksmenge/Relation in N/Ableitbare Äquivalenz und Repräsentierung/Aufgabe/Lösung

Es sei ${}\Gamma \vdash \alpha \leftrightarrow \beta$ und es sei vorausgesetzt, dass ${}\alpha$ die Relation ${}R$ repräsentiert. Wir müssen zeigen, dass auch ${}\beta$ die Relation repräsentiert. Es sei zunächst ${}n\in R$. Dann ist

$\Gamma \vdash \alpha {\frac {n}{x}}$

wegen der Repräsentierbarkeit von ${}R$ durch ${}\alpha$. Nach Voraussetzung ist

$\Gamma \vdash \alpha \rightarrow \beta .$

Aus der Alleinführung im Sukzedens (die anwendbar ist, da in ${}\Gamma$ nur gebundene Variablen vorkommen) folgt

$\Gamma \vdash \forall x{\left(\alpha \rightarrow \beta \right)}.$

Das Einsetzungsaxiom sichert

$\vdash \forall x{\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha \rightarrow \beta \right)}{\frac {n}{x}},$

was

$\vdash \forall x{\left(\alpha \rightarrow \beta \right)}\rightarrow {\left(\alpha {\frac {n}{x}}\rightarrow \beta {\frac {n}{x}}\right)}$

bedeutet. Also gilt

$\Gamma \vdash \alpha {\frac {n}{x}}\rightarrow \beta {\frac {n}{x}}$

und somit

$\Gamma \vdash \beta {\frac {n}{x}}.$

Bei ${}n\not \in R$ gilt

$\Gamma \vdash \neg \alpha {\frac {n}{x}}$

und

$\Gamma \vdash \neg \alpha \rightarrow \neg \beta .$

Mit dem gleichen Schluss wie oben ergibt sich

$\Gamma \vdash \neg \alpha {\frac {n}{x}}\rightarrow \neg \beta {\frac {n}{x}}$

und somit

$\Gamma \vdash \neg \beta {\frac {n}{x}}.$

Zur gelösten Aufgabe