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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es sei , und . Wir setzen

Der Ausdruck repräsentiert in die volle Relation , da ja für jedes gilt , aber auch . Ferner gilt . Wir behaupten, dass nicht die Relation in repräsentiert, wobei wir nachweisen wollen. Um diese Nichtableitbarkeit zu zeigen, müssen wir aufgrund des Korrektheitssatzes eine Interpretation angeben, für die gilt, aber nicht gilt. Dazu wählen wir als Grundmenge , wobei wir die und die Multiplikation (die keine Rolle spielt) natürlich interpretieren, und wo wir die Addition auf natürlich interpretieren und setzen, sobald ein Summand negativ ist. Die Variable wird als interpretiert. Bei dieser Interpretation gilt dann weder noch ,

da überhaupt nicht als Wert der gewählten Addition auftaucht. Daher gilt wiederum die Äquivalenz bei dieser Interpretation. Die Ausdrücke für gelten bei der Interpretation, der Ausdruck bedeutet und gilt hingegen nicht, da bei der Wert von größer als ist und bei der Wert nach Definition gleich ist.
Zur gelösten Aufgabe