Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 14

Übungsaufgaben

Aufgabe

Zeige durch ein Beispiel, dass Lemma 14.5 ohne die Voraussetzung, dass eine surjektive Terminterpretation vorliegt, nicht gelten muss.

Aufgabe

Bestimme den Rang der folgenden Ausdrücke.

$a = f x$ ,
$\exists x a = f x$ ,
$(\neg R x y \land f f x = c) \to (\exists x a = f x)$ ,
$(\forall y R x y) \to (\exists x a = f x)$ .

Aufgabe

Zeige durch Induktion über den Aufbau der Ausdrücke, dass sich bei einer Termsubstitution der Rang eines Ausdrucks nicht ändert.

Aufgabe

Warum führt man im Beweis zum Satz von Henkin nicht Induktion über den Aufbau der Ausdrücke?

Das Symbolalphabet $S$ bestehe aus einer einzigen Variablen $x$ und einem einzigen einstelligen Relationssymbol $P$ . Zeige, dass zu einer Interpretation $I$ die Gültigkeitsmenge $I^{⊨} \subseteq L^{S}$ keine Beispiele enthalten muss.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Es seien $x, z$ verschiedene Variablen, $t$ ein $S$ -Term und $α$ ein $S$ -Ausdruck, wobei $z$ weder in $t$ noch in $α$ vorkomme. Gilt dann die Gleichheit