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

* Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
** Wenn $t_{1}$ und $t_{2}$ Terme sind, so ist ein Ausdruck.
    $t_{1}=t_{2}$
** Wenn $R$ ein $n$-stelliges Relationssymbol ist und $t_{1},\ldots ,t_{n}$ Terme sind, so ist ein Ausdruck.
    $Rt_{1}{\ldots }t_{n}$
** Wenn $\alpha$ und $\beta$ Ausdrücke sind, so sind auch Ausdrücke.
    $\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)}$
** Wenn $\alpha$ ein Ausdruck ist und $x$ eine Variable, so sind auch Ausdrücke.
    $\forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}$
* Ein Ideal ist eine nichtleere Teilmenge ${\mathfrak {a}}\subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
** Für alle $a,b\in {\mathfrak {a}}$ ist auch $a+b\in {\mathfrak {a}}$.
** Für alle $a\in {\mathfrak {a}}$ und $r\in R$ ist auch $ra\in {\mathfrak {a}}$.
* Die Variablensubstitution definiert man rekursiv über den Aufbau der $S$-Ausdrücke.
** 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}}}.$
** 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}}}.$
** 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}}}.$
** Für Ausdrücke $\alpha$ und $\beta$ setzt man und ebenso für die anderen zweistelligen Junktoren.
    $(\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}}}$
** 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 und ebenso für den Existenzquantor.
    $(\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}}$
* 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.