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

Es sei ${}R=\mathbb {N}$, ${}\alpha =\exists y{\left(x=y+0\right)}$ und ${}\beta =\exists y{\left(x=y+1\right)}$. Wir setzen

${}\Gamma =\{\alpha \leftrightarrow \beta ,\alpha {\frac {0}{x}},\alpha {\frac {1}{x}},\alpha {\frac {1+1}{x}},\alpha {\frac {1+1+1}{x}},{\rm {{etc}\}\,.}}$

Der Ausdruck ${}\alpha$ repräsentiert in ${}\Gamma$ die volle Relation ${}R=\mathbb {N}$, da ja für jedes ${}n\in \mathbb {N}$ gilt ${}n\in R$, aber auch ${}\Gamma \vdash \alpha {\frac {n}{x}}$. Ferner gilt ${}\Gamma \vdash \alpha \leftrightarrow \beta$. Wir behaupten, dass ${}\beta$ nicht die Relation in ${}\Gamma$ repräsentiert, wobei wir ${}\Gamma \not \vdash \beta {\frac {0}{x}}$ nachweisen wollen. Um diese Nichtableitbarkeit zu zeigen, müssen wir aufgrund des Korrektheitssatzes eine Interpretation angeben, für die ${}\Gamma$ gilt, aber ${}\beta {\frac {0}{x}}$ nicht gilt. Dazu wählen wir als Grundmenge ${}\mathbb {Z}$, wobei wir die ${}0,1$ und die Multiplikation (die keine Rolle spielt) natürlich interpretieren, und wo wir die Addition auf ${}\mathbb {N}$ natürlich interpretieren und ${}m+n=-2$ setzen, sobald ein Summand negativ ist. Die Variable ${}x$ wird als ${}-1$ interpretiert. Bei dieser Interpretation gilt dann weder ${}\alpha$ noch ${}\beta$,

da ${}-1$ überhaupt nicht als Wert der gewählten Addition auftaucht. Daher gilt wiederum die Äquivalenz ${}\alpha \leftrightarrow \beta$ bei dieser Interpretation. Die Ausdrücke ${}\alpha {\frac {n}{x}}$ für ${}n\in \mathbb {N}$ gelten bei der Interpretation, der Ausdruck ${}\beta {\frac {0}{x}}$ bedeutet ${}\exists y{\left(0=y+1\right)}$ und gilt hingegen nicht, da bei ${}y\geq 0$ der Wert von ${}y+1$ größer als ${}0$ ist und bei ${}y<0$ der Wert nach Definition gleich ${}-2\neq 0$ ist.

Zur gelösten Aufgabe