Mathematische Logik/Gemischte Definitionsabfrage/16/Aufgabe/Lösung

1. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
   1. Wenn ${}t_{1}$ und ${}t_{2}$ Terme sind, so ist

      $t_{1}=t_{2}$

      ein Ausdruck.
   2. Wenn ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist

      $Rt_{1}{\ldots }t_{n}$

      ein Ausdruck.

   3. Wenn ${}\alpha$ und ${}\beta$ Ausdrücke sind, so sind auch

      $\neg {\left(\alpha \right)},\,{\left(\alpha \right)}\wedge {\left(\beta \right)},\,{\left(\alpha \right)}\vee {\left(\beta \right)},\,{\left(\alpha \right)}\rightarrow {\left(\beta \right)},\,{\left(\alpha \right)}\leftrightarrow {\left(\beta \right)}$

      Ausdrücke.

   4. Wenn ${}\alpha$ ein Ausdruck ist und ${}x$ eine Variable, so sind auch

      $\forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}$

      Ausdrücke.

2. Ein Ideal ist eine nichtleere Teilmenge ${}{\mathfrak {a}}\subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
   1. Für alle ${}a,b\in {\mathfrak {a}}$ ist auch ${}a+b\in {\mathfrak {a}}$.
   2. Für alle ${}a\in {\mathfrak {a}}$ und ${}r\in R$ ist auch ${}ra\in {\mathfrak {a}}$.
3. Die Variablensubstitution definiert man rekursiv über den Aufbau der ${}S$-Ausdrücke.
   1. Für Terme ${}s_{1},s_{2}$ setzt man

      $(s_{1}=s_{2}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.$

   2. Für ein ${}n$-stelliges Relationssymbol ${}R$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ setzt man

      $(Rs_{1}\ldots s_{n}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=Rs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.$

   3. Für einen Ausdruck ${}\alpha$ setzt man

      $(\neg \alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\neg \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.$

   4. Für Ausdrücke ${}\alpha$ und ${}\beta$ setzt man

      $(\alpha \wedge \beta ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\wedge \beta {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$

      und ebenso für die anderen zweistelligen Junktoren.

   5. Für einen Ausdruck ${}\alpha$ seien ${}x_{i_{1}},\ldots ,x_{i_{r}}$ diejenigen Variablen (unter den $x_{1},\ldots ,x_{k}$), die in ${}\forall x\alpha$ frei vorkommen. Es sei ${}v=x$, falls ${}x$ nicht in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Andernfalls sei ${}v$ die erste Variable (in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge), die weder in ${}\alpha$ noch in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Dann setzt man

      $(\forall x\alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\forall v\alpha {\frac {t_{i_{1}},\ldots ,t_{i_{r}},v}{x_{i_{1}},\ldots ,x_{i_{r}},x}}$

      und ebenso für den Existenzquantor.

4. Der Ausdruck ${}\alpha$ heißt ableitbar, wenn er sich aus den Grundtautologien, also
   • den aussagenlogischen syntaktischen Tautologien,
   • den Gleichheitsaxiomen,
   • der Existenzeinführung im Sukzedens,

durch sukzessive Anwendung der Ableitungsregeln Modus ponens und der Existenzeinführung im Antezedens erhalten lässt.

Die Abbildung ${}F$ heißt arithmetisch repräsentierbar, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die Äquivalenz ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r+s})$ gilt.

Eine unter aussagenlogischen Ableitungen abgeschlossene Teilmenge der modallogischen Sprache heißt (formale) Modallogik.

Zur gelösten Aufgabe